2
$\begingroup$

This question already has an answer here:

I can calculate the number with computer and read the digits, or I can say PowerMod[2, 100, 100] in Mathematica, or I can even determine the digits myself, pencil-and-paper, by considering congruences modulo 4 and modulo 25 separately.

But if I determine the last digit first -- it's 6 -- and then set this congruent equation for the penultimate digit $y$:

$\frac{2^{100}-6}{10} \equiv y\ (mod\ 10)$

Which simplifies to $2^{99} - 3 \equiv 5\ y\ (mod\ 10)$, or $8 \equiv 5\ y + 3\ (mod\ 10)$, or $y \equiv 1\ (mod\ 2)$. This says this digit is odd. But how can I determine its exact value from here?

I wonder why sequential modulo 10 congruences don't yield a specific answer.

$\endgroup$

marked as duplicate by lab bhattacharjee, Lucian, user223391, hardmath, user228113 Jan 17 '17 at 22:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I would advice to visit this thread were we collected a lot of relevant techniques. We have several threads alread dedicated to finding $n$ last digits, $n=2$ being very common, see this and other threads that you can find in 3 seconds from the list of Related threads in the right margin. TL; DR; I think that this should be closed as a duplicate of one of those, but I have promised not to use my power-vote to such ends. $\endgroup$ – Jyrki Lahtonen Jan 17 '17 at 13:04
  • $\begingroup$ @JyrkiLahtonen I'm not asking about the techniques, I'm familiar with the basic ones which suffice I think. What I wonder is why sequential modulo 10 congruences don't yield a specific answer. $\endgroup$ – BoLe Jan 17 '17 at 13:07
  • 1
    $\begingroup$ You already hit the reason: you cannot divide a congruence by a number that is not coprime to the modulus. If all you know that $M\equiv6\pmod{10}$. Then $(M-6)/10$ can still have any last digit you wish. You could have $M=6,16,26,36,\ldots$. You need to find the remainder of $2^{100}$ modulo both $25$ and $4$ and CRT-combine them. You cannot deduce the remainder modulo $25$ from knowing the remainder modulo $5$ alone. The even/odd deduction only says that $2^{100}$ is divisible by four (which is kinda obvious). $\endgroup$ – Jyrki Lahtonen Jan 17 '17 at 13:20
  • 1
    $\begingroup$ @BoLe It's because of multiplying both sides by 5, otherwise you will have one solution $\endgroup$ – JukesOnYou Jan 17 '17 at 13:23
2
$\begingroup$

As another method, we have :$2^{20}\equiv1(\bmod25)\implies2^{100}\equiv1(\bmod25)$ from the euler's theorem. Now, it is trivially true that $2^{100}\equiv0(\bmod4)$. Now, you can use the chinese remainder theorem to find the remainder modulo $100$ which is your required answer. For further specifics, you can refer this answer.

The answer is $76$ [$2^{100}\equiv4(25)(1)+1(19)(4)(\bmod100)$ because of the fact that $25(1)\equiv1(\bmod4) $ and $4(19)\equiv1(\bmod25)$]

$\endgroup$
  • 1
    $\begingroup$ I've already done this more or less, as I stated in the ending sentence of the first paragraph. But I wonder why sequential modulo 10 congruences don't yield a specific answer. $\endgroup$ – BoLe Jan 17 '17 at 12:55
  • $\begingroup$ didnt see that you did this already! anyways, I think modulo 10 congruences dont yield the right answer because of the non-coprimeness of 10 with 100. $\endgroup$ – vidyarthi Jan 17 '17 at 13:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.