证明70！≡61！（mod 71）

根据费马小定理，对于任意正整数a和质数p，有a^(p-1) ≡ 1 (mod p)。因为71是质数，所以有：

70! ≡ 70 × 69 × 68 × ... × 1 ≡ (70 × 69 × 68 × ... × 2) × 1 ≡ (70 × 69 × 68 × ... × 2) × 71^(–1) (mod 71)

其中，71^(–1)表示71在模71意义下的逆元。由于71是质数，所以71^(–1) ≡ 1 (mod 71)。因此：

70! ≡ (70 × 69 × 68 × ... × 2) × 1 ≡ (70 × 69 × 68 × ... × 2) × 71^(–1) ≡ (70 × 69 × 68 × ... × 2) × 1 ≡ 61! (mod 71)

因此，70! ≡ 61! (mod 71)。

相关问题

若(a,m)=1,b≡a( mod n),证明(b,m)= 1.

我们可以使用反证法证明该命题。假设(b,m)≠1，则存在一个大于1的公因数d，满足d|(b,m)。由于(a,m)=1，所以存在整数x和y，使得ax+my=1。我们将其两边同时乘以b，得到b(ax)+b(my)=b。由于b≡a(mod n)，所以可以将其改写为b(ax)+nq=my。将b(ax)代入得到b(ax)+nq=my，即b(ax)+nq≡1(mod m)。这表明b和m的最大公因数不为1，与假设矛盾。因此，我们得出结论：若(a,m)=1，b≡a(mod n)，则(b,m)=1。

Given a, x, y, m ∈ Z, m > 0. Show that (i) (1 pt) ax ≡ ay (mod m) iff x ≡ y  mod gcd( m a, m)  . (ii) (1 pt) If ax ≡ ay (mod m) and gcd(a, m) = 1, then x ≡ y (mod m

).我理解您需要我解答一个数学问题。根据您的要求，我可以回答该问题。首先，我们来看第一个问题。如果 ax ≡ ay (mod m)，则有 ax = ay + km（其中k为整数）。将公式两边同时除以 gcd(m, a)，得到 (m, a) 是 gcd(m, a) 的倍数，即存在整数 t，使得 m = t gcd(m, a)、a = s gcd(m, a)。将这个结果带回原公式，得到 ts gcd(m, a) x ≡ ts gcd(m, a) y + (k/t) m。因为 gcd(m, a) 是 m 和 a 的最大公约数，所以 gcd(m/t, a/s) = 1。因此，公式可以进一步转化为 xs ≡ ys (mod m/t)，这里 m/t 和 a/s 都是整数。这也就证明了 x ≡ y (mod gcd(m, a))。

接着看第二个问题。如果 ax ≡ ay (mod m)，且 gcd(a, m) = 1，那么我们可以先假设 x, y 不相等。根据第一个问题，得到 a(x-y) ≡ 0 (mod m)。因为 gcd(a, m) = 1，所以 a(x-y) 只能被 m 整除，也就是 x-y 只能为 0。这证明了 x ≡ y (mod m)。

希望这样的解答可以帮助您解决问题。