# Euler's theorem with fractions

Suppose I have this:

$$\frac{6^{666}}{2^{6}}$$ (mod $$125$$)

I saw it is possible to reduce only the numerator's power modulo Euler's phi function. Can someone explain why is that possible?

It is essentially this:

$$\frac{6^{666 \space (mod \phi(125))}}{2^{6}}$$ (mod $$125$$)

• What's the question? There's no need to reduce the exponent in $2^6$ as it is already small. – lulu Jan 28 at 17:06
• Can you clarify your question? It really isn't clear what you are asking. – lulu Jan 28 at 17:23
• My question is why it works? – Michael Munta Jan 28 at 17:25
• Why what works? – lulu Jan 28 at 17:27
• @MichaelMunta If, say, you had $\frac {6^{666}}{2^{501}}$ you could use Euler to write that as $\frac {6^{66}}{2^1}\pmod {125}$. – lulu Jan 28 at 17:41

It's valid to mod out the arguments of a fraction - just like it is for the arguments sums and products.

If $$(B,n)= 1\,$$ then \bmod n\!:\,\ \begin{align}A\equiv a\\ B\equiv b\end{align}\,\Rightarrow\, \dfrac{A}B\,\overset{\rm def}\equiv A\cdot B^{-1}\equiv a\cdot b^{-1}\,\overset{\rm def}\equiv\, \dfrac{a}b

So the answer to your question as to "why it works" is that unwinding the definition of a fraction yields a composition of a product and inverse operation - and those operations are compatible with modular aithmetic hence so too is their composition (modular "division" by units = invertibles = integers $$B$$ coprime to the modulus).

See this answer for much further discussion.

• So if $B \equiv b$ then also $B^{-1} \equiv b^{-1}$? – Michael Munta Jan 28 at 19:29
• @Michael Yes, multiply $\,B\equiv b\$ by $\ b^{-1}B^{-1}\$ [assuming $\,(B,n)=1,\,$ so also $\,(b,n)=(B,n)=1$] $\ \$ – Bill Dubuque Jan 28 at 20:06
• It's important to realize, as Bill Dubuque pointed out, that you must have $\gcd(B, n) = 1$. But if so, if $B \equiv b$ then $1\equiv B*B^{-1} \equiv b*B^{-1}$ and $b^{-1} \equiv b^{-1}(b*B^{-1}) \equiv B^{-1}$. Which isnt surprising as equivalence carries over multiplication and we are multiplying the inverses to get $1$ – fleablood Feb 12 at 18:01

As $$2$$ is relatively prime to $$125$$ then $$2$$ is invertable so there is a $$[\frac 12]$$ so that $$2[\frac 12]\equiv 1 \pmod {125}$$ (just let $$[\frac 12] = 63$$ but we don't actually care what $$[\frac 12]$$ is; just that it exists) so for any $$m = 2^jb$$ then $$\frac m{2^j}\equiv \frac m{2^j}(2^j*[\frac 12]^j) \equiv m*[\frac 12]^j$$.

So $$\frac {6^{666}}{2^6} \equiv 6^{666}[\frac 12]^6 \equiv 6^{\phi (666)}[\frac 12]^6\pmod {125}$$

For notation purposes it is pefectly acceptable to write $$\frac 12 \equiv 63 \pmod {125}$$ and to use the fraction notation. (Although it's perhaps misleading to use the $$2^{-1} \equiv 63 \pmod {125}$$ notation instead.)

It's just important to realize that the residuce class is not $$\{\frac 12 + 125k| k \in \mathbb Z\}$$ but $$\{m|2m \equiv 1 \pmod 125\} = \{m|\exists k\in \mathbb Z; 2m = 1 + 125k\}=\{m|2m = 1 + 125k$$ for some odd $$k\} =\{\frac {1+125(2k+1)}2| k \in \mathbb Z\}=\{63+ 125k|k \in \mathbb Z\}$$.

And it's important to realize that if $$k$$ and $$n$$ arent relatively prime there isn't and such $$k^{-1} \mod n$$ and we can't use $$\frac 1k \pmod n$$