乘法逆元、消去律
- 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}
c1c1−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