Thursday, 18 July 2019

modular arithmetic - Using Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse -- Need some help understanding the solutions here.





The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm.
a. 81mod17=8172mod17=815mod17=15mod17
b. 51mod23=5232mod23=521mod23=14mod23
c. 601mod101=601012mod101=6099mod101=32mod101
d. 221mod211=222112mod211=22209mod211=48mod211




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.


Answer



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}


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