Table of Contents

First, the basic operation law

Second, Elimination Law

Three, Euler function

four, Euler's Theorem

V. Reference

I. Basic operation laws

2. Elimination Law

     Theorem (elimination law): If gcd(c,p) = 1 , then ac ≡ bc mod p leads to a ≡ (b mod p)

3. EulerFunction

The Euler function is a very important function in number theory. The Euler function refers to: for a positive integer n, the number of positive integers less than n and relatively prime to n is denoted as: φ(n), whereφ(1) is defined as 1, but does not have any substantial meaning.

Define the set of numbers less than n and relatively prime to n as Zn, and call this set the complete remainder set of n.

Obviously, for a prime number p, φ(p) = p -1. For two prime numbers p, q, their product n = pq satisfies φ(n) =(p-1)(q-1)

Prove: For prime numbers p, q, satisfy φ(n) =(p-1)(q-1)

Consider the complete remainder set Zn = { 1,2,....,pq -1} of n, and the set that is not coprime to n consists of the union of the following three sets:

        1) The set {p,2p,3p,....,(q-1)p} that is divisible by p is q-1 in total

2) The set {q,2q,3q,....,(p-1)q} that is divisible by q has a total of p-1

3) Obviously, there are no common elements in sets 1 and 2, so the number of elements in Zn = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

Four. Euler's Theorem

V. Reference

https://zh.m.wikipedia.org/zh-hans/%E6%A8%A1%E9%99%A4a>

MOD operation_BaiduEncyclopedia

https://www.jianshu.com/p/4fadf3e45764