There exists a power of 2 such that the last five digits are all 3's or 6's. Find the last 5 digits of this number
I just took an olympiad and I'm wondering how this problem is solved.
Problem: There exists a power of 2 such that the last five digits are all 3's or 6's. Find the last 5 digits of this number.
Please don't find the solution on your computer and then work backward because you might not be able to fully explain the insight that a person working without a computer would need.
Solution 1:
66336:
The last digit is 6 because 3 is not divisible by 2.
The second-to-last digit is 3 because 66 is not divisible by 4.
The third-to-last digit is 3 because 636 is not divisible by 8.
The fourth-to-last digit is 6 because 3336 is not divisible by 16.
The fifth-to-last digit is 6 because 36336 is not divisible by 32.
(Edit: This is sufficient because $2^{n}$ divides $10^{n}$, so it doesn't matter what the preceding digits are.)
Solution 2:
The only set of five consecutive $3$'s and $6$'s that is divisible by $2^5$ is $66336$, so this must be the answer, since in base $10$, the divisibility of the last $n$ digits determines divisibility by $2^n$.
EDIT: It is the only one because the last two digits must be $36$ to get divisibility by $4$; then $636$ is not divisible by $8$ but $336$ is, and so forth.
EDIT: For the last claim, note that $10^n = 2^n\cdot 5^n$, so that a number of the form $10^na+b$ is divisible by $2^n$ if and only if $b$ is.
Solution 3:
There is a buried logic problem (or a trick question) about whether the conditions can be met, and the analysis shows that
ultimately the olympiad question is based on primitive roots, although they are not used anywhere in the solution!
The logical problem is that
if there exists no power of $2$ with the intended set of last $5$ digits, then the answer is anything at all (ex falso quodlibet) if one retains the existence assumption, or if one rejects it, the empty set (of $5$-digit strings of $3$'s and $6$'s).
If the needed power of $2$ exists but this is not proved, the solution only demonstrates that if the claimed power of $2$ exists, its last $5$ digits are $63366$.
To prove that the necessary power of $2$ exists is a form of discrete logarithm problem, find $n$ so that $2^n = 66336 \mod 100000$ (or show that an $n$ exists). A CAS says $n= 1196$ is the smallest solution. Without machine computation, $2$ is a primitive root modulo any power of $5$, and numbers ending in $3$ or $6$ are invertible mod $5$, so that $n$ exists and is unique mod $\varphi(5^5)$. According to the computer:
2^1196 = 1076154966024109413629211106003289717723745296590543120108327301025046293202609101212342783577252885830398182439497599236786557955676041314061975617670544834041218966978499430055292493532503445244154191526191032889459105329265035575618285860377372911545948985983714623669661161736418836299827548279852992159749169546641960180764219762832432152244594446314766336.
Other than $2$ being a primitive root, what makes the intended problem work is that $10$ is divisible by $2^1$ (and no higher power of $2$), $3$ and $6$ cover all residue classes mod $2$, and are both relatively prime to $\frac{10}{2}$. A similar problem could be asked about powers of $5$ with all the last $n$ digits equal to $1,3,5,7$, or $9$, which is the only set of digits that are odd and cover the residue classes mod $5$. All values mod $5^n$ can be reached uniquely by a combination of those digits, but because $5$ is not a primitive root modulo $4$, there is a limit to the values of $n$ where this can be done mod $10^n$, and in fact only $n=1$ is solvable.
The lucky fact of $2$ being a $5$-adic primitive root allows, for any desired length of the digit sequence, to boost the unique mod $2^n$ solution consistent with the given digits, to a mod $10^n$ solution, i.e., one that is the last $n$ digits of a power of $2$.
Solution 4:
Imagine writing down the number and then dividing by two several times (writing down only the last five digits). We don't know what the digits are yet, so we use dots:
..... <- n
..... <- n/2
..... <- n/4
.....
.....
These numbers are all powers of two, so they're all even, so each must end with an even digit. So n must end with 6. But n/2 cannot end with 3, so the 10's digit of n must be odd (namely 3):
...36
....8
.....
.....
.....
Then n/4 can end with 4 but not with 9, so the 10's digit of n/2 must be even, so we'll use 'e' in that place:
...36
...e8
....4
.....
.....
So the 100's digit of n must be odd (3 in fact). So the 10's digit of n/2 is 6. We continue in this vein and arrive at:
66336
.3168
..584
...92
....6