Kvant Math Problem 1270

Verified: yes
Verdicts: PASS + PASS
Solve time: 12m59s
Source on kvant.digital

Problem

Prove that if the last digit of the decimal representation of the number $m$ is 5, then $12^m+9^m+8^m+6^m$ is divisible by 1991.

N. B. Vasilyev

Step 1: Reduction of the problem

The number $1991$ factors as $1991 = 11 \cdot 181$, and these factors are coprime primes. By the Chinese Remainder Theorem, it suffices to show that

$12^m + 9^m + 8^m + 6^m \equiv 0 \pmod{11}$

and

$12^m + 9^m + 8^m + 6^m \equiv 0 \pmod{181}$

for every integer $m$ whose last decimal digit is $5$. Writing $m = 10k + 5$ with $k \ge 0$ reduces the problem to proving divisibility modulo each prime separately for all $k \ge 0$.

Step 2: Modulo 11

Since $11$ is prime, Fermat's little theorem implies that for any integer $a$ not divisible by $11$, $a^{10} \equiv 1 \pmod{11}$. The bases in question satisfy $12 \not\equiv 0$, $9 \not\equiv 0$, $8 \not\equiv 0$, and $6 \not\equiv 0$ modulo $11$. Reducing the bases modulo $11$ gives $12 \equiv 1$, $9 \equiv -2$, $8 \equiv -3$, and $6 \equiv 6$. Since $m \equiv 5 \pmod{10}$, the exponents can be reduced modulo $10$:

$12^m \equiv 1^5 \equiv 1 \pmod{11}, \quad 9^m \equiv (-2)^5 \equiv -32 \equiv 1 \pmod{11},$

$8^m \equiv (-3)^5 \equiv -243 \equiv -1 \pmod{11}, \quad 6^m \equiv 6^5 \equiv 7776 \equiv -1 \pmod{11}.$

Adding these residues yields

$12^m + 9^m + 8^m + 6^m \equiv 1 + 1 - 1 - 1 \equiv 0 \pmod{11}.$

Thus the expression is divisible by $11$ for all $m$ ending with the digit $5$.

Step 3: Modulo 181

Since $181$ is prime, Fermat's little theorem gives $a^{180} \equiv 1 \pmod{181}$ for all integers $a$ not divisible by $181$. Writing $m = 10k + 5$, the expression can be rewritten as

$12^m + 9^m + 8^m + 6^m = 12^5(12^{10})^k + 9^5(9^{10})^k + 8^5(8^{10})^k + 6^5(6^{10})^k \pmod{181}.$

The necessary powers are computed modulo $181$. First, the fifth powers:

$12^5 = 248832 \equiv 138 \pmod{181}, \quad 9^5 = 59049 \equiv 43 \pmod{181},$

$8^5 = 32768 \equiv 7 \pmod{181}, \quad 6^5 = 7776 \equiv 174 \pmod{181}.$

Next, the tenth powers:

$12^{10} = (12^5)^2 \equiv 138^2 = 19044 \equiv 39 \pmod{181},$

$9^{10} = (9^5)^2 \equiv 43^2 = 1849 \equiv 39 \pmod{181},$

$8^{10} = (8^5)^2 \equiv 7^2 = 49 \pmod{181}, \quad 6^{10} = (6^5)^2 \equiv 174^2 = 30276 \equiv 49 \pmod{181}.$

Substituting these values gives

$12^m + 9^m + 8^m + 6^m \equiv 138 \cdot 39^k + 43 \cdot 39^k + 7 \cdot 49^k + 174 \cdot 49^k \pmod{181}.$

Combining like terms:

$(138 + 43)\cdot 39^k + (7 + 174) \cdot 49^k = 181 \cdot 39^k + 181 \cdot 49^k \equiv 0 \pmod{181}.$

Hence the expression is divisible by $181$ for all $k \ge 0$, and therefore for all integers $m$ ending with the digit $5$.

Step 4: Final conclusion

Since $12^m + 9^m + 8^m + 6^m$ is divisible by both $11$ and $181$, and these primes are coprime, the Chinese Remainder Theorem implies that the expression is divisible by

$11 \cdot 181 = 1991$

for every integer $m$ whose last decimal digit is $5$. This establishes the universal divisibility statement required.

This completes the proof.