The number $2^{29}$ has (in base $10$) $9$ digits, all different. Which digit is missing? I think about using fermats theorem dosen't know how to begin
Asked
Active
Viewed 405 times
1
-
6What is the remainder of $2^{29}$ modulo $9$? – Daniel Fischer Oct 28 '16 at 21:26
-
That is 5 how come – user3704516 Oct 28 '16 at 21:35
-
And what is the sum of all digits modulo $9$? – Daniel Fischer Oct 28 '16 at 21:36
2 Answers
3
$2^{29}\equiv2^{-1}\equiv\frac{1}{2}\equiv\frac{10}{2}\equiv5\equiv \text{s} \pmod 9$ where $\text{s}$ denotes the sum of its digits.
The sum of the ten digits is $\text{S}=0+1+2+3+4+5+6+7+8+9=\frac{1}{2}\times10\times9=45\equiv0 \pmod 9$
Therefore, if $2^{29}$ contains $9$ of these and the remaing one is $n$, $2^{29}\equiv S-n\equiv-n \pmod{9}$
so $s\equiv-n\equiv5 \pmod{9}$ and the missing digit is $n=4$.
Evariste
- 2,511
-
-
Where is the part you don't understand ? I used Fermat's little theorem at line $1$. – Evariste Oct 28 '16 at 21:49
-
-
$S$ is the sum of all the digits from $0$ to $9$, which is $45$, so $S\equiv45\equiv0 \pmod 9$. And $0-n=-n$ – Evariste Oct 28 '16 at 21:54
-
-
Right, this was Euler's, sorry. I mix them up sometimes because they're so similar. – Evariste Oct 29 '16 at 08:56
0
I'll take this opportunity to do some exponentiation by squaring... work down the left-hand column, subtracting $1$ from odd numbers and halving even numbers. then go up the right-hand column. multiplying by the base, $2$, or squaring as appropriate.
$$ \begin{array}{c|r} x & 2^x\\\hline 29 & 536870912 \\ 28 & 268435456 \\ 14 & 16384 \\ 7 & 128 \\ 6 & 64 \\ 3 & 8 \\ 2 & 4 \\ 1 & 2 \\ \end{array} $$
Of course I didn't really need to go right down to the bottom, but for the sake of completeness...
Anyhow the missing digit by this labour-intensive method (yes, I did it literally on the back of an envelope while sitting at a computer) is indeed $4$.
Joffan
- 39,627