How to divide a number from both sides of from congruence equation from $79^{80}\equiv 1 \pmod{100}$ to $79^{79}\equiv x \pmod{100}$? This problem is to solve $79^{79} \equiv x \pmod{100}$. I'm aware this may be solved by binomial expansion or other methods. But when we apply Euler's theorem we obtain $79^{80} \equiv 1 \pmod{100}$, which seems to be very close to our goal. I just need to divide 79 from both sides. 
Now I can do this using a stupid method: by subtracting 100 from LHS to obtain -99, -199, -299,... until "X99" is divisible by 79. I then find that $79 \times(-81)=-6399$. So we obtain $79^{80} \equiv -6399 \pmod{100}$ and divides 79 on both sides as 79 is coprime of 100. This gives me $79^{79}\equiv-81\equiv19 \pmod{100}$.
My question is if there is a more systematic/standard way of carrying out a division on both sides, perhaps something related to "inverse" etc. A group theory/ring theory approach is welcome as well.
 A: You have $79x\equiv 1 \bmod 100$ which is the same as $79x+100y=1$ for integers $x$ and $y$.
Values of $x$ and $y$ can be determined by using the Euclidean algorithm for highest common factor (=1) on the pair $100, 79$
$100=79+21$
$79=63+16$
$21=16+5$
$16=15+1$
Then reverse:
$1=16-3\times 5=16-3\times (21-16)=4\times 16-3\times 21=4\times (79-3\cdot 21)-3\times 21=4\times 79-15\times 21=4\times 79-15\times (100-79)=19\times 79-15\times 100$
whence $x=19$
A: Generally  this form of the extended Euclidean algorithm is easiest, but here below is quicker.
$\!\bmod 100\!:\ (\color{#c00}{80\!-\!1})(80\!+\!1)\equiv -1,\ $ because $\  \color{#0a0}{80^2\equiv 0}$ 
therefore: $\ \ \  \color{#c00}{79}^{-1}\equiv -81\equiv \bbox[4px,border:1px solid #c00]{19}\ $ Generally if $\,\color{#0a0}{a^n\!\equiv 0}\,$ this  iinverts $1\!-\!a\,$ [unit + nilptotent] by using a terminating geometric series:  $\ \dfrac{1}{1\!-\!a} \equiv \dfrac{1-\color{#0a0}{a^n}^{\phantom{|^|}}\!\!\!\!\!}{1-a}\equiv 1\!+\!a\!+\cdots + a^{n-1}$

Or using  a fractional form of the Extended Euclidean Algorithm, and $\,79\equiv \color{#90f}{-21}\!:$
${\rm mod}\ 100\!:\,\ \dfrac{0}{100} \overset{\large\frown}\equiv \dfrac{1}{\color{#90f}{-21}} \overset{\large\frown}\equiv \dfrac{\color{#c00}5}{\color{#0a0}{-5}} \overset{\large\frown}\equiv \dfrac{19}1\,$ or, $ $ in equational form
$\ \ \ \ \ \ \begin{array}{rrl} 
[\![1]\!]\!:\!\!\!& 100\,x\!\!\!&\equiv\ \ 0\\
[\![2]\!]\!:\!\!\!& \color{#90f}{-21}\,x\!\!\!&\equiv\ \ 1\\
[\![1]\!]+5[\![2]\!]=:[\![3]\!]\!:\!\!\!& \color{#0a0}{{-}5}\,x\!\!\!&\equiv\ \  \color{#c00}5\\
-[\![2]\!]+4[\![3]\!]=:[\![4]\!]\!:\!\!\!& x\!\!\! &\equiv \bbox[4px,border:1px solid #c00]{19}\\
\end{array}$

Or $\bmod 100\!:\,\ { \dfrac{-1}{-79}\equiv\dfrac{99}{21}\equiv \dfrac{33}7\,\overset{\rm\color{#c00}{R}_{\phantom{|}}}\equiv\, \dfrac{133}7}\equiv \bbox[4px,border:1px solid #c00]{19}\,\ $ by $\,\small\rm\color{#c00}R = $ inverse Reciprocity.

Or by CRT: $\bmod \color{#0a0}{25}\!:\ x\equiv {\large \frac{1}{79}\equiv \frac{1}4\equiv \,\frac{\!\!-24}4}\equiv \color{#0a0}{-6}.\ $ $\!\bmod\color{#c00} 4\!:\ x\equiv {\large \frac{1}{79}\equiv \frac{1}{-1}}\equiv -1,\ $ so $-1^{\phantom{|^|}}\!\!\!\equiv x \equiv \color{#0a0}{6\!+\!25}j\equiv 2\!+\!j\iff \color{#c00}{j\equiv 1}$ $\iff x = -6\!+\!25(\color{#c00}{1\!+\!4n}) = \bbox[4px,border:1px solid #c00]{19}^{\phantom{|}}\!+\!100n$
Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. In particular it is valid to cancel $\,3\,$ in $\,99/21\,$ above. See here for further discussion.  
A: Simply multiply both sides by the inverse of $79\bmod 100$. To determine it, it's easy: use the extended Euclidean algorithm to find the coefficients of a Bézout's relation between $79$ and $100$.
\begin{array}{rrrrc}
r_i&u_i&v_i&q_i \\\hline
100 & 0 & 1 \\
79 & 1 & 0 & 1 \\ \hline
21 & -1 & 1 & 3 \\
16 & 4 &-3 & 1 \\
5 & -5 & 4 & 3 \\
1 & \color{red}{19} & -15 \\
\hline
\end{array}
A: $79\equiv 4\pmod {25}\\79 \equiv 3\pmod 4\\
79^{79} \equiv 4^{79} \equiv 4^{-1}\pmod {25}\equiv 19\pmod {25}\\
79^{79} \equiv 79\equiv 3 \pmod 4$
What is the smallest number that is equivalent to $19 \pmod {25}$ and $3 \pmod 4$?
A: I discovered a way to do inverse without the messy extended GCD calculations.
Just do regular GCD calculations, and write down the intermediates.  
Example, GCD(100,79): 100 79 21 16 5 1 → gcd(100,79)=1
1
5  → -floor(1/5*16) = -3 = inverse of 5 (mod 16)
16 → -floor(-3/16*21) = 4 = inverse of 16 (mod 21)
21 → -floor(4/21*79) = -15 = inverse of 21 (mod 79)
79 → -floor(-15/79*100) = 19 = inverse of 79 (mod 100)
100
If only the last inverse is needed, you can skip some calculations.
Ignoring signs, every fractions below are convergents of $\frac{19}{100}$:
$$\frac{1}{5}, \frac{3}{16}, \frac{4}{21}, \frac{15}{79}, \frac{19}{100}$$
Since the gap $|\frac{3}{16} - \frac{4}{21}| = \frac{1}{16\times21} < \frac{1}{100}$, we can skip 2 entries in the table:  
$$79^{-1} \text{ (mod 100)} ≡ (-1)^3 \lfloor \frac{-3}{16}*100 \rfloor ≡ 19$$
see https://www.hpmuseum.org/forum/thread-446-post-113586.html#pid113586
A: You can use the binomial expansion:
$$79^{79}\equiv (80-1)^{79}\equiv A\cdot 100+{79\choose 1}\cdot 80-1\equiv 6320-1\equiv 6319\equiv 19\pmod{100}.$$
