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

Question

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.

Answer 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.)

Answer 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.

Answer 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$.

Answer 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

Answer 5

See rogerl's answer to see why you need 32.

Here is a detailed answer. 1) last digit has to be a 6 (duh!)

For last two digits we need either $$ 2^n \equiv 36 \mod 100 \\ 2^n \equiv 66 \mod 100 $$ You know that if a number is divisible by 4 and ends in 6, the previous digit has to be odd. So the it has to be 36

Next, one of the following holds $$ 2^n \equiv 336 \mod 1000 \\ 2^n \equiv 636 \mod 1000 $$ Since 8 divides 2^n, it has to divide 336 or 636. Clearly only 336 ends. So the last 3 digits of $2^n$ is 336.

next $X336$ should be divisible by 16. So $X = 6$ so the last four digits are 6336.

Finally $x6336$ should be divisible by 32. So $x=6$

Answer 6

Another easy way would be to work with binary representation.

The number in question is a power of 2 and all powers of a number n when represented in the same base n must have their most significant digit as 1 and all other digits as 0.

e.g. 2 in binary is 10, 4 is 100, 8 is 1000...., 1024 is 10,00,00,00,000 and so on. Your number will also look like this.

But, of course, this method is equivalent to sequentially checking divisibility by 2, 4, 8, 16 and 32.