[2024/08/04] Extended Euclid's Algorithm
[2024/08/04] Extended Euclid's Algorithm
- Given
n
andm
are coprime, show that there exist integern'
such thatnn' mod m=1
. - The extended Euclid's algorithm is given below without proof, which may be useful in your proof.
(I'm too lazy to type out the algorithm again, so look at the image yourself)
1
comments
Hint
spoiler
If you are studying the algorithm, you are doing it wrong
Solution: https://gmtex.siri.sh/fs/1/School/Extra/Maths/Qotd solutions/2024-08-04_extended-euclid.html
spoiler
2Reply