Modulo operation (MOD)

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