Thanks A Million (Almost), Galileo!

Number Theory Level 4

Find the last 6 digits of $16^{1564}$ .

The answer is 999936.

2 solutions

Otto Bretscher
Feb 7, 2016

Since $4\equiv -1 \pmod{5}$ , we know that $4^{5^5}\equiv -1^{5^5}=-1 \pmod{5^6}$ . Now $4^{5^5}\equiv 2^{2\times 5^5}$ $=2^{6250}\equiv -1 \pmod{5^6}.$ Multiplying through with $2^{6}=64$ , we find that $2^{6256}=16^{1564}\equiv -64\equiv \boxed{999936} \pmod{10^6}$ .

The second conclusion of your posting is not understandable for me! Can you please explain?

Andreas Wendler - 5 years, 4 months ago

I will be glad to explain. Which exactly is the second conclusion?

Otto Bretscher - 5 years, 4 months ago

This one immediately after "...we know that". Thanks.

Andreas Wendler - 5 years, 4 months ago

@Andreas Wendler – Yes, that is an important principle in the modular arithmetic of prime powers: If $a \equiv b \pmod{p^k}$ , where $p$ is prime, then $a^p\equiv b^p \pmod{p^{k+1}}$ . To see this, write $b=a+np^k$ and take the $p$ th power, using the binomial theorem. All the terms on the RHS except possibly $a^{p}$ will factor through $p^{k+1}$ . In my solution, I'm using this principle five times in a row, for $p=5$ .

Does this make sense?

Otto Bretscher - 5 years, 4 months ago

@Otto Bretscher – Thank you very much, Sir. I never heard about this principle but will keep it in mind now! The proof was not difficult with your help!

Andreas Wendler - 5 years, 4 months ago

@Otto Bretscher – Woah! This is literally awesome! I'm adding this trick into my arsenal of modular arithmetic tricks! Thank you, Comrade Otto!

Pi Han Goh - 5 years, 4 months ago

May I know what's the relevance of Galileo to this problem?

Pi Han Goh - 5 years, 4 months ago

Have a look at Galileo's year of birth and you will know! ;-)

Andreas Wendler - 5 years, 4 months ago

Hahahahahaha! Got it thanks!

Pi Han Goh - 5 years, 4 months ago

I thought about this , $a\equiv b$ (mod z) , then , $an\equiv bn$ (mod $zn$ ) for any $n$

Nice solution btw ...@Otto Bretscher

A Former Brilliant Member - 5 years, 4 months ago

Yes, good point: I am using this type of congruence too, with $n=2^6$ , to go from $2^{6250}\equiv -1 \pmod{5^6}$ to $2^{6256}\equiv -2^6 \pmod{10^6}$ .

Otto Bretscher - 5 years, 4 months ago

The condition for $a^{p}\equiv b^{p}$ mod $p^{k+1}$ should be $a$ should not be prime right ? @Otto Bretscher

A Former Brilliant Member - 5 years, 4 months ago

$p$ is required to be prime... no conditions are imposed on $a$ and $b$

Otto Bretscher - 5 years, 4 months ago

Mark Hennings
Feb 7, 2016

Since $64 = 5\times13 - 1$ we have $64^{5^5} \,\equiv\, (-1)^{5^5} \; \equiv \; -1$ modulo $5^6$ . If it were true that $16^{1564} \equiv 64$ modulo $5^6$ , then $64^{5^5} \; \equiv \; 16^{4\times391\times5^5} \; =\; 16^{391 \phi(5^6)} \; \equiv \; 1$ modulo $5^6$ , which is not the case. Thus $64^{5^5} \not\equiv 64$ modulo $5^6$ .

Now $16 = 3\times5+1$ , so that $\begin{array}{rcl} 16^{3125} \; = \; 16^{5^5} & \equiv & 1 \\ \big(16^{1564}\big)^2 \; \equiv \; 16^{3128} & \equiv & 16^3 \; \equiv \; 64^{2} \end{array}$ modulo $5^6$ , and hence $16^{1564} \,\equiv\, \pm 64$ modulo $5^6$ . From the first paragraph, we deduce that $16^{1564} \,\equiv\, -64$ modulo $5^6$ .

On the other hand, it is clear that $16^{1564} \,\equiv\, 0$ modulo $2^6$ , from which we deduce that $16^{1564} \,\equiv\, -64$ modulo $10^6$ . The last $6$ digits of $16^{1564}$ are $1000000-64 = \boxed{999936}$ .

Another careful solution! Thanks! (+1)

Here is a question for you, just to clarify: If $x^2 \equiv 64^2 \pmod{5^6}$ , how do you know that $x\equiv \pm 64$ ?

Otto Bretscher - 5 years, 4 months ago

$x+64$ and $x-64$ cannot both be divisible by $5$ , since $128$ is not. Thus one or the other is divisible by $5^6$ .

Mark Hennings - 5 years, 4 months ago

Yes, exactly. It would not work mod 8, for example, where $x^2 \equiv 3^2$ has 4 solutions.

Otto Bretscher - 5 years, 4 months ago

Thanks A Million (Almost), Galileo!

The answer is 999936.

2 solutions

0 pending reports