It is proved that if A is coprime with 10, then the power of A is congruent with module A 1000, n=0, 1, 2…
Certificate:
The Euler function value of 125 is 100.
The Euler function of 8 is 4.
(standby:
The Euler function value of 10 is φ( 10)= 4.
The Euler function value of 1000 is 400.
)
Based on the property theorem of Euler function (I call it reduced residual counting function or reduced system counting function, see the note below),
When a and 10 are coprime, that is, a and 8 are coprime, and a and 125 are coprime, that is,
A 4 = = 1mod8, so a 100 = = 1mod8.
a^ 100== 1 mod 125
So it is obvious: (you can see it without China's remainder theorem)
A100 =1module 8* 125 = 1 module 1000.
Therefore, a (100n+1) = = amod1000.
BBB number theory terminology reference:
Double equal sign = =
It is introduced for the convenience of typing to replace the three-line equal sign ≦, which can be used as a symbol of congruence.
The greatest common divisor gcd(a, m), sometimes abbreviated as (a, m):
The greatest common divisor, greatest common factor and greatest common divisor of A and M. In order to avoid confusion, some materials are written in gcd(a, m) or gcf(a, m), and the English text is great common divisor or great common factor.
Convention ⊥,a⊥m, a and m are conventions, irreducible, mutual quality, mutual quality:
Irreducible, irreducible, or coprime, or coprime, A and M are irreducible, that is, the greatest common divisor of A and M is 1, and the common factor is irreducible.
Residual class, congruence class:
The set {a+mk, k is an arbitrary integer} is called the A-class residue class of M, in which every element is congruent to the module M and is equivalent in the sense of congruence, so it is also called the congruence class. At the same time, any element can be the representative of all elements, and any element is called the representative element, representative number or representative of the remaining class.
Reduced residue class, irreducible residue class, prime residue class:
The set {a+mk, k is an arbitrary integer, and a and m are coprime} is called the class A reduced residue class, irreducible prime residue class or prime residue class of m.
Reduced residue system, prime residue system, simplified residue system, simplified residue system, simplified system, simplified system Z (m);
A series of residual classes represented by the sum of positive integers not greater than m and m coprime are a special set (series set).
Simplify the representative set of the residual system
A set of representative elements is extracted from each residual class of the reduced residual system.
It is particularly important to note that in the sense of congruence (congruence equivalence), a residue system is represented by one of the representative numbers. At this time, there is no need to distinguish between the representative set of the reduced residual system and the reduced residual system.
Minimum reduced residual representative set z (m);
A set of positive integers not greater than m and coprime with m.
φ(m), Euler function, I call it reduced residual counting function of m, or prime residual counting function of m, or contraction counting function of m.
Is the count of the number of positive integers that are not greater than m and are coprime with m, which I call the reduced residual counting function of m, or the prime residual counting function of m, or the contraction counting function of m. As Euler is a great mathematician and physicist, there are too many names named after Euler function and euler theorem, so it is not confusing to give a specific name.