0
$\begingroup$

Naturally, one could do this with a calculator pretty easily, but is there a trick, or something you may notice, to calculate this easily by hand?

I know $\phi{125} = 100$, so could I perhaps use that somehow? I feel like I can, but I'm not exactly sure how.

$\endgroup$
2
$\begingroup$

Since you know that $7^{100}\equiv 1$, by Euler's theorem, we get that $7^{99}\equiv 7^{-1}$, so you could search for numbers on the form $125n+1$ which are divisible by $7$, and once you find one, divide it by seven and you will have your answer.

Of course, we have $125n+1\equiv -n+1 \pmod7$, which makes the search simple.

Alternate solution (brute force) The way computers compute powers is to do what is called repeated squares. You can calculate $7^2=49$. Then you can square that to make $7^4=49^2\equiv26$. Then you can square that again to get $7^8\equiv 26^2\equiv 51$, and so on. Then you use that $$7^{99}=7^{64+32+2+1}=7^{64}7^{32}7^27^1$$ to calculate the power with relatively few multiplications.

$\endgroup$
  • $\begingroup$ forgive my ignorance--modular arithmetic has never been my strong suit. Could you explain where the $125n + 1$ is coming from? Again, my apologies, but I would not necessarily know how to implement the method you mention in a test situation (and I feel that that's the mark of truly knowing it) Thank you so much for your help! $\endgroup$ – John L. Nov 15 '15 at 18:25
  • $\begingroup$ @JohnL. You want an $x$ such that $7x\equiv 1\pmod{125}$. All numbers that are $\equiv1\pmod{125}$ are on the form $125n+1$. That means that we want an $x$ such that there is an $n$ with $7x=125n+1$. In that case we have $x=\frac{125n+1}{7}$. Remembering that everything has to be integers, we have to make sure that $n$ is such that the fraction becomes an integer, and therefore we search for a specific $n$ such that... $\endgroup$ – Arthur Nov 15 '15 at 18:30
  • $\begingroup$ ahhh thank you so much! I really appreciate you laying it all out for me--seriously, for some reason mods just tend to go over my head most of the time lol $\endgroup$ – John L. Nov 15 '15 at 18:33
  • $\begingroup$ @JohnL. No problem. It definitely takes practice to get the feel for things. $\endgroup$ – Arthur Nov 15 '15 at 18:35
  • $\begingroup$ If you will humor me just a moment, so as to make sure I understand this: clearly, n=1 => x = 18. So now I know that [18] = [7]^-1, but now how might I make use of this in my initial equation? Again, you've already answered enough, so if you don't wish to explain I completely understand! But I just want to know how I'd now use that information in the equation $7^{99} \equiv 7^{-1}$ $\endgroup$ – John L. Nov 15 '15 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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