§ 3 Congruence 

 

    [ Congruence and its properties ]   Let m be a natural number , if the difference ab between integers a and b is a multiple of m , then a and b are said to be congruential modulo m , denoted as

    (mod m )

Otherwise record as

   (mod m )

Indicates that a and b are not congruent modulo m .

    Congruence has the following properties :

    1 ° (mod m ) ( reflexive )                                

    2 ° If (mod m ), then (mod m ) ( symmetry )                

    3 ° If , (mod m ), then (mod m ) ( transitive )           

    4 ° If , (mod m ), then 

          (mod m )

          (mod m )

             (mod m )

    5 ° If , (mod m ), and , then (mod m ). 

    [ Complete Residual System and Reduced Residual System ]   Let m be the modulus , then by the congruence properties 1 ° , 2 ° , 3 ° , all integers can be divided into m classes , the numbers of the same class are congruent , and the numbers of different classes are different We call such a class a congruence class , and each class is represented by a number , for example

form a complete residual system .

    Take a representative from the classes that are relatively prime to m

Constitute a reduced residual system ( referred to as a reduced system ), where j ( m) is the number of numbers that do not exceed m and are relatively prime to m ( called the Euler function ).

    The residual system has the following properties :

    1 ° If x passes through a complete residual system of m , and passes through a complete residual system , then passes through a complete residual system . 

    2 ° If x passes through m in a constricted system , and over a condensed line , then over a condensed line . 

    If 3 ° is a contraction system of the modulus m , and ( k, m )=1, then 

          

is also a shortened system of m

    [ Eulerian theorem ]   If ( k, m )=1, then

(mod m )

where j (m) is the Euler function .

    [ Fermat's theorem ]   If p is prime , then for all integers a , we have

(mod p )

    Obviously Fermat's theorem is a special case of Euler's theorem .

    [ Conditions for Solvability of First-order Congruence Equations ]   Congruence Equations

(mod m )

The necessary and sufficient conditions for a solution are :

                            

When this condition is satisfied , the number of solutions ( different remainders to modulo m ) is

                            

    [ Solving method of first-order congruential equation in one variable ]   First- order congruential equation in one variable

           (mod m )                                  (1)

The necessary and sufficient conditions for a solution are : , if there is a solution, there are ( a , m ) mutually different complementary solutions , mod m . The solution is as follows :

    Set ( a , m ) = d , , then the original equation (1) can be transformed into

Referred to as

                                     (2)

    First determined by rolling division ( see § 1), such that

but

is the solution of the congruence equation (2) , and finally we get

x=x'+m't , t=

is the solution of the original equation (1) , mod m . That is, there are d solutions

Not congruent modulo m .

    [ Sun Tzu's Theorem * ] If i ≠ j , then the system of congruence equations

                                         (3)

There is a unique solution , .

    The solution of the system of congruence equations (3) is as follows :

    Because , so it can be obtained by the tossing and dividing method , satisfying

    remember

then

    final calculation

It is the only solution to the system of congruence equations (3) , .

    [ Quadratic residual and quadratic non-residual ]   Let m be an integer greater than 1 , ( n , m )=1, if

  (mod m )

solvable , then n is called the quadratic residue modulo m , or quadratic residue , mod m . Otherwise , n is called the quadratic non-residue modulo m .

    The product of two quadratic residues is still quadratic residue , mod p.

    The product of two quadratic non-residues is the quadratic residue , mod p.

    The product of a quadratic residual and a quadratic non-residual is a quadratic non-residue , mod p.

    Let p be an odd prime , then in the reduced residual system modulo p , there is a quadratic residual :

There is a quadratic non-residue , mod p .

    [ Legendre symbols and their properties ]   Let p be an odd prime number , and p n also set

It is called Legendre notation .

    Legendre symbols have the following properties :

    1 ° if (mod p ), p n then 

=

    2 ° Eulerian criterion : Let p be an odd prime number , then 

 (mod p )

    3 ° If ​​p is an odd prime number , p mn , then 

    4 ° If p is an odd prime number , then 

    5 ° If p is an odd prime number , then 

    6 ° Gaussian reciprocity law : Let p, q be two different odd prime numbers , then 

    [ Number of solutions of quadratic congruence ]   Let l > 0, p n , if p is an odd prime number, then the quadratic congruence

  (mod )

The solution of .

    When p = 2 , there is a solution when l = 1 .

                        

    [ Number of times modulo m ] Let h be an integer , ( m , h )=1, satisfying 

(mod m )

The smallest positive integer l of is called the degree of h to modulo m , or the degree of h , mod m .

    If (mod m ), then , where l is the number of h , mod m

    [ Primitive roots and exponents of prime modulo ]   Let p be a prime number , and the number whose degree is p - 1 is called the primordial root modulo p .

    Let g be a primitive root modulo p , then

The two are not complementary to each other .

    For any integer n ( p n ), there must be a number a such that

  (mod p )   ,

This a is called the exponent of n , mod p . It is written as

                               

When it is not easy to be confused , abbreviated ind n .

    The index has the following properties :

    1 ° if b is satisfied 

                               (mod p )

any number of , then

                             (mod p - 1)

    2 ° (mod p - 1), p ab 

    3 ° (mod p - 1), p a  

    4 ° The base interchange formula is set as two unequal primitive roots of mod p , and (mod p ), then 

(mod p - 1)

    [ Original root modulo m ] Let m be a natural number , if there is a number g such that 

                           (mod m )

If the two are not complementary to each other , then this g is called the primitive root of the modulo m, and the necessary and sufficient conditions for the existence of the primitive root of the modulo m are :

( p is an odd prime number , l is a positive integer )

[ List of prime numbers and their smallest primitive roots ( within 5000 )] The one with * means 10 is its primitive root