✨ 最佳解答 ✨
与えられた合同式は、8x ≡ 7 (mod 15) です。
この式は、「8x を 15 で割った余りが 7 である」という意味です。
この合同式を解くために、拡張ユークリッドの互除法を使います。
■拡張ユークリッドの互除法
拡張ユークリッドの互除法は、2つの整数 a と b の最大公約数 (GCD) を求めると同時に、
ax + by = GCD(a, b) を満たす整数 x と y を求める方法です。
■手順
●15 と 8 の最大公約数を求める
15 = 8 × 1 + 7
8 = 7 × 1 + 1
7 = 1 × 7 + 0
したがって、GCD(15, 8) = 1 です。
●拡張ユークリッドの互除法を使って、15x + 8y = 1 を満たす整数 x と y を求める
1 = 8 - 7 × 1
1 = 8 - (15 - 8 × 1) × 1
1 = 8 - 15 × 1 + 8 × 1
1 = 8 × 2 - 15 × 1
したがって、x = -1, y = 2 です。
●合同式を解く
8x ≡ 7 (mod 15)
8 × 2 ≡ 1 (mod 15)
両辺に 7 をかけると、
8 × 2 × 7 ≡ 7 (mod 15)
8 × 14 ≡ 7 (mod 15)
したがって、x ≡ 14 (mod 15) となります。
■答え
したがって、合同式 8x ≡ 7 (mod 15) の解は、x ≡ 14 (mod 15) です。
つまり、x = 14 + 15k (k は整数) と表すことができます。
■画像について
画像では、拡張ユークリッドの互除法を計算しているように見えます。
画像内の計算と上記の計算を比較すると、同じ結果になっていることがわかります。
