Prove that the integer $145^{n} + 3114\cdot 138^{n}$ is divisible by $1981$ if $n=1981$, and that it is not divisible by $1981$ if $n=1980$.
Problem
Source: ISL 1980 (replacement IMO shorlist)
Tags: modular arithmetic, number theory unsolved, number theory
15.06.2011 08:42
a) Show that $1981 \mid 145^{1981} + 3114\cdot 138^{1981}$. Proof. We know that $1981 = 7 \times 283$, and $7,283$ are primes. So we should show that $145^{1981} + 3114\cdot 138^{1981}$ is divisible by $7$ and $283$. Note that \[\left.\begin{array}{cc}145 \equiv 5 \pmod 7 \implies 145^n \equiv 5^n\pmod 7\\ \text{ } \\ \left.\begin{array}{cc}3114 \equiv -1 \pmod 7\\138 \equiv 5 \pmod 7\end{array}\right\} \implies 3114\cdot 138^{n} \equiv -5^n \pmod7\end{array}\right\} \implies\]\[ 145^{n} + 3114\cdot 138^{n} \equiv 5^n - 5^n \equiv 0 \pmod 7 \qquad \forall n \in \mathbb N.\] So $7 \mid 145^{1981} + 3114\cdot 138^{1981}$. Now, we see that $3114 \equiv 1 \pmod{283}$, so we need to show that $145^{1981} + 138^{1981} \equiv 0 \pmod{283}$. By Fermat's theorem, we have $138^{1981}=138^{283 \times 7}\equiv 138^7 \pmod{283}$ and $145^{1981}=145^{283 \times 7}\equiv 145^7 \pmod{283}$. So it suffices to show that $138^7+145^7 \equiv 0 \pmod{283}$, which is easy since $138+145=283 \equiv 0 \pmod{283}$. Thus the number $145^{1981} + 3114\cdot 138^{1981}$ is divisible by both $7$ and $283$, and we are done. b) Show that $1981 \nmid 145^{1980} + 3114\cdot 138^{1980}$. Proof. It suffices to show that $283 \nmid 145^{1980} + 3114\cdot 138^{1980}$. Suppose thae contrary, i.e. suppose that $283 \mid 145^{1980} + 3114\cdot 138^{1980}$. Now since \[283 \mid 145^{1980} + 3114\cdot 138^{1980} \iff 283 \mid 145^{1980} + 138^{1980},\] we should have $283 \mid 145^{1980} + 138^{1980}$. As we proved above, $145^{1981} + 138^{1981} \equiv 0 \pmod{283}$, also \[145^{1981} + 138^{1981} = 138 \underbrace{(145^{1980} + 138^{1980})}_{\equiv 0 \pmod{283}} + 7 \cdot145^{1980} \equiv 0\pmod{283}.\] So we should have $7 \cdot145^{1980} \equiv 0\pmod{283}$, which is clearly false. Contradiction!