Article From:https://www.cnblogs.com/Linke-din/p/9062490.html

concept

       Congruence definition: there are two integers $a, b$, if they are divided by integer $m$, the remainder is equal, then it is called a and B for module $m$congruence or $a$congruence in $b$mode $m$.

Note: $a\equiv B \pmod{m}$

To put it simply, for two numbers $a, b$, $a\div m=x\ldots r$, $b\div m=y\ldots r$, the remainder of the two expressions is the same, so that $a$and $b$are related to the modulus $m$congruence. For example, $34\div 7=4\ldots 6$, $20\div 7=2\ldots, 6$, 34 and 20, divided by 7, have the same remainder, 6, 34 and 20 about module 7 congruence. It’s very simple.

The following is used: $(a, b) $, which represents the greatest common divisor of $a$and $b$, and can also be expressed as $gcd (a, b) $. Similarly, $[a, b]$represent the least common multiple of $a$and $b$, and can also be expressed as $lcm (a, b) $.

Ten properties of congruence

  1. If $b\equiv $a\equiv B \pmod{m}$, then $b\equiv a \pmod{m}$
  2. If $a\equiv B \pmod{m}$\pmod{m}$, $b\equiv C \pmod{m}$, $a\equiv C \pmod{m}$
  3. If $a_1\equiv b_1 \pmod{m}$\pmod{m}$, $a_2\equiv b_2 \pmod{m}$, $a_1+a_2\equiv b_1+b_2 \pmod{m}$
  4. If $a\equiv $a+b\equiv C \pmod{m}$, then $a\equiv C-B \pmod{m}$\pmod{m}$.
  5. If $a\equiv, B, \pmod{m}$, and $a=a_1d$, $b=b_1d$, $(D, m) $=1, then $a_1\equiv b_1 \pmod{m}\\$\pmod{m}\\$.What is the proof? It is known that $a-b\equiv 0, \pmod{m}$, $a_1d-b_1d\equiv 0, \pmOd{m}$, then $d (a_1-b_1) \equiv 0, \pmod{m}$, $m\mid D (a_1d-b_1) $So $m\mid a_1d-b_1$
  6. If $a\equiv, B, \pmod{m}$, $k&gt, 0$, $ak\equiv BK \pmod{mk}$
  7. If $a\equiv B \pmod{m}$, $d$is any integer of $a, b$and $m$, $\frac{a}{b}\equiv \frac{b}{d} \pmod{\frac{m}{d}} $
  8. If $a\equiv, B, \pmod{mi}$, $i=1,2\ldots k$, $a\equiv B, \pmod{[m_1, m_2\ldots m_k]}$
  9. If $a\equiv, B, \pmod{m}$, $d\mid m$, $d&gt, 0$, $a\equiv B
  10. If $a\equiv, B, \pmod{m}$, then $(a, m) = (B, m) $, if $d\mid m$and $a, b$double, then $a, another.

 application

There are several types of congruences, such as whether a proof can be divisible, the remainder and the last number, and the indefinite equation.

Look at some of the classic questions

Example 1: an integer except $300262205$is the same as the remainder (the residue is not zero).

Analysis: according to the property of congruence, if $n$is divided by $a and b$to get the same remainder, then $n$must divide $a-b (a&gt, b) $.

So this question becomes $gcd (300-262262-205) $.

Example two: to find the remainder of $6^{592}$by $11$

Analysis: by Fermat’s little theorem, $6^{10}\equiv 1 \pmod{11}$, $(6,11) =1$, so $6^{592}=6^{10*59}*6^2= (6^{10}) ^{59}*6^2$

$(6^{10})^{59}\equiv 1 \pmod{11}$,$6^2*(6^{10})^59\equiv 6^2 \pmod{11}$,So $6^{592}\equiv 3 \pmod{11}$

Example three: $2$month $9$day in $1986$is Sunday. What is the next day of $1988$? Then what day is it on $1988^{1986}$days?

Analysis: the issue of the date is essentially a cycle problem, the cycle cycle is $7$, how many days after the week, is converted to the number of days divided by the remainder of the $7$is how much, a little look for the rule of the feeling. $1988\div 7=284\ldots 0$, the remainder is $0$, so again.$1988$day is still Sunday, but how can we solve it later? It takes some skills. To know, the power of the remainder determines the remainder of the power, several multiplied by the divisor, and the product of the remainder of each number divided by the same remainder, which determines the product of the multiplicative divisor divided by the divisorThe remainder, look at it

$8\div 7=1 \ldots 1\\$        $9\div 7=1 \ldots 2\\$         $72\div 7=10 \ldots 2$

It can be seen that the product of the multiplicative remainder determines the remainder of the $8$and the $9$product $72$divided by the $7$, so for this problem, we can divide the $1988$by $7$to get the remainder, and the remainder is multiplied by the whole to divide the remainder by the whole $7$. $1988\div 7=284\ldots * 0$, the remainder is 0, the remainder multiplied by $0^{1986}=0$, so the $1988^{1986} \div 7$residue number is $0$, so that day is still Sunday.

Example four: prove that $641 \mid (2^{2^5}+1) $

Analysis:

\begin{equation}
\begin{split}
2^{2^5}+1 & = 2^{32}+1 \\
& = 2^5*2{27}+1 \\
& = 32*2^{27}+1 \\
& = 32*(2^9)^3+1 \\
& = 32*512^3+1 \\
\end{split}
\end{equation}

So $641\equiv 32* (-129) ^3+1 \pmod{641}$

There are still many questions. However, I am too fond of qwq to pick up a few exercises.

1.Verification of $5 \not\mid \sum_{i=0}^n C_{2n+1}^{2i+1}*2^{3i}$

2.The last two digits of $(\sqrt{29} +\sqrt{21}) ^{1984}$

3.Ask all integers $m, n$, so that $mn\mid 3^m+1, mn\mid 3^n+1$

4.Find a pair of positive integers $a, b$, so that $(1) AB (a+b) $can not be divisible by $7$, and $(2) (a+b) ^7-a^7-b^7$can be divided by $7$(twenty-fifth IMO).

              a warm welcome.

 There will be the introduction of various theorems in the back.(LaTeXReal TM hard to fight)

$updateing \ldots$

Leave a Reply

Your email address will not be published. Required fields are marked *