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

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

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

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

ポイント: 「不定方程式ふていほうていしき」 と 「合同式ごうどうしき」 は 同どう じ こ と を 違 う 表ひょう現げん で 言げん っ て い る だ け。 (ax \equiv b \pmod{m}) は (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) と し ま す。 ま ず 拡張かくちょう互除法じょほう で (ax_0 + by_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, \quad Y = Y_0 - \frac{a}{d} t \quad (t \in \mathbb{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 + 11 t, \quad y = 2 - 7 t \quad (t \in \mathbb{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, \quad y = 1 - 2t \quad (t \in \mathbb{Z}) ]

2. 合同ごうどう式しき

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

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

[ a \equiv b \pmod{m} ]

と 書しょ き、 「(a) と (b) は (m) を 法ほう と し て 合同ごうどう」 と 言げん い ま す。 (\bmod) は 法ほう (modulus) を 表ひょう し ま す。

例れい

• (17 \equiv 2 \pmod{5}) (17 - 2 = 15 は 5 の 倍数ばいすう)
• (100 \equiv 4 \pmod{6}) (100 - 4 = 96 = 6 \cdot 16)
• (-3 \equiv 4 \pmod 7) (-3 - 4 = -7)

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

(a \equiv b)、 (c \equiv d \pmod{m}) の と き

演算えんざん	性質せいしつ
加法かほう	(a + c \equiv b + d \pmod{m})
減法げんぽう	(a - c \equiv b - d \pmod{m})
乗法じょうほう	(a c \equiv b d \pmod{m})
累乗るいじょう	(a^k \equiv b^k \pmod{m})

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

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 \pmod{10})。 以い降こう 4 周期しゅうき で 巡回じゅんかい。 (100 = 4 \cdot 25) な の で (7^{100} \equiv (7^4)^{25} \equiv 1^{25} = 1 \pmod{10})。 答こたえ え は 1。

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

(2^{1000}) を 7 で 割わり っ た 余よ り は ?

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

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

形かたち

[ ax \equiv b \pmod{m} ]

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

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

解法かいほう の 流ながれ

(ax \equiv b \pmod m) は 「(ax + my = b)」 と 同どう じ。 拡張かくちょう互除法じょほう で (x) を 求もとめ め、 (\bmod 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 \pmod 7)。 両辺りょうへん に 3 を か け て

(x \equiv 3 \cdot 3 = 9 \equiv 2 \pmod 7)。 答こたえ え は (x \equiv 2 \pmod 7) (= ..., -5, 2, 9, 16, ...)。

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

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

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

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

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