不定ふてい方程式ほうていしき (ax+by=c, 一いち次じ合同ごうどう式しき)

この章しょうで学まなぶこと

$\gcd$ を求もとめる道具どうぐ (互除法じょほう) を使つかって、 いよいよ 整せい数すう解かいを持もつ方程式ほうていしき に取とり組くみます。 ここでは一いち次じ不定方程式ふていほうていしきと合同式ごうどうしきの基本きほんを押おさえます。

• 一いち次じ不定方程式ふていほうていしき $ax+by=c$ の 整せい数すう解かいがある条件じょうけん
• 一ひとつの解かいから 一いっ般ぱん解 を表あらわす
• 合同式ごうどうしき の表記ひょうき$a\equiv b\left(modm\right)$
• 一次合同式いちじごうどうしき $ax\equiv b\left(modm\right)$ の解法かいほう
• 大おおきな数かずの余あまり問題もんだいを合同ごうどう式しきで解とく

ポイント: 「不定方程式ふていほうていしき」 と 「合同式ごうどうしき」 は 同おなじことを違ちがう表ひょう現げんで言いっているだけ。 $ax\equiv b\left(modm\right)$ は $ax-my=b$ と等とう価かです。

1. 一いち次じ不定ふてい方程式ほうていしき ax + by = c

解かいが存在そんざいする条件じょうけん

整せい数すう $a,b,c$ と $d=\gcd (a,b)$ としたとき、 $ax+by=c$ が整せい数すう解かいを持もつ必ひつ要よう十じゅう分ぶん条件じょうけんは $d\mid c$ です。

例れい

• $6x+8y=14$: $\gcd (6,8)=2$、 $2\mid 14$ → 解かいあり
• $6x+8y=9$: $2\nmid 9$ → 整せい数すう解かいなし

一般いっぱん解かいの求もとめ方

$d\mid c$ とします。 まず拡張かくちょう互除法じょほうで $a{x}_0+b{y}_0=d$ の解かいを求もとめ、 両辺りょうへんを $c/d$倍して一ひとつの解$(X_0,Y_0)=(x_0\cdot c/d, y_0\cdot c/d)$ を得えます。 このとき すべての整せい数すう解かい は

$X=X_0+\frac{b}{d}t,Y=Y_0-\frac{a}{d}t(t\in Z)$

と表あらわせます。

例題れいだい 1: 7x + 11y = 1

$\gcd (7,11)=1$ なので整せい数すう解かいあり。 互除法じょほうと逆ぎゃく算で

$11=7\cdot 1+4$、 $7=4\cdot 1+3$、 $4=3\cdot 1+1$。

$1=4-3=4-(7-4)=4\cdot 2-7=(11-7)\cdot 2-7=11\cdot 2-7\cdot 3$。

整形せいけいすると $7\cdot (-3)+11\cdot 2=1$。 したがって 1 つの解かいは $(x,y)=(-3,2)$。 一いっ般ぱん解は

$x=-3+11t,y=2-7t(t\in Z)$

例題れいだい 2: 12x + 18y = 30

$d=\gcd (12,18)=6$、 $6\mid 30$ → 解かいあり。 両辺りょうへんを 6 で割われると $2x+3y=5$。

$2\cdot 1+3\cdot 1=5$ を観察かんさつで見みつけると (x, y) = (1, 1) が 1 つの解かい。 一いっ般ぱん解は

$x=1+3t,y=1-2t(t\in Z)$

2. 合同ごうどう式しき

表記ひょうきと定義ていぎ

整せい数すう $a,b$ と正せいの整せい数すう $m$ について、 $a-b$ が $m$ の倍ばい数すう (= $m\mid (a-b)$) であるとき、

$a\equiv b\left(modm\right)$

と書かき、 「$a$ と $b$ は $m$ を法ほうとして合同ごうどう」 と言いいます。 $<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>$ は 法ほう (modulus) を表あらわします。

例れい

• $17\equiv 2\left(mod5\right)$ (17 - 2 = 15 は 5 の倍数ばいすう)
• $100\equiv 4\left(mod6\right)$ (100 - 4 = 96 = 6 \cdot 16)
• $-3\equiv 4\left(mod7\right)$ (-3 - 4 = -7)

合同ごうどう式しきの性質せいしつ

$a\equiv b$、 $c\equiv d\left(modm\right)$ のとき

