Number theory -- detailed proof of Euler function, sieve method for Euler function, Euler theorem and Fermat theorem

Euler function

What is an Euler function ？

Euler function _ Baidu Encyclopedia

In number theory , Right integer n, The Euler function is less than n And n The number of Coprime numbers

How to find Euler function ？

The formula for finding Euler function is given below ,N The result of decomposing the prime factor is p1^α1 × p2^α2 × . . . × pk^αk, To find the Euler function of a number, we need to decompose its prime factor first , So Euler function φ(N) The results are as follows

 

Based on the fundamental theorem of arithmetic , For an integer N The result of decomposing the prime factor is p1^α1 * p2^α2 * . . . * pk^αk

The formula derivation is given below , Prove by using the principle of tolerance and exclusion

How to ask for 1 ~ n neutralization n The number of Coprime numbers ？n The result of decomposing the prime factor , That is to say n The only qualitative factor is p1、p2. . .pk

If a number is p1 Multiple , It's also p2 Multiple , Removed twice , But it can only be removed once , So we need to add back the extra one , Add all the pi × pj Multiple , That is, the combination of all two prime numbers ( i and j from 1 ~ k Choose two numbers from the list )

If a number is p1、p2、p3 Multiple , Will be p1 Subtract one time , Re be p2 Subtract one time , Re be p3 Subtract one time , Less 3 Time , Then be p1 × p2 One more time , By p1 × p3 One more time , By p2 × p3 One more time , add 3 Time , It actually needs to be removed

Time complexity analysis

The bottleneck lies in the decomposition of prime factors , The time complexity is O( √ n )

There are altogether n Number , The time complexity is O( n √ ai ),O( 100 × 4 w ) = O( 400 w )

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n --) 
    {
        int a;
        cin >> a;
        // answer 
        int res = a;
        // Decomposing prime factor 
        for(int i = 2;i <= a / i;i++ )
            // If  a  aliquot  i  explain  i  yes  a  The quality factor of 
            if(a % i == 0) 
            {
                // Euler function 
                res = res / i * (i - 1); /* res * (1 - 1 / a) -> res / a * (a - 1) */ 
                while(a % i == 0) a /= i;
            }
        //a There is a big qualitative factor 
        if(a > 1) res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}

Sieve method for Euler function

The last question is to find the Euler function of a certain number , The question is to ask 1 ~ n The Euler function of each number , If you need to decompose each number into prime factors according to the previous question , Time complexity is high O( n √ n ), A method of finding prime numbers using a linear sieve , It can be used O( n ) Calculate the Euler function of each number

number theory --- Simple sieve method 、 Ethmoidal method 、 Linear sieve method _ Xiaoxuecai's blog -CSDN Blog

If a number p Prime number , What is its Euler function ？

The definition of Euler function ： stay 1 ~ p How many numbers are there and p Coprime , obviously 1 ~ p - 1 It's all with p Reciprocal , So a prime number p The Euler function of is p - 1

If i mod pj = 0,primes[ j ] * i What is the Euler function of ?

If i mod pj = 0, explain pj yes i The quality factor of , So I'm asking for φ( i ) In the process of 1 - 1 / pj

In the process of finding Euler function , As long as it contains a prime factor pi, I'm going to take 1 - 1 / pi, It has nothing to do with the number of prime factors , As long as it has appeared, it should be multiplied by 1 - 1 / pi

i All the qualitative factors of are p1 ~ pk,φ( pj × i ) The result of decomposing the prime factor is only φ( i ) Multiply by one more term pj nothing more , because pj yes i The quality factor of , So in φ( i ) The expression of has been multiplied by 1 - 1 / pj,pj × i All the prime factors of are in i In the

 

If i mod pj ≠ 0, explain pj yes i × pj The minimum quality factor of , and pj Not included in i Among the qualitative factors

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

// And may explode int  The time complexity is n^2
typedef long long LL;

int n;

// Store each prime number   Subscript of prime number 
int prime[N], cnt;

//st  Indicates whether each number has been sifted out 
bool st[N];

// Euler function 
int phi[N];

