# Easy Way to Solve $7^{99} \pmod {125}$

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.

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.
• 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! – John L. Nov 15 '15 at 18:25
• @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... – Arthur Nov 15 '15 at 18:30
• 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}$ – John L. Nov 15 '15 at 18:35