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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

大きな数をそのまま掛け算せずに (186·852 + 156) mod 8 を求めましょう：まず簡約します。

n = 8
(186·852 + 156) mod 8 =
2.やさしい
aqbr1008=?·609+??=?·?+??=?·?+??=?·?+??=?·?+?

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

a = 1008b = 609
gcd(1008, 609) =
3.ふつう

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

n = 45 = 32·5
φ(45) =
4.ふつう

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

a = 22n = 97
22−1 mod 97 =
5.むずかしい

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

a = 65k = 139n = 77
65139 mod 77 =
6.むずかしい
mc = me​ mod n241m = cd​ mod n?(n, e) = (301, 5)d

ある RSA 鍵は p = 7、q = 43、e = 5 を使います。暗号文 c = 241 を復号して、メッセージ m を求めてください。

p = 7q = 43e = 5c = 241
m =

解答

  1. 1. (186·852 + 156) mod 8 = 4
  2. 2. gcd(1008, 609) = 21
  3. 3. φ(45) = 24
  4. 4. 22−1 mod 97 = 75
  5. 5. 65139 mod 77 = 65
  6. 6. m = 278

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