Congruence theorem
I. Congruence:
For the problem of dividing an integer by some positive integer, if only the remainder is concerned, the concept of congruence arises.
Definition 1 Divide the integers a and b by the given positive integer m, and if the resulting remainder is equal, it is called the congruence of a and b to module m, denoted as a≡b(mod m), such as 56≡0 (mod 8).
Theorem 1 The congruence of integers a,b to module m is necessary and sufficient if a-b is divisible by m (i.e. m|a-b).
If a≡b(mod m), r1=r2 by definition 1, then a-b=m(q1 q2), that is, m|a-b.
Conversely, if m|a-b, that is, m|m(q1-a2) r1-r2, then m|r1-r2, but |r1-r2|< m, so r1=r2, i.e. a≡b(mod m).
inference a≡b(mod m) is necessary and sufficient if a=mt b(t is an integer).
The expression of the congruence relation to the module m is called the congruence of the module m, and the notation of the congruence is first used by Gauss in 1801.
Theorem 2 The congruence relation has reflexivity, symmetry and transitivity, that is
1)a≡a (mod m);
2)a≡b (mod m), b≡a (mod m);
Theorem 3 If a≡b(mod m), c≡d (mod m), then
1)a c≡b d(对m取模);
2)a-c≡b-d(对m取模);
3)ac≡bd (mod m).
More than two congruential formulas can also be added, subtracted and multiplied.
There are also the following corollaries to multiplication:
inference If a≡b(mod m) and n is a natural number, then an≡bn (mod m).
Theorem 4; If ca≡cb(mod m), (c,m)=d and a and b are integers, then a≡b(mod m\/d).
inference If ca=cb(mod m), (c,m)=1, and a and b are integers, then a≡b(mod m).
Theorem 5. If a≡b(mod m),a≡b (mod n), then a≡b(mod [m,n]).
inference If a≡b(mod mi), i=1,2,... ,n, then a≡b (mod [m1,m2,..,mn]).
Example: known 23 ^ nbsp; ≡ 1(mod 7), then 22005 ≡ 23*668 1 ≡ (23)668*2 ≡ 2(mod 7) (Theorem 3 is used for this calculation)
Certificate: 23 ≡ 1(mod 7), from law 5, gives 23. * 23 ≡ 1*1(mod 7)… (23)668 ≡ 1(mod 7),
,,,,, 故，(23)668*2≡2(mod 7)。
Algorithm application:
1. Mod puts :ab mod n = (a mod n)(b mod n) mod n
1 \/ \/ 2。A *b%c 2 int mul_mod(int A, int b, int c) 3 {4 int r = 1, d = A;* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *9 d = (d*d)%c;10 b >>= 1;11} 12返回r;13}
2. Large integer modulus:
1 \/\/大整数取模n%m 2 int big_mod(char n[]， int m) 3 {4 int len = strlen(n);5长长ans=0;6 for(int i=0;i<兰;我7 ans) =((很久)答* 10 n[我]& # 39;0 & # 39;)% m;8返回(int)ans;9}
,
3. Power modeling
1 \/ \/ 1。根据定义2 int pow_mod(int a, int n, int m) 3 {4 long long ans=1;5 for(int i=0;i< n;1) 6 ans = (long long)ans*n%m 7返回ans;8}
1 \/\/2. Daca daca daca daca daca daca daca daca daca daca daca daca daca daca daca 6 int x = pow_mod(a, n\/2, m); 7 long long years = (long long)x*x%m; If (n%2 == 1) 9 years = years *a%m; 10 return (int) years; 11}
Definition 2 If m is a natural number, the set Kr={x|x=mt r,t is any integer}, r=0,1,... m, then K0,K1,... Km-1 is the residual class of module m.
For example, the remaining classes of module 2 are the even and odd classes; The remaining classes of module 3 are :K0={... - 6, 3,0,3,6,... }, K1={... , - 5-2,1,4,7,... }, K2={... - 4-1,2,5,8... }.
The remaining classes have the following obvious properties:
1) Residual classes of module m K0, K1,...... Km-1 is a nonempty subset of integers;
2) Each integer must belong to one and only one remaining class;
3) The necessary and sufficient condition for two integers to belong to the same residual class is that they are congruent to the module m.
Definition 3 Take any number from each residual class of a module m, and the resulting number of m is called the complete residual system of a module m.
For a module m, there are many complete residual systems, often using:
0, 1, 2,…,m - 1;
1、2、3、…、m;
-(m-1)\/2,… , 1, 1,... ,m\/2 (m is odd),
-m\/2 1,… , 1, 1,... ,m\/2 (m is an even number),
-m\/2,… , 1, 1,... ,m\/2-1 (m is an even number).
Theorem 6. k integers a1,a2,... The necessary and sufficient condition for ak to form a complete residual system of a module m is that k=m, and the m number is not complementary to the module m in pairs.
Theorem 7 If x1,x2,... xm is a complete residual system of the module m, (a,m) =1 and b is an integer, then ax1 b, ax2 b,... axm b is also a complete residual system of the module m.
,
2. , Euler function
Definition 1 In a complete residue system of a module m, all numbers that are coprime to m are called reduced residue systems of the module m. For example, 1,3,7,9 is a simplified residual system of module 10.
Definition 2 For any natural number m, Phi (m) is used to represent 0,1,2,... Phi (m) is the Euler function for the number of coprime with m in m-1.
For example Phi (10)=4, Phi (7)=6, Phi (1)=1.
Theorem 1 k integers a1,a2,... The sufficient and necessary conditions for ak to form a simplified residual system of module m are k= Phi (m), (ai,m)=1,i=1,2,... Phi (m), and the Phi (m) number is not congruent to the modulus m.
Theorem 2 If (a,m)=1, x1,x2... x Phi (m) is a reduced residual system of the module m, then ax1,ax2,... ax Phi (m) is also a reduced residual system of the module m.
Theorem 3 (Euler's Theorem) If (a,m)=1, then a phi (m) ≡1 (mod m)
Certificate: Let x1,x2,... x Phi (m) is a reduced residual system of the module m, according to theorem 2, ax1,ax2,... ax Phi (m) is also a reduced residual system of the module m.
So we know that x1,x2,... x Phi (m) in any number must be ax1,ax2,... , congruence of a certain number in ax Phi (m) to the modulus m;
And conversely ax1,ax2... Any number in ax Phi (m) must be equal to x1,x2... A certain number in x Phi (m) is congruent to the module m, which is:
ax1ax2… Ax ф (m) ≡ x1x2... X ф (m) & have spent (mod m), again (x1x2... x phi (m),m)=1, so a phi (m) ≡1 (mod m).
Example 1. Given that x=h is the smallest positive integer that holds ax≡1 (mod m), verify h| phi (m).
From the proof that ah-1=mt(t is an integer) we can see that (a,m)=1, thus
A glance (m) &ncsp; transf1 (mod m).
Phi (m)=hq r,0< =r< h and q are natural numbers
By substituting the above congruence, ar ≡1 (mod m), so r=0, so h| phi (m).
Inference (Fermat's little theorem) If p is prime, then. 1) When (a,p)=1, ap-1 ≡1 (mod p);
2) AP ≡A (mod P)
Proof: First proof 1), by p is prime, know 0,1,2,... There are p-1 numbers in p-1 and p reciprocity, so Phi (p)=p-1. And since (a,p)=1, theorem 3 proves 1).
Reproof 2), when (a,p)=1, it is established that 1) knows 2); When (a,p) is not equal to 1,p |a, and the remainder is both 0,2) is also true.
Euler proved Theorem 3 in 1760, so it is called Euler's theorem. Fermat proposed the above inference in 1640, and its proof was completed by Euler in 1736, and this inference is often called Fermat's little theorem.
Example 2. Let a be an integer and verify that a5≡a(mod 30).
Proof since 30=2.3.5, and according to Fermat's little theorem, there is
A5 transfa (mod 5) (1)
A3≡a(mod 3) (2)
A2≡A(mod 2) (3)
(2) gives a5≡a3≡a(mod 3) (4)
(3) gives a5≡a4≡a2≡a(mod 2) (5)
So (1).(4),(5), and 2,3,5 are pairwise prime, so a5≡a(mod 30).
Theorem 4; If p is prime, Phi (pa)=pa-pa-1. (Phi (pa) formula)
Prove that the complete residual system of module pa is considered 0,1,2,... ,p,… ,2p,… ,pa-1 (1)
The only numbers that are not prime to pa in the formula (1) are multiples of p 0,p,2p,... Pa-1-1 p, this is p a- one,
So the number of mutual primes with pa in (1) is pa-p a minus 1, so phi (pa)=pa-pa-1.
Theorem 5. If (m,n)=1, Phi (mn)= Phi (m) phi (n).
inference If the positive integers m1,m2,... mk pairwise prime phi (m1m2... Mk) = ф ф (m1) (m2)... ф (mk).
Theorem 6. If the standard factorization of m is m=p1a1p2a2... pkak, Phi (m)=p1a1-1p2a2-1... pkak-1(p1-1)(p2-1)… (pk-1).
Example 3. Let (n,10)=1 and verify that n101 is the same as the last three digits of n.
Proof: To prove n101-n≡0 just prove n100≡1(mod 1000).
In fact by (n, 125) = 1, from (125) = (5 ^ 3) = 5 ^ ^ 2 = 3-5, 100, has n100 ≡ 1 (mod) 125;
If n is odd, we know that 8|n^2-1, n^100≡1(mod 8), and (125,8)=1.
Algorithm:
1. Solve φ(n)
,
1 \/\/ Directly solve the euler function 2 int phi(int n) 3 {4 \/\/ Return euler(n) 5 int res=n,a=n; 6 for(int i=2; i*i< =a; i ) 7 { 8 if(a%i==0) 9 { 10 res=res\/i*(i-1); \/\/ Division is performed first to prevent overflow of intermediate data. 11 while(a%i==0) a\/=i; 12 } 13 } 14 if(a> 1) 15 res=res\/a*(a-1); 16 return res; 17}
Filter euler function table #define Max 1000001 int euler[Max]; void Init() { for(int i=1; i< Max; i ) euler[i]=i; for(int i=2; i< Max; i ) if(euler[i]==i) for(int j=i; j< Max; j =i) euler[j]=euler[j]\/i*(i-1); \/\/ Division is performed first to prevent overflow of intermediate data}
If the object has x, it can be obtained
x≡2(mod 3);
X ≡3(mod 5);
x≡2 (mode 7).
Let's look at the general solution of the first congruence equation.
[formula]
[formula]
…
[formula]
First let
formulate
Minimize [formula]{[formula]}
Find [the formula] and substitute the following formula:
[formula]
I can find the minimum value of x
So back to the question
< br >
If the object has x, it can be obtained
x≡2(mod 3);
X ≡3(mod 5);
x≡2 (mode 7).
< br >
m = 3 * 5 * 7 = 105
< br >
[Formula] = 105, [formula] = 105, [formula] = 105
[Formula] =35, [formula] =21, [formula] =15
< br >
[formula], [formula] {minimum}
[formula], [formula]
[formula], [formula]
finally
[formula]
[formula]
[formula]
If we do this, we get the minimum value of x is 23, and we're done.
test
23[formula]3=7...... Two out of three is two
23[Formula]5=4...... Three out of five
23[formula]7=3...... Two of the seventy-seven are left
New hair
Congruence theory is often used in number theory. The first person to cite the concept and symbol of congruence was the German mathematician Gauss. Congruence theory is an important part of elementary number theory and one of the important tools to study integer problems. It is very simple to prove some divisible problems by using congruence theory. Congruence is an important part of mathematics competition.
Definition of the congruence theorem:
< br \/ >
Two integers a and b are said to be congruent to the module m if they simultaneously obtain the same remainder from a natural number m. Call it a≡b (mod m). Read as: a congruence to b module m. Here \"≡\" is the congruence symbol.
< br \/ >
2. Some properties of the congruence theorem:
< br \/ >
For the same divisor, the sum (or difference) of two numbers is congruent with the sum (or difference) of their remainder. (same with addition, subtraction and multiplication)
(a b)%c==(a%c b%c)%c
< br \/ >
For the same divisor, if there are two integers congruence, then their difference must be divisible by the divisor.
For the same divisor, if two numbers are congruent, then their powers are still congruent.