3

Find the last 10 digits of the number $9511627776^{195761}2^{17}$.

Well, I know I just have to perform $$9511627776^{195761}2^{17} \mod 10^{10}$$

and I know that $195761$ is prime. Also, $9511627776 \equiv 2^{40} \mod 10^{10}$. Where do we go from here?

Don Larynx
  • 4,703
  • Chinese Remainder Theorem is your friend. You already know the remainder modulo $2^{10}$. Concentrate on $5^{10}$. Have you got access to a CAS? Remember that the multiplicative group of residue classes modulo $5^{10}$ is cyclic of order $4\cdot5^9=7812500$, and $40\cdot195761=7830440$, which allows for a significant reduction in the exponent. – Jyrki Lahtonen Jan 21 '15 at 20:24
  • The answer is $9511627776^{195761}2^{17}\equiv (2^{10})\cdot r\cdot \left(\frac{1}{2^{10}}\mod {5^{10}}\right) \pmod {10^{10}}$, where $9511627776^{195761}2^{17}\equiv r \pmod {5^{10}}$. After very tedious calculations with the Windows 7 calculator (I hope I didn't make a mistake in the long process), I have that $r\equiv 1099622\pmod {5^{10}}$, giving the answer $9511627776^{195761}2^{17}\equiv 4786255872\pmod {10^{10}}$ (I used this website to find $(2^{10})^{-1}\pmod 5^{10}$). – user26486 Jan 21 '15 at 20:49
  • @JyrkiLahtonen Let $k=195761$. We know that $40k\equiv 17940\pmod {\phi(5^{10})}$ and $\text{OP}\equiv 9674651^{k\pmod {\phi(5^{10})}}2^{17}\pmod {5^{10}}$. How are you able to reduce the exponent? – user26486 Jan 21 '15 at 21:24
  • @user314: Don already said that $9511627776\equiv2^{40}\pmod{10^{10}}$. Therefore $$9511627776^{195761}\equiv2^{40\cdot195761}\equiv2^{17940}\pmod{5^{10}}.$$ – Jyrki Lahtonen Jan 21 '15 at 22:09
  • 1
    $2^{\large40~\cdot~195761~+~17}\equiv9700303872\mod10^{10}$. – Lucian Jan 21 '15 at 23:07
  • @Lucian how did you get that number? – Don Larynx Jan 21 '15 at 23:16
  • I used Mathematica. – Lucian Jan 21 '15 at 23:19
  • Maple and Maxima confirm the result. – Lucian Jan 22 '15 at 00:50

0 Answers0