2
$\begingroup$

In a correction of an exercise, the teacher simply wrote down

$$2^{107}\text{mod }187 = 161.$$

Is there any way for this to be so easily calculated?

$\endgroup$

closed as off-topic by TheSimpliFire, José Carlos Santos, user91500, Adrian Keister, Arnaud D. Jan 16 at 16:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – TheSimpliFire, José Carlos Santos, user91500, Adrian Keister, Arnaud D.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Well, $187=11\times 17$ and it is easy enough to work out $2^{107}$ modulo each of those primes. That's a good start. $\endgroup$ – lulu Jan 21 '18 at 16:28
  • $\begingroup$ See math.stackexchange.com/questions/81228/… $\endgroup$ – Arnaud D. Jan 16 at 16:57
2
$\begingroup$

We have $$2^{10}=1024\equiv89\pmod{187}$$ $$89^2=7921\equiv67\pmod{187}$$ $$67^2=4489\equiv1\pmod{187}$$ so $$2^{107}=2^{100}\cdot2^{7}=(2^{10})^{10}\cdot128\equiv89^{10}\cdot128\equiv67^5\cdot128\equiv67\cdot128=161\pmod{187}$$as desired.

$\endgroup$
1
$\begingroup$

use that $$2^{40}\equiv 1 \mod 187$$

$\endgroup$
  • 1
    $\begingroup$ Would you care to explain how to use that? It doesn' t seem to have immediate connections to the question or the (known) answer. $\endgroup$ – Professor Vector Jan 21 '18 at 16:31
  • $\begingroup$ it is the Little Theorem of Fermat $\endgroup$ – Dr. Sonnhard Graubner Jan 21 '18 at 16:32
  • 1
    $\begingroup$ Sorry, maybe I didn't make myself clear enough: I wasn't asking about well-known theorems, I asked how to use your remark. $\endgroup$ – Professor Vector Jan 21 '18 at 16:34
  • 1
    $\begingroup$ I don't have a problem, I asked a question: how can your remark help to get to the known answer? If @Atmos can do $2^{27}$ by mental calculation, that's fine, but most can't. $\endgroup$ – Professor Vector Jan 21 '18 at 16:38
  • 1
    $\begingroup$ Ok, I desist. When you understand something, you call it a device. When you don't, you call it a trick. $\endgroup$ – Professor Vector Jan 21 '18 at 16:43

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