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$)

  • $\begingroup$ What's the question? There's no need to reduce the exponent in $2^6$ as it is already small. $\endgroup$ – lulu Jan 28 at 17:06
  • 1
    $\begingroup$ Can you clarify your question? It really isn't clear what you are asking. $\endgroup$ – lulu Jan 28 at 17:23
  • $\begingroup$ My question is why it works? $\endgroup$ – Michael Munta Jan 28 at 17:25
  • 1
    $\begingroup$ Why what works? $\endgroup$ – lulu Jan 28 at 17:27
  • 1
    $\begingroup$ @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}$. $\endgroup$ – 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.

  • $\begingroup$ So if $B \equiv b$ then also $B^{-1} \equiv b^{-1}$? $\endgroup$ – Michael Munta Jan 28 at 19:29
  • $\begingroup$ @Michael Yes, multiply $\,B\equiv b\ $ by $\ b^{-1}B^{-1}\ $ [assuming $\,(B,n)=1,\,$ so also $\,(b,n)=(B,n)=1$] $\ \ $ $\endgroup$ – Bill Dubuque Jan 28 at 20:06
  • $\begingroup$ 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$ $\endgroup$ – 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$


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.