§ 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 ij , 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 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

p

g

p

g

p

g

p

g

3

5

7 *

11

13

17 *

19 *

23 *

29 *

31

37

41

43

47 *

53

59 *

61 *

67

71

73

79

83

89

97 *

101

103

107

109 *

113 *

127

131 *

137

139

149 *

151

157

163

167 *

173

179 *

181 *

191

193 *

197

199

211

223 *

227

229 *

233 *

239

241

 

2

2

3

2

2

3

2

5

2

3

2

6

3

5

2

2

2

2

7

5

3

2

3

5

2

5

2

6

3

3

2

3

2

2

6

5

2

5

2

2

2

19

5

2

3

2

3

2

6

3

7

7

 

251

257 *

263 *

269 *

271

277

281

283

293

307

311

313 *

317

331

337 *

347

349

353

359

367 *

373

379 *

383 *

389 *

397

401

409

419 *

421

431

433 *

439

443

449

457

461 *

463

467

479

487 *

491 *

499 *

503 *

509 *

521

523

541 *

547

557

563

569

571 *

 

6

3

5

2

6

5

3

3

2

5

17

10

2

3

10

2

2

3

7

6

2

2

5

2

5

3

twenty one

2

2

7

5

15

2

3

13

2

3

2

13

3

2

7

5

2

3

2

2

2

2

2

3

3

 

577 *

587

593 *

599

601

607

613

617

619 *

631

641

643

647 *

653

659 *

661

673

677

683

691

701 *

709 *

719

727 *

733

739

743 *

751

757

761

769

773

787

797

809

811 *

821 *

823 *

827

829

839

853

857 *

859

863 *

877

881

883

887 *

907

911

919

 

5

2

3

7

7

3

2

3

2

3

3

11

5

2

2

2

5

2

5

3

2

2

11

5

6

3

5

3

2

6

11

2

2

2

3

3

2

3

2

2

11

2

3

2

5

2

3

2

5

2

17

7

 

929

937 *

941 *

947

953 *

967

971 *

977 *

983 *

991

997

1009

1013

1019 *

1021 *

1031

1033 *

1039

1049

1051 *

1061

1063 *

1069 *

1087 *

1091 *

1093

1097 *

1103 *

1109 *

1117

1123

1129

1151

1153 *

1163

1171 *

1181 *

1187

1193 *

1201

1213 *

1217 *

1223 *

1229 *

1231

1237

1249

1259 *

1277

1279

1283

1289

 

3

5

2

2

3

5

6

3

5

6

7

11

3

2

10

14

5

3

3

7

2

3

6

3

2

5

3

5

2

2

2

11

17

5

5

2

7

2

3

11

2

3

5

2

3

2

7

2

2

3

2

6

 

 

p

g

p

g

p

g

p

g

1291 *

1297 *

1301 *

1303 *

1307

1319

1321

1327 *

1361

1367 *

1373

1381 *

1399

1409

1423

1427

1429 *

1433 *

1439

1447 *

1451

1453

1459

1471

1481

1483

1487 *

1489

1493

1499

1511

1523

1531 *

1543 *

1549 *

1553 *

1559

1567 *

1571 *

1579 *

1583 *

1597

1601

1607 *

1609

1613

1619 *

1621 *

1627

1637

1657

1663 *

p

2

10

2

6

2

13

13

3

3

5

2

2

13

3

3

2

6

3

7

3

2

2

5

6

3

2

5

14

2

2

11

2

2

5

2

3

19

3

2

3

5

11

3

5

7

3

2

2

3

2

11

3

g

1667

1669

1693

1697 *

1699

1709 *

1721

1723

1733

1741 *

1747

1753

1759

1777 *

1783 *

1787

1789 *

1801

1811 *

1823 *

1831

1847 *

1861 *

1867

1871

1873 *

1877

1879

1889

1901

1907

1913 *

1931

1933

1949 *

1951

1973

1979 *

1987

1993 *

1997

1999

2003

2011

2017 *

2027

2029 *

2039

2053

2063 *

2069 *

2081

p

2

2

2

3

3

3

3

3

2

2

2

7

6

5

10

2

6

11

6

5

3

5

2

2

14

10

2

6

3

2

2

3

2

5

2

3

2

2

2

5

2

3

5

3

5

2

2

7

2

5

2

3

g

2083

2087

2089

2099 *

2111

2113 *

2129

2131

2137 *

2141 *

2143 *

2153 *

2161

2179 *

2203

2207 *

2213

2221 *

2237

2239

2243

2251 *

2267

2269 *

2273 *

2281

2287

2293

2297 *

2309 *

2311

2333

2339 *

2341 *

2347

2351

2357

2371 *

2377

2381

2383 *

2389 *

2393

2399

2411 *

2417 *

2423 *

2437 *

2441

2447 *

2459 *

2467

p

2

5

7

2

7

5

3

2

10

2

3

3

