CINTA-04

发表于 2022-10-16 更新于 2022-10-17 分类于 CINTA 阅读次数：

CINTA作业三

1、设\(p=23\) 和\(a=3\)，使用费尔马小定理计算\(a^{2019}\ mod\ p\).

解：由题得，代入\(p,a\)得 \(3^{2019}\ mod\ 23\).

原式=\(3^{91\times22+17}\ mod\ 23\).

因为\(3^{22}\equiv1\ (mod\ 23)\)

所以原式=\(3^{17}\ mod\ 23\ =\ 3^{22-5}\ mod\ 23\ =3^{-5}\ mod\ 23\).

求3的乘法逆元，\(33^{-1}\equiv1\ (mod\ 23)\),由扩展欧几里得算法可得\(3^{-1}=8\)，即3的乘法逆元为8

所以原式=\(8^5\ mod\ 23=16\).

2、使用费尔马小定理求解同余方程\(x^{50}\equiv2\ (mod\ 17)\).

解：由题可得\(x^{50}\ mod\ 17=x^{16\times3+2}\ mod\ 17=x^2\ mod\ 17\).

所以原式=\(x^2\equiv2\ (mod\ 17)\)，即\(x^2-2=k\times17,k\in\mathbb{Z}\).

所以\(x=\pm\sqrt{17k+2}\).

5、请证明13 整除\(2^{70}+3^{70}\)。

解：由题得即证明\(2^{70}+3^{70}\equiv0\ (mod\ 13)\)成立；

因为\(gcd(2,13)=gcd(3,13)=1\)，所以上式可化为\(2^{70}\equiv0\ (mod\ 13)+3^{70}\equiv0\ (mod\ 13)\);

再利用费尔马小定理化简得\(2^{12\times6-2}\equiv2^{-2}\equiv0\ (mod\ 13)+3^{12\times6-2}\equiv3^{-2}\ (mod \ 13)\)

由扩展欧几里得定理算出2和3 的乘法逆元分别为\(-6\)和\(-4\)；

所以上式可写为\(36\equiv0\ (mod\ 13)+16\equiv0\ (mod\ 13)\to52\equiv0\ (mod\ 13)\);

显然成立，得证。

6、使用欧拉定理计算\(2^{100000}\ mod\ 55\).

解：因为\(gcd(2,55)=1\)，所以\(2^{\phi(55)}\equiv1\ (mod\ 55)\)，又\(\phi(55)=\phi(5\times11)\)，又5与11都是素数，

由欧拉phi函数性质可得\(\phi(55)=\phi(5\times11)=\phi(5)\times\phi(11)=40\)；所以\(2^{40}\equiv1\ (mod\ 55)\),

所以原式=\(2^{100000}\ mod \ 55=2^{40\times2500}\ mod\ 55\)，

所以原式可由2500个\(2^{40}\equiv1\ (mod\ 55)\)相乘得到，即\(2^{100000}\equiv1\ (mod\ 55)\);

所以\(2^{100000}\ mod\ 55=1\).

8、手动计算\(7^{1000}\) 的最后两个数位等于什么?

解：由题得题目可看成计算\(7^{1000}\ mod\ 100\)的结果，

由欧拉定理与欧拉phi函数性质可得：\(\phi(100)=\phi(4\times25)=\phi(4)\times\phi(25)=2\times20=40\);

所以\(7^{1000}\ mod\ 100=7^{40*25}\ mod\ 100\)

所以\(7^{1000}\equiv7^0\ (mod\ 100)\);

所以\(7^{1000}\ mod\ 100=1\);

所以\(7^{1000}\)最后两位为01.

9、编写Python 语言程序完成欧拉Phi 函数的计算，即输入正整数n，计算并返回\(\phi(n)\).

def gcd(a, b): # 判断互素
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def euler_phi(n):
    num = 1
    for i in range(2, n):
        if gcd(i, n) == 1:
            num += 1
    return num

10、设p 是素数，计算\((p-1)!\ mod\ p\)，并找出规律，写成定理，并给出证明。

解：列举几个

当p=2；\((p-1)!\ mod\ p=1\)；

当p=3；\((p-1)!\ mod\ p=2\)；

当p=5；\((p-1)!\ mod\ p=4\)；

当p=7；\((p-1)!\ mod\ p=6\)；.......

所以猜想\((p-1)!\ mod\ p=p-1\)，即\((p-1)!\equiv(p-1)\ (mod\ p)\)；

证明：实在是不会证明，想用归纳法证明，但是素数并不是连续的，不会用，参考一下威尔逊定理再结合一下上课时讲的逆元一一对应的问题

使用消去律将上式变成\((p-2)!\equiv1\ (mod\ p)\);

若[1, p-2]中的整数能存在一一对应的逆元使其两两对应，即\(aa^{-1}bb^{-1}cc^{-1}...\equiv1\ (mod\ p)\),该式必定能成立。

因为1的逆元是1，且当\(p=2\)时，该定理成立，又p是素数，所以在\(p>2\)时，\(p-2\)必定时奇数，

在\([1,p-2],p>2\)中去掉1，就刚好有偶数个整数，即证明这偶数个整数能一一匹配成逆元；

设\(a\in(1,p-2]\)，证存在\(a^{-1}\in(1,p-2]\)使\(aa^{-1}\equiv1\ (mod\ p)\),且\(a\ne a^{-1}\);

假设\(a=a^{-1}\),则\(aa^{-1}\equiv1\ (mod\ p)\to a^2\equiv1\ (mod\ p)\),此时\(a\)只有\(1\)与\(p-1\)两个解，都不在范围内，

所以\(a\ne a^{-1}\);

再证明\(a,a^{-1}\)是否是一一对应；

假设存在\(a_1,a_2\)都是a的逆元，则\(aa_1\equiv1\ (mod\ p),aa_2\equiv1\ (mod\ p)\)，即\(aa_1\equiv aa_2\ (mod\ p)\),

使用消去律得\(a_1\equiv a_2\ (mod\ p)\),

所以\(a,a^{-1}\)是一一对应的。

所以再\((1,p-2]\)的偶数个整数中存在若干对能一一匹配的逆元，所以他们的乘积符合\((p-2)!\equiv1\ (mod\ p)\);

所以得证.