<h1 class="pgc-h-arrow-right" > Euclidean algorithm (tossing division</h1>).
Euclidean's algorithm, also known as tossional division, is mainly used to calculate the greatest common divisor of two integers a and b.
To put it simply, the principle of the algorithm: the greatest common divisor of two integers is equal to the small one and the large divided by the larger remainder of the greatest common divisor.
即： gcd(a,b)=gcd(b,a mod b) 。
Here's a simple example:
For example, find the greatest common divisor of 10 and 24:
a = gcd(10, 24):
1. The greatest common divisor of 10 and 24 is equal to the greatest common divisor of 10 and 4:
a = gcd(10, 24) = gcd(10, 4)
2. The greatest common divisor of 10 and 4 is equal to the greatest common divisor of 4 and 2, which is 2:
= gcd(4, 2) = 2
<h1 class="pgc-h-arrow-right" > extend Euclidean algorithm</h1>
Algorithm principle: if a and b are positive integers, there is an integer x, y such that gcd(a,b) = ax+by;
In layman's terms, gcd(a,b) can be expressed as a linear combination of integers a and b.
gcd(10, 24) = 2
2 = 10*(-7) + 24*3
The main applications are as follows:
1. Solve indefinite equations;
2. Solve the inverse of the module (multiplying inverse), with reference to the congruent equation, Euler's function, multiplying inverse, and the matrix defined on Zm
3. Solve the modular linear equation (linear congruence equation);
1). Solve the common residual equation ax ≡ b (mod m), x = ?
2). Solving the System of Homojunctive Equations Continue looking down at the Chinese residual theorem
< h1 class= "pgc-h-arrow-right" > The Chinese residual theorem</h1>
There is a question in the Sun Tzu Arithmetic: "Now there are things whose number is unknown, and two of the three numbers are left (divided by 3 for 2),
The remaining three of the five-five number (divided by 5 more than 3), the remaining two of the seven-seven number (divided by 7 more than 2), the question is geometric? ”
The Song Dynasty mathematician Qin Jiushao made a complete and systematic solution to the problem of "unknown numbers" in 1247 in the Nine Chapters of the Book of Numbers, Volume I and II, "Great Yan Class". The Ming Dynasty mathematician Cheng Dawei compiled the solution into an easy-to-catch "Sun Tzu Song Recipe":
Three people walking together seventy rare,
Fifty-one plum blossoms,
Seven sons reunion half moon,
Except for one hundred and five, we know.
This means that as long as it is divided by 3 and a 1, it adds a 70;
As long as it is divided by 5 and a 1, add a 21;
Just divide by 7 and add a 1. Then add up.
Finally, the sum is calculated divided by the remainder of 105.
That is, (2×70 + 3×21 + 15×2 ) mod 105 = 23
The solution is as follows:
First, from the common multiples of 3 and 5, 3 and 7, 5 and 7, find the smaller numbers 15, 21, and 70 divided by the average remainder 1 of 7, 5, and 3 respectively (this step is also called the "modulo inverse" operation, referring to the multiplicative inverse solution). namely:
15÷7=2...... Yu1,
21÷5=4...... Yu1,
70÷3=23...... Yu 1.
Then multiply the three smaller numbers found by multiplying the required numbers by the product of the remainder divided by 7, 5, and 3, respectively,
15×2+21×3+70×2=233.
Finally, divide the sum by 233 and divide the three smallest common multiples of the three divisors of 3, 5, and 7.
233÷105=2...... Yu23,
This remainder 23 is the minimum number that qualifies.
Expand to the general situation:
Assuming that the integers m1, m2, ... , mn are mutually identical, then for arbitrary integers: a1, a2, ... , an system of equations:
Both have integer solutions, and if both X and Y satisfy the system of equations, there must be X ≡ Y (mod N) where:
The formula is as follows:
The formula symbols in the textbook really don't want to see, so let's take the homework to give two examples.
<h1 class="pgc-h-arrow-right" > job 1:</h1>
Solve the system of congruent equations:
x ≡ 12 (vs. 25)
x ≡ 9 (vs. 26)
x ≡ 23 (vs. 27)
The above system of equations is equivalent to x = 25a + 12 = 26b + 9 = 27c + 23
Shift the next item to get:
① : 25a - 27c = 23-12 = 11
②: 26b - 25a = 12-9 = 3
First of all, the use of (1) expands Euclid:
27 = 25×1 + 2
25 = 2×7 + 11
rule:
11 = 25 - 2×7
= 25 - (27-25) ×7
= 25×8 - 27×7
So a=8, c=7
Substitution x = 25a + 12 = 27c + 23 gets:
x = 212
Get the merging equation x = 212 + 25 × 27t i.e. x ≡ 212 (mod 675)
Then merge with x ≡ 9 (mod 26).
x = 212 + 675t = 26b + 9
26b - 675t = 203
675 = 26×25+25
25 = 25×1
So:
203 = (26-25)×203
= (26 - (675-26*25))×203
= 26×5278 - 675×203
b=5278 , t=203
Substitution is x = 137237
The combined equation x = 137237 + 25 × 27×26t i.e. x ≡ 137237 (mod 17550), x = 14387
x = 14387 + 17550n (n∈Z)
<h1 class="pgc-h-arrow-right" > job 2:</h1>
Solve the following system of congruent equations:
13x ≡ 4 (vs. 99)
15x ≡ 56 (vs. 101)
This kind of system of coherent equations with coefficients is head-scratching, but it does not prevent the use of extended Euclid,
First remove the coefficients:
x ≡ 46 (vs. 99)
x ≡ 98 (vs. 101)
Eliminate x to: 99a - 101b = 52
Extend Euclid Walk You: x = 7471 (mod 9999)
x = 9999 n + 7471 (n ∈ Z)