Basic theorem of number theory, Euler function and Euler power reduction formula

Source of ideas

Blog.csdn.net/qq_41157137…

tips

Found himself really is again and again of the dead cut to prove, as expected is meaningless……

The knowledge I learned in November last year, I dug it once in February and again in July…

In the future or less cut proof is better, can use……

Invitational tournament also encountered generalized Euler reduced powers this application…

Knowledge arrangement

1. Wilson theorem

When p is prime, (p-1) factorial = -1 (mod p)

(p – 1)! If + 1 goes into p, p is prime

Fermat’s Little Theorem

Euler’s theorem

4. Pei Shu Theorem

Ax + by = m has an integer solution if and only if m is a multiple of d

5. Euler factor summation

Assume that the factors of n are d1, d2…… Di is the sum of the Euler functions.F of n is also an integral functionFor the prime number p, the factors of p ^ k are p, p ^ 2, p ^ 3…… P to the k, combined with the formula ②, you getAccording to the unique decomposition theoremF of m.

6. Sum of mutual prime numbers

Among the numbers less than m, the sum of the numbers that are interchangeable with m is: ，The first thing to knowIf n is coprime with m, then m-n is coprime with m, so when m> 1, the numbers that are interchangeable with m always appear in a pair of pairs, and the sum of each pair is M, totalright

7. Euler generalized reduced power