第三次作业

第三次作业

由费尔马小定理得：

所以

所以

找规律：

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)

代数计算可得

证明如下：

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

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

解得:

其余两两配对;故而

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