CINTA拓展作业二

乘法逆元、消去律

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​

上一篇:Kubernetes 弹性伸缩全场景解析 (一):概念延伸与组件布局


下一篇:GantD - 专注于数据密集型业务场景|基于AntD聚合型React组件库