1.やさしい
ユークリッドの互除法を使って gcd(86, 74) を求めてください。
a = 86b = 74
gcd(86, 74) =
解答つき整数論と合同式ワークシート
2.やさしい
最小公倍数 lcm(47, 29) を求めてください。まずユークリッドの互除法で gcd を求めましょう。
a = 47b = 29
lcm(47, 29) =
3.ふつう
48x ≡ 41 (mod 71) を解いてください。0 < x < 71 を満たす解 x を答えてください。
48x ≡ 41 (mod 71)
x =
4.ふつう
19 を法とする 12 の逆元を求めてください：0 < x < 19 かつ 12·x ≡ 1 (mod 19) を満たす数 x です。
a = 12n = 19
12−1 mod 19 =
5.むずかしい
反復二乗法を使って 3142 mod 20 を求めてください。
a = 3k = 142n = 20
3142 mod 20 =
6.むずかしい
31 は素数です。フェルマーの小定理を使って 2325932 mod 31 を求めてください。
p = 31k = 25932
2325932 mod 31 =
解答
- 1. gcd(86, 74) = 2
- 2. lcm(47, 29) = 1363
- 3. x = 26
- 4. 12−1 mod 19 = 8
- 5. 3142 mod 20 = 9
- 6. 2325932 mod 31 = 2
ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。