Kvant Math Problem 1081
Compute a few values:
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m43s
Source on kvant.digital
Problem
Prove that the penultimate digit of the number $3^n$ is even for any natural number $n\gt2$.
V. I. Plachko
Exploration
Compute a few values:
$$3^3=27,\qquad 3^4=81,\qquad 3^5=243,\qquad 3^6=729.$$
The penultimate digits are respectively $2,8,4,2$, all even.
The penultimate digit of a positive integer is the tens digit. If a number $N$ is written as
$$N=100q+r,\qquad 0\le r<100,$$
then its tens digit is the tens digit of $r$. Hence it is enough to study the last two digits of $3^n$, that is, $3^n$ modulo $100$.
Calculating successive powers modulo $100$ gives
$$3^3\equiv 27,\quad 3^4\equiv 81,\quad 3^5\equiv 43,\quad 3^6\equiv 29,\quad 3^7\equiv 87,\quad 3^8\equiv 61,$$
and
$$3^{9}\equiv 83,\quad 3^{10}\equiv 49,\quad 3^{11}\equiv 47,\quad 3^{12}\equiv 41,\quad 3^{13}\equiv 23,\quad 3^{14}\equiv 69,$$
$$3^{15}\equiv 7,\quad 3^{16}\equiv 21,\quad 3^{17}\equiv 63,\quad 3^{18}\equiv 89,\quad 3^{19}\equiv 67,\quad 3^{20}\equiv 1.$$
A cycle of length $20$ appears. Every displayed residue has an even tens digit. The step most likely to hide an error is proving that the cycle really repeats and that every exponent belongs to it.
The natural idea is to show that $3^{20}\equiv1\pmod{100}$ and then check the finitely many residues corresponding to exponents $3,4,\dots,22$.
Problem Understanding
We must prove that for every natural number $n>2$, the tens digit of the decimal representation of $3^n$ is even.
This is a Type B problem, a pure proof.
The core difficulty is to translate a statement about the tens digit into a statement about residues modulo $100$, and then to control all powers of $3$ modulo $100$.
Proof Architecture
First, show that the tens digit of an integer depends only on its residue modulo $100$; consequently it suffices to study the last two digits of $3^n$.
Second, prove that $3^{20}\equiv1\pmod{100}$ by direct computation.
Third, deduce that the sequence of residues $3^n\bmod100$ is periodic with period $20$.
Fourth, compute the residues $3^3,3^4,\dots,3^{22}$ modulo $100$ and verify that each has an even tens digit.
Finally, use periodicity to conclude that every power $3^n$ with $n>2$ has the same tens digit as one of these checked residues.
The lemma most likely to fail under scrutiny is the periodicity claim; it requires an explicit congruence showing that multiplying the exponent by $20$ does not change the residue modulo $100$.
Solution
The tens digit of a positive integer is determined by its last two decimal digits. Thus, if two integers are congruent modulo $100$, they have the same tens digit.
Hence it is enough to study the residues of $3^n$ modulo $100$.
We first compute
$$3^{10}=59049\equiv49\pmod{100}.$$
Therefore
$$3^{20}\equiv49^2=2401\equiv1\pmod{100}.$$
Let $n>2$. Write
$$n=20k+r,$$
where
$$3\le r\le22.$$
Such an $r$ exists because replacing $r=2$ by $r=22$ and decreasing $k$ by $1$ preserves the equality.
Using $3^{20}\equiv1\pmod{100}$, we obtain
$$3^n = 3^{20k+r} = (3^{20})^k3^r \equiv 3^r \pmod{100}.$$
Thus $3^n$ and $3^r$ have the same tens digit.
It remains to check the finitely many residues $3^r\bmod100$ for $3\le r\le22$. Successive multiplication by $3$ gives
$$\begin{aligned} 3^3&\equiv27, & 3^4&\equiv81, & 3^5&\equiv43, & 3^6&\equiv29, \ 3^7&\equiv87, & 3^8&\equiv61, & 3^9&\equiv83, & 3^{10}&\equiv49, \ 3^{11}&\equiv47, & 3^{12}&\equiv41, & 3^{13}&\equiv23, & 3^{14}&\equiv69, \ 3^{15}&\equiv7, & 3^{16}&\equiv21, & 3^{17}&\equiv63, & 3^{18}&\equiv89, \ 3^{19}&\equiv67, & 3^{20}&\equiv1, & 3^{21}&\equiv3, & 3^{22}&\equiv9 \pmod{100}. \end{aligned}$$
The tens digits of these residues are
$$2,8,4,2,8,6,8,4,4,4,2,6,0,2,6,8,6,0,0,0,$$
all of which are even.
Since every exponent $n>2$ is congruent modulo $20$ to one of the exponents $3,4,\dots,22$, the number $3^n$ has the same tens digit as one of the listed residues. Hence its tens digit is even.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the passage from a tens digit statement to congruences modulo $100$. If
$$N=100q+r,\qquad 0\le r<100,$$
then the last two digits of $N$ are exactly the decimal representation of $r$. The tens digit of $N$ is therefore the tens digit of $r$. No information beyond the residue modulo $100$ is needed.
The second delicate point is the periodicity. From
$$3^{20}\equiv1\pmod{100},$$
we get
$$3^{n+20}=3^n3^{20}\equiv3^n\pmod{100}.$$
Thus every residue repeats after $20$ exponents. Without this explicit congruence, checking only finitely many powers would not justify the claim for all $n$.
A third place where mistakes can occur is the reduction of exponents. For $n=22$, the decomposition gives $k=0$, $r=22$. For $n=23$, it gives $k=1$, $r=3$. Every integer $n>2$ is covered, and no exponent outside the verified range is needed.
Alternative Approaches
A shorter argument uses Euler's theorem. Since $\gcd(3,100)=1$ and
$$\varphi(100)=40,$$
Euler's theorem gives
$$3^{40}\equiv1\pmod{100}.$$
One may then compute the $40$ possible residues modulo $100$ and check that every one has an even tens digit. This proves the result but requires twice as many cases.
Another approach works modulo $20$. The tens digit of a number $N$ is even exactly when the residue of $N$ modulo $20$ belongs to the set
$${0,1,\dots,9}.$$
The powers of $3$ modulo $20$ form the cycle
$$3,9,7,1.$$
Combining this with the fact that every power of $3$ is odd determines the possible last two digits and leads again to an even tens digit. The direct modulo $100$ method is more transparent because it tracks the last two digits exactly.