Modular reduction of 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$)
 A: It is valid to mod out arguments of a fraction - just like it is for the arguments sums and products
Lemma $ $ 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 \color{#c00}{B^{-1}}\equiv  a\color{#c00}{b^{-1}}\,\overset{\rm def}\equiv\, \dfrac{a}b$
Proof $\, $ Scaling $\, b\equiv B\,$ by $\,b^{-1}B^{-1}\Rightarrow \color{#c00}{B^{-1}\equiv b^{-1}}\,$ by CPR = Congruence Product Rule, so multiplying this by $\, A\equiv a\,$ yields $\, A\color{#c00}{B^{-1}}\equiv a\color{#c00}{b^{-1}}$ again by CPR. $ $ Note $b^{-1}$ exists since $\,b\equiv B\pmod{n}\Rightarrow (b,n) = (B,n)=1$
Thus 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 arithmetic (by Product and Inverse Congruence Rules) hence so too is their composition (modular "division" by units = invertibles = integers $B$ coprime to the modulus).
Similarly the Polynomial Congruence Rule extends to polynomial fractions (rational "functions") or to any expression composed of sum, product, and inverse operations (where the inverses all exist) by a simple inductive proof.
See this answer for much further discussion.
A: 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$
