C/C++教程

CINTA拓展作业二

本文主要是介绍CINTA拓展作业二,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

乘法逆元、消去律

    • 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​

这篇关于CINTA拓展作业二的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!