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

0 ≤ r < 4 を満たす余り r、つまり 693 mod 4 を求めてください。

最小公倍数 lcm(53, 16) を求めてください。まずユークリッドの互除法で gcd を求めましょう。

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

x ≡ 2 (mod 3) かつ x ≡ 0 (mod 10) を満たす最小の正の整数 x を求めてください。

ある RSA 鍵は、素数 p = 23 と q = 47、公開指数 e = 5 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。

53 は素数です。フェルマーの小定理を使って 4³⁰⁰⁷¹ mod 53 を求めてください。