第三次作业

第三次作业

1.

$3^{2019}(mod~23)$

$已知3^{3}\equiv2^{2}(mod~23),3^{17}\equiv3^{3}3^{3}3^{11}(mod~23)$

2.

5.

由费尔马小定理得：

所以

所以$2^{10}\equiv2^{4}2^{4}2^{2}\equiv334\equiv10(mod~13)$

6.

$55=511,5和11都是素数，所以\phi(55)=(5-1)(11-1)=40$

8.

找规律：

9.

def euler_function(n):
    j = 0
    for i in range(2, n):#欧几里得算法求是否互素
        a = n
        q = i
        r = a % i
        while r != 1 and r != 0:
            a = int(q)
            q = int(r)
            r = int(a) % int(q)
        if r == 1:
            j += 1
        elif r == 0:
            pass
    print(j)

10.

代数计算可得

证明如下：

若是素数,取集合 ; 则A 构成模p乘法的简化剩余系,即任意使得:

那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况

解得:

其余两两配对;故而

(不会证明……，这是离散数学书上对威尔逊定理的必要性证明)