数论与模运算练习卷（附答案）

求最小公倍数 lcm(507, 416)。先用欧几里得算法求最大公约数。

用欧几里得算法求 gcd(686, 476)。

解 66x ≡ 70 (mod 79)。给出满足 0 < x < 79 的解 x。

求欧拉函数 φ(351)，即 1 到 351 中与 351 互素的整数个数。

某个 RSA 密钥使用素数 p = 13 和 q = 31，公钥指数 e = 11。求私钥指数 d（0 < d < φ(n)）。

13 是素数。用费马小定理求 11³⁵⁵⁰² mod 13。