5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See my answer in math.stackexchange.com/questions/407478/… or math.stackexchange.com/questions/318423/… $\endgroup$ – lab bhattacharjee Aug 16 at 15:40
  • 3
    $\begingroup$ You can't use Fermat's Little Theorem here (unless you do it twice and combine it with the Chinese Remainder Theorem). You can use Euler's Theorem, though... As to finding multiplicative inverses modulo $N$, you can use the Euclidean algorithm. $\endgroup$ – Arturo Magidin Aug 16 at 15:44
  • $\begingroup$ @ArturoMagidin Yes, I used Euler's theorem. Sometimes, people just call this theorem Fermat' little theorem since it is just a generalization. $\endgroup$ – Daniel Li Aug 16 at 15:48
  • 2
    $\begingroup$ @DanielLi: Fair point, I was hasty there. P.S. Use \pmod{2}, not (\mod 2). $\endgroup$ – Arturo Magidin Aug 16 at 19:32
  • 1
    $\begingroup$ @BillDubuque Thank you very much, Bill. That's an amazing observation. I have seen this idea used everywhere unexpectedly, often related to inverse and invertibility. For example, just recently I saw a proof of existence of square root of an invertible operator $T$ using similar idea, by first breaking down $T$ to sum of nilpotent operator and identity. That's truly amazing. $\endgroup$ – Daniel Li Aug 16 at 19:48
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ @OP Beware that this common back-substitution method is notoriously error prone. It is usually much easier to propagate the linear combinations in the forward direction as in Bernards's answer, or my answer (either the fractional form, or the non-fractional form linked in the first sentence). $\endgroup$ – Bill Dubuque Aug 16 at 16:58
  • $\begingroup$ @BillDubuque Fair comment - it is as well to have practical methods of computing these things, and I agree that the back-propagation method is error-prone in practice. If you want a very brief solution here, noting that $79=80-1$ and $80+20=100$ gives $(80-1)(20-1)\equiv 1 \bmod 100$ with a lot less work - but that depends on special features of the problem. $\endgroup$ – Mark Bennet Aug 16 at 17:18
  • 1
    $\begingroup$ That's equivalent to what I wrote since $\,20\equiv -80\,$ so $\,20\!-\!1\equiv -(80\!+\!1).\,$ The reason I present it that way is because it is a special case of a general method to invert a unit + nilpotent, said with analytic intuition $\,1/(1\!-\!80) \equiv 1\!+\!80\!+\!\color{#c00}{80^2\!+\cdots}\equiv 1\!+\!80\ $ by $\ 0\equiv \color{#c00}{80^2+\cdots}\ \ $ $\endgroup$ – Bill Dubuque Aug 16 at 17:40
  • $\begingroup$ @BillDubuque Once again an acute comment. I hadn't seen your answer when I responded to your comment: the general unit+nilpotent inversion is better sense for learning. I was conscious that he way I put it was opportunistic. $\endgroup$ – Mark Bennet Aug 16 at 18:23
  • 1
    $\begingroup$ @Mike Many students make mistakes performing back-substituion (or have difficulties remembering or applying it). I've lost count of the number of times I've seen such. Otoh, far fewer errors seem to occur during forward propagation - which seems to be of lower mental complexity (essentially row operations as I explain here.) $\endgroup$ – Bill Dubuque Aug 16 at 18:56
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Note that this boils down to the same equations as in the fractional form in my answer (= first $2$ columns above), except there we optimized by using (signed) least magnitude remainders, which eliminates $\,79x\equiv 1\,$ and $\,16 x\equiv 4\,$ above. This optimization often reduces the work by a factor of $2.\ \ $ $\endgroup$ – Bill Dubuque Aug 16 at 17:06
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}.$$

$\endgroup$

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.