// Find Euler functions 
LL get_eulers(int n)
{
    // Special provisions  φ(1) = 1,1 ~ 1  China and  1  The number of Coprime is only  1 
    phi[1] = 1;  
    // Linear sieve method  i  from  2  Start enumeration 
    for(int i = 2;i <= n;i++ )
    {    
        // If the current number is not filtered   Show the current  i  It's a prime number 
        if(!st[i])        
        {
            primes[cnt ++] = i;
            // If a number is prime   Its Euler function is as follows 
            phi[i] = i - 1;
        }  
        for(int j = 0;primes[j] <= n / i;j++ )
        {
            st[primes[j] * i] = true;
            // In this case  primes[j] * i  What is the Euler function of ?
            if(i % primes[j] == 0) 
            {
                phi[primes[j] * i] = phi[i] * primes[j]; /* primes[j] * phi[i] */
                break;
            }
            //if(i % primes[j] != 0) 
            // Organize into similar forms 
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }    
    // Calculate the sum 
    LL res = 0;
    for(int i = 1;i <= n;i++ ) res += phi[i];
    return res;
} 

int main()
{
    int n;
    cin >> n;
    // seek  1 ~ n  The sum of the Euler functions of each number  
    cout << get_eulers(n) << endl;

    return 0;
}

Euler theorem

Euler theorem _ Baidu Encyclopedia

If it's a positive integer a And n Coprime ( The greatest common divisor is 1), be a^φ( n ) model n more than 1

hypothesis 1 - n All of them and a The number of Coprime is a1、a2 . . . aφ(n), because a and n Coprime , therefore a × a1、a × a2 . . . a × aφ(n) Every number is also a sum n Reciprocal , because a and n Coprime , every last ai And all n Coprime , And this φ(n) Two numbers are different , It is deduced that their numbers are actually the same , It's just in a different order

 

Fermat's small Theorem _ Baidu Encyclopedia

Congruence theorem _ Baidu Encyclopedia

Prove Euler's theorem

a And n Coprime ( The greatest common divisor is 1),3 And 10 Coprime ,7 And 10 Coprime

3^4 be equal to 81, model 10 more than 1,7^4 be equal to 2401, model 10 more than 1

When n It's hard to handle when it's big φ( n ), Then we can use the formula

φ( n ) be equal to n Multiply from 1 To n Between all prime factors p Composed of 1 - 1 / p The product of the

What does this mean ？ Here's an example

First pair 1000 Do prime factor decomposition , That is, the product of prime numbers , be equal to 2^3 × 5^3, So the prime factor is only 2 and 5, That is to say p Can only take 2 and 5

φ(1000) = 1000 × (1 - 1 / 2) × (1 - 1 / 5) = 400

If n It's a prime number p,φ( p ) So what is that equal to ？

Less than prime number p In the positive integer of , Every number is coprime with it , So the total number is p - 1

If it's a positive integer a and p Coprime , that a^p-1 model p more than 1, That is, Fermat's theorem , So in fact, Fermat's theorem is a special case of Euler's theorem

Next, we prove Euler's theorem

Suppose you choose a number n, In less than n The positive integer of n The number of Coprime is φ(n) individual , Write it down as b1、b2、. . . 、bφ( n )

Take another sum n Reciprocal positive integers a, Then multiply by b1、b2、. . . 、bφ( n ), It is clear that these numbers will still be related to n Coprime , Can there be two numbers with the same congruence ？

because n and a It's reciprocal , That is to say n Divisible only bi - bj, bi and bj The range is (1,n - 1), That is to say bi It can only be equal to bj, It's a number , Explain these digital and analog n And then it's different , Or these digital and analog n And then b1、b2、. . . 、bφ( n ) Rearrangement of

Because the numbers on both sides are and n Reciprocal , obtain a^φ( n ) model n more than 1, Prove Euler's theorem

Derivation of Euler function

hold n Decomposing prime factor ,e1 - ek Is the corresponding number of times ,1000 = 2^3 × 5^3, That is to say p1 be equal to 2,p2 be equal to 5

hypothesis n There is only one prime factor , That is to say n = p1^e1,φ(n) In fact, that is 1 ~ n Inside and n The number of Coprime numbers , Think in reverse , and n Non - coprime means the same prime factor , since n There's only one prime factor , So as long as it's p1 The multiples of will be equal to n Not mutual , How many such numbers are there ？ All in all n Number , Just divide the total by p1, You can get p1 How many times are there , These numbers are related to n Not mutual , Include n own , So and n The number of Coprime is n Subtract these numbers , Obviously , It is consistent with φ(n) The form of

Expand the , If at this time n There are two prime factors , So from 1 ~ n Between and n How many coprime numbers are there ？ Same as above , In fact, it is to find out that among these numbers is p1 A multiple of or p2 But some of them are also p1 and p2 Multiple , These numbers were counted twice in the statistics , It needs to be removed once