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

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

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

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

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

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

43 は素数です。フェルマーの小定理を使って 29⁶⁵⁹³⁵ mod 43 を求めてください。