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.

-
"last five digits" means the five at the right? and these can be threes and sixes in some order, is that correct? –  Igor Rivin Jan 8 at 1:20
I too just had the same problem (which I did not know how to solve)! You might want to add a tag number-theory. –  user2612743 Jan 8 at 1:26
Out of curiosity, which contest is this from? –  Potato Jan 8 at 1:26
The mandelbrot contest –  user2612743 Jan 8 at 1:26
In case anyone is interested, the first such powers of 2 are $2^{1196}$, $2^{3696}$, $2^{6196}$ ... and all solutions are of the form $2^{1196 + 2500k}$ for $k=0,1,2,\dots$. –  Chris Taylor Jan 8 at 11:47

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.

-
Why this is the only one? –  Berci Jan 8 at 1:21
"in base 10, the divisibility of the last n digits determines divisibility by $2^n$" --- can you supply a link or proof for this? This seems like a pretty non-obvious fact. –  Newb Jan 8 at 1:22
36336 is not divisible by 32. –  Braindead Jan 8 at 1:25
@Braindead Oops, thanks. –  rogerl Jan 8 at 1:28
@Newb because if you work in mod 2^n, any term with power higher than or equal to 10^n is divisible by 2^n so working in mod 2^n makes it 0. –  user2612743 Jan 8 at 1:32

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

-
Is there a way to do this without checking divisibility by such large numbers? What if the problem specified to get 20 digits and you didn't have a calculator? Would it be possible? –  Elliot G Jan 8 at 2:36
Checking for divisibility by $2^n$ is really easy, though. When you check for divisibility by 31, you have to divide the whole number by 31. When you check for divisibility by 32, you only have to divide by 2, at most 5 times, and you only have to divide the last 5 digits. –  MJD Jan 8 at 2:38
Ok then. I still prefer rogerl's answer because he proved that divisibility of the last $n$ digits determines divisibility by $2^n$ more clearly, in my opinion. Maybe I just didn't understand you. –  Elliot G Jan 8 at 2:40

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

-
There seems to be some steps/explanation of reasoning missing from this answer. I can follow where the 1's column digits come from, but it isn't obvious from your steps where you are getting the them, and therefore why any given 10's digit must be odd or even. Personally I've failed to make the leap from 'e must be even' to 'the 100's digit of n must be odd'. What information am I missing that makes this obvious? –  Mr.Mindor Jan 8 at 17:34
@Mr.Mindor: Let's call the 10^k digit of the jth row [j,k]. Given [j,k], there are two choices for [j+1,k], one odd and one even. The choice will determine whether [j,k+1] is odd or even. The 10's digit of n ([1,1]) is 3, so the 10's digit of n/2 ([2,1]) must be 1 or 6. If the 100's digit of n ([1,2]) is even then [2,1] is less than [1,1], namely 1; if [1,2] is odd then [2,1] is more than [1,1], namely 6. We already know it must be even, so it's 6, and [1,2] is odd (which is to say 3). –  Beta Jan 8 at 18:24
I see now. It wasn't clicking that this held true generally for all digits [j,k] (when dividing by 2). IMO it wouldn't hurt to add this reasoning into the answer itself somewhere before you start pulling specific numbers out. (maybe a chart of the possible values of [j+1,k] for values of [j,k] at the end) –  Mr.Mindor Jan 8 at 20:46
Also the relationship between [j+1,k] and [j,k+1] presented in a way that the value you have ([j+1,k]) leads to the odd/even attribute of the value you don't have ([j,k+1]) would be clearer in this case: The choice will determine whether [j,k+1] is odd or even, if the greater of the two options is selected, [j,k+1] will be odd, otherwise [j, k+1] will be even. The [j+1,k] is less than / more than [j,k] doesn't hold when [j,k] is 0 or 9. –  Mr.Mindor Jan 8 at 20:55
Once fully understood, I like this answer the most, it breaks the problem down into a plain logic puzzle. For others like myself for whom the possible values for [j+1,k] do not immediately jump to mind: 0:[0|5], 1:[0|5], 2:[1|6], 3:[1|6], 4&5:[2|7], 6&7:[3|8], 8&9: [4|9] –  Mr.Mindor Jan 8 at 22:33
show 1 more comment

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

-
Thanks, this was very interesting. –  Chris Taylor Jan 9 at 8:24

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$

-

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.

-