乘法逆元、消去律

• • 1、给出正整数a和m，gcd(a,m)=1，请问，a模m的乘法逆元（在mod m的意义下）是唯一的吗？为什么？请证明。
  • 2、设p是素数，计算(p-1)! mod p，并找出规律（可编写一个程序），写成定理，并给出证明。（！表示阶乘）
  • 3、思考另一个版本的消去律。设 a , b , c ∈ Z a, b, c \in \Z a,b,c∈Z， m m m是一个正整数。如果 g c d ( c , m ) = g gcd(c, m) = g gcd(c,m)=g， g g g是大于一的整数，且 a c ≡ b c ( m o d m ) ac \equiv bc \pmod{m} ac≡bc(modm)。 请问此时能消去 c c c得到某个同余式 a ≡ b ( m o d m ′ ) a \equiv b \pmod{m'} a≡b(modm′)吗？这个 m ′ m' m′会是什么？给出证明。

1、给出正整数a和m，gcd(a,m)=1，请问，a模m的乘法逆元（在mod m的意义下）是唯一的吗？为什么？请证明。

证明如下：
设存在 a − 1 a^{-1} a−1满足： a a − 1 ≡ 1 ( m o d 55 ) aa^{-1}\equiv 1 \pmod {55} aa−1≡1(mod55)
因为：gcd(a,m)=1，由Bezout定理得，存在唯一的Bezout系数使得： a r + m s = 1 ar+ms=1 ar+ms=1，即 a r ≡ 1 ( m o d m ) ar\equiv 1 \pmod m ar≡1(modm)
故乘法逆元 a − 1 a^{-1} a−1=r，且是唯一的。

2、设p是素数，计算(p-1)! mod p，并找出规律（可编写一个程序），写成定理，并给出证明。（！表示阶乘）

定理：
( p − 1 ) ! m o d    p = （ p − 1 ） (p-1)! \mod p=（p-1） (p−1)!modp=（p−1）
（证明真不会qwq）

3、思考另一个版本的消去律。设 a , b , c ∈ Z a, b, c \in \Z a,b,c∈Z， m m m是一个正整数。如果 g c d ( c , m ) = g gcd(c, m) = g gcd(c,m)=g， g g g是大于一的整数，且 a c ≡ b c ( m o d m ) ac \equiv bc \pmod{m} ac≡bc(modm)。 请问此时能消去 c c c得到某个同余式 a ≡ b ( m o d m ′ ) a \equiv b \pmod{m'} a≡b(modm′)吗？这个 m ′ m' m′会是什么？给出证明。

证明如下：
由gcd(c,m)=g，设 m_1= m g \frac mg gm​ ， c_1= c g \frac cg gc​，则gcd( c 1 , m 1 c_1,m_1 c1​,m1​)=1，由 a c ≡ b c ( m o d m ) ac \equiv bc \pmod{m} ac≡bc(modm)，有：m|(a-b)c
所以有 m 1 m_1 m1​|(a-b) c 1 c_1 c1​，即 a c 1 ≡ b c 1 ( m o d m 1 ) ac_1 \equiv bc_1 \pmod{m_1} ac1​≡bc1​(modm1​)
由于 g c d ( c 1 , m 1 ) = 1 gcd(c_1,m_1)=1 gcd(c1​,m1​)=1，由Bezout定理得，存在唯一的 c 1 − 1 c_1^{-1} c1−1​，使得： c 1 c 1 − 1 ≡ 1 ( m o d m 1 ) c_1c_1^{-1} \equiv 1 \pmod{m_1} c1​c1−1​≡1(modm1​)
所以有： a ≡ b ( m o d m 1 ) a \equiv b \pmod{m_1} a≡b(modm1​)，其中： m 1 = m g m_1=\frac mg m1​=gm​