演算えんざん	性質せいしつ
加法かほう	$a+c\equiv b+d\left(modm\right)$
減法げんぽう	$a-c\equiv b-d\left(modm\right)$
乗法じょうほう	$ac\equiv bd\left(modm\right)$
累乗るいじょう	$a^k\equiv b^k\left(modm\right)$

注意ちゅうい: 一いっ般ぱんに 「両辺りょうへんを同おなじ数かずで割われる」 ことはできません。 例れい: $6\equiv 0\left(mod6\right)$ だが、 両辺りょうへんを 2 で割われると $3\equiv 0\left(mod6\right)$ となり偽にせ。 割わり算ざんには別べっ途と 「逆元げん」 が必ひつ要ようです。

3. 大おおきな数かずの余あまり

計算けいさん例れい 1: 末尾まつびだけ知しりたい

$7^{100}$ を 10 で割わった余あまり (= 一いちの位くらい) は ?

$7^1=7, 7^2=49\equiv 9, 7^3\equiv 63\equiv 3, 7^4\equiv 21\equiv 1\left(mod10\right)$。 以い降こう 4 周期しゅうきで巡回じゅんかい。 $100=4\cdot 25$ なので $7^{100}\equiv (7^4{)}^{25}\equiv 1^{25}=1(mod10)$。 答えこたえは 1。

計算けいさん例れい 2: フェルマーの小しょう定理ていり風ふう

$2^{1000}$ を 7 で割わった余あまりは ?

$2^1=2, 2^2=4, 2^3=8\equiv 1\left(mod7\right)$。 したがって周期しゅうき 3。 $1000=3\cdot 333+1$ なので $2^{1000}\equiv 2^1=2\left(mod7\right)$。

4. 一いち次じ合同ごうどう式しき

形

$ax\equiv b\left(modm\right)$

解かいが存在そんざいする条件じょうけん

$d=\gcd (a,m)$ として、 $d\mid b$ のとき、 かつそのときに限かぎって解かいが存在そんざいします。 解かいがあるとき、 法$m$ のもとで解かいは $d$個 あります。

解法かいほうの流ながれ

$ax\equiv b\left(modm\right)$ は 「$ax+my=b$」 と同おなじ。 拡張かくちょう互除法じょほうで $x$ を求もとめ、 $<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow> m$ で整せい理りする。

例題れいだい 3: 5x ≡ 3 (mod 7)

$\gcd (5,7)=1\mid 3$ → 解かいあり (法ほう 7 のもとで 1 個こ)。

5 \cdot 3 = 15 \equiv 1 \pmod 7 なので $5^{-1}\equiv 3\left(mod7\right)$。 両辺りょうへんに 3 をかけて

$x\equiv 3\cdot 3=9\equiv 2\left(mod7\right)$。 答えこたえは $x\equiv 2\left(mod7\right)$ (= ..., -5, 2, 9, 16, ...)。

例題れいだい 4: 6x ≡ 4 (mod 10)

$\gcd (6,10)=2\mid 4$ → 解かいあり、 法ほう 10 のもとで 2 個こ。 両辺りょうへんと法ほうを 2 で割われると $3x\equiv 2\left(mod5\right)$。 $3\cdot 2=6\equiv 1\left(mod5\right)$ なので $3^{-1}\equiv 2\left(mod5\right)$。 したがって $x\equiv 2\cdot 2=4\left(mod5\right)$、 つまり法ほう 10 では $x=4$ と $x=9$ の 2 つ。

5. 章しょう末まつまとめ

内ない容よう	ポイント
$ax+by=c$	解かいの条件じょうけん: $\gcd (a,b)\mid c$
一いっ般ぱん解	$X=X_0+\frac{b}{d}t, Y=Y_0-\frac{a}{d}t$
合同ごうどう式しき	$a\equiv b\left(modm\right)$ は 「差さが $m$ の倍ばい数すう」
加減かげん乗じょう	法ほうを保たもったまま計算けいさん可か
一いち次じ合同ごうどう式しき	拡張かくちょう互除法じょほうか逆元げんで解とく

次じの章しょうでは: 整せい数すうから図形ずけいへ。 三角形さんかくけいの 5 つの 心しん (重心じゅうしん・外心がいしん・内心ないしん・垂心すいしん・傍心ぼうしん) とその性せい質しつを学まなびます。