Juan writes the list of pairs $(n, 3^n)$, with $n=1, 2, 3,...$ on a chalkboard. As he writes the list, he underlines the pairs $(n, 3^n)$ when $n$ and $3^n$ have the same units digit. What is the $2013^{th}$ underlined pair?
Problem
Source: CentroAmerican 2013 Problem 1
Tags: modular arithmetic, number theory unsolved, number theory, Last digit
professordad
24.08.2013 22:44
The units digit of $3^n$ can only be 3, 9, 7, or 1. Also, $n$ would have to be even for the units digit of $3^n$ to be 9 or 1; then $n$ and $3^n$ cannot have the same units digit.
We have two possibilities:
1) $n \equiv 1 \pmod{4}$ and $3 \pmod{10}$: then $n \equiv 13, 33 \pmod{40}$
2) $n \equiv 3 \pmod{4}$ and $7 \pmod{10}$: then $n \equiv 7, 27 \pmod{40}$
The 1st underlined pair is $(7,3^7)$; the 5th underlined pair is $(47,3^{47})$; the 9th underlined pair is $(87,3^{87})$; and so on. The $(4k+1)$-th underlined pair is $(40k+7)$-th pair, so the $n$th pair for $n \equiv 1 \pmod{4}$ is $10n - 3$. Thus the answer is $\boxed{(20127,3^{20127})}$.
Tanjiro139
11.05.2022 02:26
Let $a_{i}$ the $i-th$ underlined pair. Checking some cases we have $a_{1}=7$, $a_{2}=13$, $a_{3}=27$, $a_{4}=33$, $a_{5}=47$, $a_{6}=53$, $a_{7}=67$ and so on. Here, is easy to see that if $i$ is odd, $a_{i+2} - a_{i}=20.$ Claim; If $i$ is odd, $a_{i}=7+20 \lfloor\frac{i}{2}\rfloor$ Proof using induction; If $i=1\Rightarrow a_{1}=7+20\lfloor\frac{1}{2}\rfloor=7+20(0)=7$. Now, suppose that its true for $1,3,5,..,i$. So, we have to prove it for $i+2$. We have $a_{i+2}=7+20 \lfloor\frac{i+2}{2}\rfloor$=$7+20( \lfloor\frac{i}{2}\rfloor+1)$=$7+20 \lfloor\frac{i}{2}\rfloor+20$=$a_{i}+20$, this implies that this is true. So, $a_{2013}=7+20 \lfloor\frac{2013}{2}\rfloor$=$20127$. So, the $2013-th$ underlined pair is $(20127, 3^{20127})$