Saturday, 13 May 2017

abstract algebra - How to divide a number from both sides of from congruence equation from 7980equiv1pmod100 to 7979equivxpmod100?



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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...