解答つき整数論と合同式ワークシート

無料で印刷できる整数論と合同式のワークシート：やさしい問題から試験レベルまで 6 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい
aqbr136=?·108+??=?·?+??=?·?+??=?·?+?

ユークリッドの互除法を使って gcd(136, 108) を求めてください。

a = 136b = 108
gcd(136, 108) =
2.やさしい
012345678910mod 11

0 ≤ r < 11 を満たす余り r、つまり (−78) mod 11 を求めてください。

a = −78n = 11
(−78) mod 11 =
3.ふつう

71 を法とする 27 の逆元を求めてください：0 < x < 71 かつ 27·x ≡ 1 (mod 71) を満たす数 x です。

a = 27n = 71
27−1 mod 71 =
4.ふつう

オイラーのトーシェント関数 φ(1125)、つまり 1 から 1125 までの整数のうち 1125 と互いに素なものの個数を求めてください。

n = 1125 = 32·53
φ(1125) =
5.むずかしい
42c = me​ mod n?m = cd​ mod nm(n, e) = (55, 7)d

メッセージ m = 42 を RSA 公開鍵 (n, e) = (55, 7) で暗号化してください。暗号文 c を求めてください。

n = 55e = 7m = 42
c =
6.むずかしい

反復二乗法を使って 549 mod 47 を求めてください。

a = 5k = 49n = 47
549 mod 47 =

解答

  1. 1. gcd(136, 108) = 4
  2. 2. (−78) mod 11 = 10
  3. 3. 27−1 mod 71 = 50
  4. 4. φ(1125) = 600
  5. 5. c = 48
  6. 6. 549 mod 47 = 31

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。