1
$\begingroup$

The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm.
a. $8^{-1}\bmod17=8^{17-2}\bmod17=8^{15}\bmod17=15\bmod17$
b. $5^{-1}\bmod23=5^{23-2}\bmod23=5^{21}\bmod23=14\bmod23$
c. $60^{-1}\bmod101=60^{101-2}\bmod101=60^{99}\bmod101=32\bmod101$
d. $22^{-1}\bmod211=22^{211-2}\bmod211=22^{209}\bmod211=48\bmod211$

The above is using Fermat's little theorem to find the multiplicative inverse of some modular functions. However, there is a final step just before arriving at the answer that I do not understand how to solve, except to solve it by factoring. Factoring takes a very long time.

Basically, I don't see how the answers move from the third step to the fourth step aside from arriving at the answer by factoring. There has to be a better way using Fermat's Theorem or Euler's Theorem.

$\endgroup$
  • 1
    $\begingroup$ There is no info in that image that indicates how they are computing $\large \ a^{p-2}\equiv a^{-1} \pmod p.\ $ Possibly they are using powering by repeated squaring. $\endgroup$ – Bill Dubuque Mar 17 at 2:38
  • $\begingroup$ Yes, I suspect this as well, but this is very time consuming. I am looking for a better way, but I don't seem to be able to find it. Repeating the square and factoring gives you the final answer, but as stated previously, it just takes too long. Thanks for posting. $\endgroup$ – John Doe X Mar 17 at 2:48
  • $\begingroup$ There really is no better way. Repeated squaring is actually quite fast. $\endgroup$ – Randall Mar 17 at 2:50
  • $\begingroup$ Alright, I'll take your word for it and move on to other problems. I just thought there would be a better way. Thanks a lot. $\endgroup$ – John Doe X Mar 17 at 2:55
  • 1
    $\begingroup$ @Daniel The method you used to compute $\,60^{\large -1}\pmod{101}\,$ goes back to Gauss. It is clearer in fractional form (as in my answer below), which enables fractional simplifications such as factoring (e.g. the $\!\bmod 122$ example there). Though this generally works only for prime moduli, one can in fact do the general extended Euclidean algorithm in fractional form (using multi-valued fractions). $\endgroup$ – Bill Dubuque Mar 17 at 20:06
1
$\begingroup$

Bill's way seems great. Here's another approach (with the goal of finding easily reducible powers)

\begin{align} 8^{15}\pmod {17} &\equiv 2^{45}\\ &\equiv 2\cdot (2^{4})^{11}\\ &\equiv 2\cdot (-1)^{11} \tag{$16 \equiv -1$}\\ &\equiv 15 \tag{$15 \equiv -2$} \end{align}


\begin{align} 5^{21}\pmod {23} &\equiv 5\cdot 5^{20}\\ &\equiv 5\cdot 25^{10}\\ &\equiv 5\cdot 2^{10} \tag{$25 \equiv 2$}\\ &\equiv 5\cdot 32^2\\ &\equiv 5\cdot 9^2 \tag{$32 \equiv 9$}\\ &\equiv 5\cdot 12 \tag{$81 \equiv 12$}\\ &\equiv 14 \tag{$60 \equiv 14$} \end{align}


\begin{align} 60^{99}\pmod {101} &\equiv 10^{99}&\cdot 6^{99}\\ &\equiv 10\cdot 100^{49}&\cdot 6^4 \cdot (7776)^{19}\\ &\equiv -10&\cdot -6^4\\ &\equiv 12960\\ &\equiv 32 \end{align}


