Congruence of Integers
Definition 1 When an integer \(\small{n}\) is divided by a non-zero integer \(\small{m}\), there must be an integral quotient \(\small{q}\) and a remainder \(\small{r}\), where \(\small{0 \leq|r|<m}\). This relation is denoted by
$$\small{n=m q+r}$$
and the process for getting this relation is called division with remainder.
Definition 2 Two integers \(\small{a}\) and \(\small{b}\) are said to be congruent modulo \(\small{\boldsymbol{m}}\), denoted by \(\small{a \equiv b(\bmod m)}\), if \(\small{a}\) and \(\small{b}\) have the same remainder when they are divided by a non-zero integer \(\small{m}\). If the remainders are different, then \(\small{a}\) and \(\small{b}\) are said to be not congruent modulo \(\small{m}\), denoted by \(\small{a \not \equiv b(\bmod m)}\).
By the definition of congruence, the following four equivalent relations are obvious:
$$\small{a \equiv b \quad(\bmod m) \Longleftrightarrow a-b=k m \Longleftrightarrow a-b \equiv 0 \quad(\bmod m) \Longleftrightarrow m \mid(a-b)}$$
Basic Properties of Congruence
(I) If \(\small{a \equiv b(\bmod m)}\) and \(\small{b \equiv c(\bmod m)}\), then \(\small{a \equiv c(\bmod m)}\).
(II) If \(\small{a \equiv b(\bmod m)}\) and \(\small{c \equiv d(\bmod m)}\), then
$$\small{(a+c) \equiv(b+d) \quad(\bmod m), \quad(a-c) \equiv(b-d) \quad(\bmod m)}$$
(III) If \(\small{a \equiv b(\bmod m)}\) and \(\small{c \equiv d(\bmod m)}\), then \(\small{a \cdot c \equiv b \cdot d(\bmod m)}\).
(IV) If \(\small{a \equiv b(\bmod m)}\) then \(\small{a^n \equiv b^n(\bmod m)}\) for all natural numbers \(\small{n}\).
(V) If \(\small{a c \equiv b c(\bmod m)}\) and \(\small{(c, m)=1}\), then \(\small{a \equiv b(\bmod m)}\).
The Units Digit of Powers of Positive Integers \(\small{a^n}\)
Let \(\small{P}\) be the units digit of a positive integer \(\small{a}\), and \(\small{n}\) be the positive integer power of \(\small{a}\). Then the units digit of \(\small{a^n}\) is determined by the units digits of \(\small{P^n}\), denoted by \(\small{U\left(P^n\right)}\), and the sequence \(\small{\left\{U\left(P^n\right), n=1,2,3, \ldots\right\}}\) follows the following rules:
(I) The sequence takes constant values for \(\small{P=0,1,5,6}\), i.e. \(\small{U\left(P^n\right)}\) does not change as \(\small{n}\) changes.
(II) The sequence is periodic with a period 2 for \(\small{P=4}\) or 9.
(III) The sequence is periodic with a period 4 for \(\small{P=2,3,7,8}\).
The Last Two digits of some positive integers
(I) The last two digits of \(\small{5^n(n \geq 2)}\) is 25.
(II) The ordered pair of last two digits of \(\small{6^n(n \geq 2)}\) changes with the period ” \(\small{36,96,76,56}\) ” as \(\small{n}\) changes.
(III) The ordered pair of last two digits of \(\small{7^n(n \geq 2)}\) changes with the period ” \(\small{07,49,43,01}\) ” as \(\small{n}\) changes.
(IV) The ordered pair of last two digits of \(\small{76^n}\) is always 76.
Examples
Example 1. (CHINA/2004) When a three digit number is divided by 2,3,4,5 and 7, the remainders are all 1. Find the minimum and maximum values of such three digit numbers.
Solution: Let \(\small{x}\) be a three digit with the remainder 1 when divided by \(\small{2,3,4}\), 5 and 7 . Then \(\small{x-1}\) is divisible by each of \(\small{2,3,4,5,7}\), so
$$\small{x-1=k \cdot[2,3,4,5,7]=420 k}$$
Thus, the minimum value of \(\small{x}\) is \(\small{420+1=421}\), the maximum value of \(\small{x}\) is \(\small{2 \times 420+1=841}\)
Example 2. It is known that \(\small{2726,4472,5054,6412}\) have the same remainder when they are divided by some two digit natural number \(\small{m}\). Find the value of \(\small{m}\).
Solution: For excluding the effect of the unknown remainder, the three differences by the four given numbers can be used to replace the original four numbers. Then
\begin{aligned}
& \small{m|(4472-2726) \Rightarrow m| 1746 . \quad 1746=2 \cdot 3^2 \cdot 97 \text {; } }\\
& \small{m|(5054-4472) \Rightarrow m| 582 . \quad 582=2 \cdot 3 \cdot 97 \text {; } }\\
& \small{m|(6412-5054) \Rightarrow m| 1358 . \quad 1358=2 \cdot 7 \cdot 97.}
\end{aligned}
Since 97 is the unique two digit common divisor of the differences, so \(\small{m=97}\).
Example 3. (CHINA/2000) Find the remainder of \(\small{3^{2000}}\) when it is divided by 13.
Solution: \(\small{3^3=27 \equiv 1(\bmod 13)}\) provides the method for reducing the power of 3, it follows that
$$\small{3^{2000} \equiv\left(3^3\right)^{666} \cdot 3^2 \equiv 3^2 \equiv 9 \quad(\bmod 13)}$$
Thus, the remainder is 9.
Note: For finding the remainder of a large power of a positive integer, it is important to find the minimum power with remainder 1, or see if the remainders are constant as the power changes.
Example 4. (SSSMO(J)/2001) Find the smallest positive integer \(\small{k}\) such that \(\small{2^{69}+}\) \(\small{k}\) is divisible by 127.
Solution: \(\small{2^7 \equiv 1(\bmod 127)}\) implies \(\small{2^{7 m} \equiv\left(2^7\right)^m \equiv 1^m \equiv 1(\bmod 127)}\), hence
$$\small{2^{69}=\left[\left(2^7\right)^9\right]\left(2^6\right) \equiv 2^6 \equiv 64 \quad(\bmod 127)}$$
therefore the minimum value of \(\small{k}\) is equal to \(\small{127-64=63}\).
Example 5. (SSSMO/2003) What is the remainder when \(\small{6^{273}+8^{273}}\) is divided by 49?
Solution: In general, for odd positive integer \(\small{n}\),
$$\small{a^n+b^n=(a+b)\left(a^{n-1}-a^{n-2} b+a^{n-3} b^2-\cdots+b^{n-1}\right)}$$
so that
$$\small{6^{273}+8^{273}=(6+8)\left(6^{272}-6^{271} \cdot 8+6^{270} \cdot 8^2-\cdots+8^{272}\right)=14 M}$$
where \(\small{M=6^{272}-6^{271} \cdot 8+6^{270} \cdot 8^2-\cdots+8^{272}}\). Furthermore,
$$\small{M \equiv \underbrace{(-1)^{272}-(-1)^{271}+(-1)^{270}-\cdots+1}_{273 \text { terms }} \equiv 273 \equiv 0 \quad(\bmod 7)}$$
therefore \(\small{7 \mid M}\), hence \(\small{49 \mid 14 M}\), i.e. the remainder is 0.
Example 6. Find the remainder of the number \(\small{2005^{2007^{2009}}}\) when divided by 7.
Solution: First of all \(\small{2005^{2007^{2009}} \equiv 3^{2007^{2009}}(\bmod 7)}\). Since \(\small{3^3 \equiv-1(\bmod}\) 7) yields \(\small{3^6 \equiv\left(3^3\right)^2 \equiv 1(\bmod 7)}\),
$$\small{2007^{2009} \equiv 3^{2009} \equiv 3 \quad(\bmod 6)}$$
it follows that \(\small{2007^{2009}=6 k+3}\) for some positive integer \(\small{k}\). Therefore
$$\small{2005^{2007^{2009}} \equiv 3^{6 k+3} \equiv 3^3 \equiv 6 \quad(\bmod 7)}$$
Thus, the remainder is 6.
Example 7. (SSSMO/1997) Find the smallest positive integer \(\small{n}\) such that \(\small{1000 \leq}\) \(\small{n \leq 1100}\) and \(\small{1111^n+1222^n+1333^n+1444^n}\) is divisible by 10.
Solution: Let \(\small{N=1111^n+1222^n+1333^n+1444^n}\). Then
$$\small{N \equiv 1^n+2^n+3^n+4^n \quad(\bmod 10)}$$
For estimating the minimum value of \(\small{n}\), we test \(\small{n=1000}\). Then
$$\small{N \equiv 1+\left(2^4\right)^{250}+\left(3^4\right)^{250}+\left(4^2\right)^{500} \equiv 1+6+1+6 \equiv 4 \quad(\bmod 10)}$$
Hence for \(\small{n=1001}\),
$$\small{N \equiv 1+6 \cdot 2+1 \cdot 3+6 \cdot 4 \equiv 1+2+3+4 \equiv 0 \quad(\bmod 10)}$$
Thus \(\small{n_{\min }=1001}\).
Example 8. Prove that for any odd natural number \(\small{n}\), the number \(\small{1^{2007}+2^{2007}+}\) \(\small{\cdots+n^{2007}}\) is not divisible by \(\small{n+2}\).
Solution By taking modulo \(\small{n+2}\), and partition the terms as groups of two each,
$$\begin{aligned}
& \small{1^{2007}+2^{2007}+\cdots+n^{2007} }\\
& \small{=1+\left\lfloor 2^{2007}+n^{2007}\right\rfloor+\cdots+\left\lfloor\left(\frac{n+1}{2}\right)^{2007}+\left(\frac{n+3}{2}\right)^{2007}\right\rfloor }\\
& \small{\equiv 1+\left\lfloor 2^{2007}+(-2)^{2007}\right\rfloor+\cdots+\left\lfloor\left(\frac{n+1}{2}\right)^{2007}+\left(-\frac{n+1}{2}\right)^{2007}\right\rfloor }\\
& \small{\equiv 1(\bmod n+2)}
\end{aligned}$$
Thus, the conclusion is proven.
Example 9. (SSSMO(J)/2001) Write down the last four digits of the number \(\small{7^{128}}\).
Solution: Here the recursive method is effective. Start from \(\small{7^4=2401}\), then
$$\begin{aligned}
& \small{7^4=2401 \equiv 2401 \quad\left(\bmod 10^4\right) }\\
& \small{7^8=\left(7^4\right)^2=(2400+1)^2=(2400)^2+4800+1 \equiv 4801 \quad\left(\bmod 10^4\right) }\\
& \small{7^{16} \equiv(4800+1)^2 \equiv 9601 \quad\left(\bmod 10^4\right) }\\
& \small{7^{32} \equiv(9600+1)^2 \equiv 9201 \quad\left(\bmod 10^4\right) }\\
& \small{7^{64} \equiv(9200+1)^2 \equiv 8401 \quad\left(\bmod 10^4\right) }\\
& \small{7^{128} \equiv(8400+1)^2 \equiv 6801 \quad\left(\bmod 10^4\right)}
\end{aligned}$$
Therefore the last four digits of \(\small{7^{128}}\) is 6801.
Testing Questions (A)
- (CHINA/2001) Find the number of positive integer \(\small{n}\), such that the remainder is 7 when 2007 is divided by \(\small{n}\).
- (SSSMO/1999) What is the remainder of \(\small{123456789^4}\) when it is divided by 8?
- Prove that \(\small{7 \mid\left(2222^{5555}+5555^{2222}\right)}\).
- Find the remainder of \(\small{47^{37^{27}}}\) when it is divided by 11.
- (CHINA/1990) What is the remainder when \(\small{9^{1990}}\) is divided by 11?
- (CHINA/2004) \(\small{n=3 \times 7 \times 11 \times 15 \times 19 \times \cdots \times 2003}\). Find the last three digits of \(\small{n}\).
- (CHINA/2002) When a positive integer \(\small{n}\) is divided by \(\small{5,7,9,11}\), the remainders are \(\small{1,2,3,4}\) respectively. Find the minimum value of \(\small{n}\).
- (IMO/1964) (a) Find all positive integers \(\small{n}\) for which \(\small{2^n-1}\) is divisible by 7.
(b) Prove that there is no positive integer \(\small{n}\) for which \(\small{2^n+1}\) is divisible by 7. - (SSSMO/00/Q11) What is the units digit of \(\small{3^{1999} \times 7^{2000} \times 17^{2001}}\)?
(A) 1 \(\quad\)\(\quad\)(B) 3 \(\quad\)\(\quad\)(C) 5 \(\quad\)\(\quad\)(D) 7 \(\quad\)\(\quad\)(E) 9 - Find the last two digits of \(\small{2^{999}}\).
Testing Questions (B)
- Find the last two digits of \(\small{14^{14^{14}}}\).
- Find the remainder of \(\small{\left(257^{33}+46\right)^{26}}\) when it is divided by 50.
- (SSSMO(J)/2003) What is the smallest positive integer \(\small{n>1}\) such that \(\small{3^n}\) ends with 003?
- (CHNMOL/1997) There is such a theorem: “If three prime numbers \(\small{a, b, c>}\) 3 satisfy the relation \(\small{2 a+5 b=c}\), then \(\small{a+b+c}\) is divisible by the integer \(\small{n}\).” What is the maximum value of the possible values of \(\small{n}\) ? Prove your conclusion.
- (MOSCOW/1982) Find all the positive integers \(\small{n}\), such that \(\small{n \cdot 2^n+1}\) is divisible by 3.