Question

modular inversion

Answer 1

I'm trying to find
1/16 mod 23 = ...
But I don't see what I'm doing wrong, (see attempt below)


Using the extended euclidean algorithm we get:
23 = 16 * 1 + 7
16 = 7 * 2 + 2
7 = 2 * 3 + 1

=>
1 = 7 - 2 * 3
2 = 16 - 7 * 2
7 = 23 - 16 * 1

1 = (23 - 16 * 1) - (16 - 7 * 2) * 3
1 = (23 - 16 * 1) - (16 - (23 - 16 * 1) * 2) * 3
1 = (23 - 16 * 1) - (16 - 23 * 2) * 3
1 = 23 - 16 + 6 * 23 + 16 * (-3)
1 = 7 * 23 + 16 * (-4)

7 * 23 = 0
-4 mod 23 = 19

=>
1/16 mod 23 = 19

Answer 2

From :
1 = (23 - 16 * 1) - (16 - 7 * 2) * 3
1 = (23 - 16 * 1) - (16 - (23 - 16 * 1) * 2) * 3
1 = (23 - 16 * 1) - (\(\color{red}{3}\)*16 - 23 * 2) * 3 \(\color{red}{check,please}\)
1 = 23 - 16 + 6 * 23 + 16 * (-3)
1 = 7 * 23 + 16 * (-4)