Sunday, November 26, 2017

abstract algebra - 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.


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...