twenty three

7

5

5

2

2

2

3

2

7

2

2

3

7

19

2

5

2

3

2

2

7

3

13

2

2

5

3

5

2

3

11

6

3

5

2

6

5

2

2

g

2473 *

2477

2503

2521

2531

2539 *

2543 *

2549 *

2551

2557

2579 *

2591

2593 *

2609

2617 *

2621 *

2633 *

2647

2657 *

2659

2663 *

2671

2677

2683

2687 *

2689

2693

2699 *

2707

2711

2713 *

2719

2729 *

2731

2741 *

2749

2753 *

2767 *

2777 *

2789 *

2791

2797

2801

2803

2819 *

2833 *

2837

2843

2851 *

2857

2861 *

2879

p

5

2

3

17

2

2

5

2

6

2

2

7

7

3

5

2

3

3

3

2

5

7

2

2

5

19

2

2

2

7

5

3

3

3

2

6

3

3

3

2

6

2

3

2

2

5

2

2

2

11

2

7

g

2887

2897 *

2903 *

2909 *

2917

2927 *

2939 *

2953

2957

2963

2969

2971 *

2999

3001

3011 *

3019 *

3023 *

3037

3041

3049

3061

3067

3079

3083

3089

3109

3119

3121

3137 *

3163

3167 *

3169

3181

3187

3191

3203

3209

3217

3221 *

3229

3251 *

3253

3257 *

3259 *

3271

3299 *

3301 *

3307

3313 *

3319

3323

3329

3331 *

p

5

3

5

2

5

5

2

13

2

2

3

10

17

14

2

2

5

2

3

11

6

2

6

2

3

6

7

7

3

3

5

7

7

2

11

2

3

5

10

6

6

2

3

3

3

2

6

2

10

6

2

3

3

g

3343 *

3347

3359

3361

3371 *

3373

3389 *

3391

3407 *

3413

3433 *

3449

3457

3461 *

3463 *

3467

3469 *

3491

3499

3511

3517

3527 *

3529

3533

3539 *

3541

3547

3557

3559

3571 *

3581 *

3583

3593 *

3607 *

3613

3617 *

3623 *

3631

3637

3643

3659 *

3671

3673 *

3677

3691

3697

3701 *

3709 *

3719

3727 *

3733

3739

3761

p

5

2

11

twenty two

2

5

3

3

5

2

5

3

7

2

3

2

2

2

2

7

2

5

17

2

2

7

2

2

3

2

2

3

3

5

2

3

5

twenty one

2

2

2

13

5

2

2

5

2

2

7

3

2

7

3

g

3767

3769

3779 *

3793

3797

3803

3821 *

3823

3833 *

3847 *

3851 *

3853

3863 *

3877

3881

3889

3907

3911

3917

3919

3923

3929

3931

3943 *

3947

3967 *

3989 *

4001

4003

4007 *

4013

4019 *

4021

4027

4049

4051 *

4057 *

4073 *

4079

4091 *

4093

4099

4111

4127

4129

4133

4139 *

4153 *

4157

4159

4177 *

4201

4211 *

p

5

7

2

5

2

2

3

3

3

5

2

2

5

2

13

11

2

13

2

3

2

3

2

3

2

6

2

3

2

5

2

2

2

3

3

10

5

3

11

2

2

2

17

5

13

2

2

5

2

3

5

11

6

g

4217 *

4219 *

4229 *

4231

4241

4243

4253

4259 *

4261 *

4271

4273

4283

4289

4297

4327 *

4337 *

4339 *

4349 *

4357

4363

4373

4391

4397

4409

4421 *

4423 *

4441

4447 *

4451 *

4457 *

4463 *

4481

4483

4493

4507

4513

4517

4519

4523

4547

4549

4561

4567 *

4583 *

4591

4597

4603

4621

4637

4639

4643

4649

4651 *

p

3

2

2

3

3

2

2

2

2

7

5

2

3

5

3

3

10

2

2

2

2

14

2

3

3

3

twenty one

3

2

3

5

3

2

2

2

7

2

3

5

2

6

11

3

5

11

5

2

2

2

3

5

3

3

g

4657

4663

4673 *

4679

4691 *

4703 *

4721

4723

4729

4733

15

3

3

11

2

5

6

2

17

5

4751

4759

4783 *

4787

4789

4793 *

4799

4801

4813

4817 *

19

3

6

2

2

3

7

7

2

3

4831

4861

4871

4877

4889

4903

4909

4919

4931 *

4933

3

11

11

2

3

3

6

13

6

2

4937 *

4943 *

4951

4957

4967 *

4969

4973

4987

4993

4999

3

7

6

2

5

11

2

2

5

3

 

 



* Foreign books and periodicals call Sun Tzu's theorem the Chinese remainder theorem. In ancient my country, the solution to this kind of problem has been described in the question "I don't know how many things" in "Sun Tzu's Suanjing".

Original text