Thursday, October 31, 2019

elementary number theory - How to solve this congruence $17x equiv 1 pmod{23}$?




Given $17x \equiv 1 \pmod{23}$



How to solve this linear congruence?
All hints are welcome.



edit:
I know the Euclidean Algorithm and know how to solve the equation $17m+23n=1$
but I don't know how to compute x with the use of m or n.


Answer



To do modular division I do this:




an - bm = c where c is dividend, b is modulo and a is divisor, then n is quotient



17n - 23m = 1



Then using euclidean algorithm, reduce to gcd(a,b) and record each calculation



As described by http://mathworld.wolfram.com/DiophantineEquation.html



17 23 $\quad$ 14 19




17 6 $\quad\;\;$ 14 5



11 6 $\quad\;\;\;\;$ 9 5



5 6 $\quad\;\;\;\;\;$ 4 5



5 1 $\quad\;\;\;\;\;$ 4 1



1 1 $\quad\;\;\;\;\;$ 0 1




Left column is euclidean algorithm, Right column is reverse procedure



Therefore $ 17*19 - 23*14 = 1$, i.e. n=19 and m=14.



The result is that 1/17 ≡ 19 mod 23



this method might not be as quick as the other posts, but this is what I have implemented in code. The others could also be, but I thought I would share my method.


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