\begin{align} 22^{209}\pmod {211} &\equiv (2\cdot11)^{11\cdot19}\\ &\equiv ?\\ &\text{This is where the superiority of Bill's approach becomes obvious} \end{align}

$\endgroup$
  • 1
    $\begingroup$ turn 11 into $-200 = -(2^35^2)$ and rinse. $\endgroup$ – Roddy MacPhee Mar 17 at 21:19
2
$\begingroup$

The excerpt does not indicate how they compute the power in $\, a^{\large p−2}\equiv a^{\large −1}\pmod{\! p}.\,$ One common method is to use powering by repeated squaring. You remark "but this is very time consuming. I am looking for a better way". For manual computations it is often easier to use Gauss's algorithm or other convenient variations of the extended Euclidean algorithm. Here that takes under a minute of purely mental arithmetic as below.

$\bmod 17\!:\ \ \ \ \ \ \dfrac{1}8\equiv \dfrac{2}{16}\equiv \dfrac{2}{-1}\equiv -2 $ $\ \left[\,\rm or\ \ \ \dfrac{1}8\equiv \dfrac{-16}{8},\ \ {\rm or}\,\ \ \dfrac{1}8\equiv \dfrac{18}{-9}\,\right]$

$\bmod 23\!:\ \ \ \ \ \, \dfrac{1}5\equiv \dfrac{5}{25}\equiv \dfrac{5}{2}\equiv\dfrac{28}2\equiv 14 $ $\, \left[\,\rm or\ \ \ \dfrac{1}5\equiv\dfrac{4}{20}\equiv\dfrac{4}{-3}\equiv\dfrac{27}{-3} \right]$

$\bmod 101\!:\,\ \dfrac{1}{60}\equiv \dfrac{2}{120}\equiv \dfrac{2}{19}\equiv\dfrac{10}{95}\equiv\dfrac{10}{-6}\equiv\dfrac{-5}3\equiv\dfrac{96}3\equiv 32$

$\bmod 211\!:\,\ \dfrac{1}{22}\equiv \dfrac{10}{220}\equiv \dfrac{10}{9}\equiv \dfrac{-201}3\:\dfrac{1}3\equiv\dfrac{-67}{3}\equiv\dfrac{144}3\equiv 48$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

$\endgroup$
  • 1
    $\begingroup$ you can define division with both numerator and denominator have a gcd>1 with the modulus as well most times, you just fall to a ring without it. ex. 4/2 mod 6 = 2 mod 3 $\endgroup$ – Roddy MacPhee Mar 17 at 21:34
  • $\begingroup$ @Roddy I discuss such multivalued modular fractions here.. They are not used above (and not recommended for beginners). $\endgroup$ – Bill Dubuque Mar 17 at 22:02
  • $\begingroup$ Oh I know, I'm just pointing out you can well define them, just not in the original ring $\endgroup$ – Roddy MacPhee Mar 17 at 22:25
  • $\begingroup$ @Roddy This (tangential) topic is discussed at length in the last link I gave in the answer, There is no need to repeat that here, esp. since it is not related to the question (and it may confuse beginners). $\endgroup$ – Bill Dubuque Mar 17 at 23:10
  • $\begingroup$ okay, okay. Maybe I'll make a question about a long polynomial you can answer quickly. $\endgroup$ – Roddy MacPhee Mar 17 at 23:12
1
$\begingroup$

I think you'll find there not many ( but still some) faster ways. Factoring such low exponents, isn't all that hard. Every product of same parity numbers, is a difference of perfect squares (which algebraically factors).(15=3*5;21=3*7;99=3*3*11;209=11*19)

You,could also express the exponents as sums. (15=5+5+5;21=7+7+7;99=33+33+33;209=19+19+19+19+19+19+19+19+19+19+19)

repeated squaring, and negation if over halfway(and done carefully to obey certain rules), keeps the numbers you are dealing with smaller.

with small numbers, you could potentially use more methods as shown by Bill.

EDIT for the first turn it into $2^{45}\equiv 2^{13}\bmod 17$, second is $-(3)^{20}2^{21} \bmod 23$, I think, third is equivalent to $2^{98}3^{99}5^{99}\bmod 101$ which can be made even better, fourth can be made into $-(2)^{206}5^{208}\bmod 211$

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