- #1
PsychonautQQ
- 784
- 10
Homework Statement
in mod 35, find the inverse of 13 and use it to solve 13x = 9
gcd(35,13) =1 so the inverse exsists:
35 = 2*13 + 9
13 = 1*9 + 4
9 = 2*4 + 1
4 = 4*1
and then to find the linear combination
1 = 9 - (2*4) = 9 - 2(13-9) = 3*9 - 2*13 = 3* (35 - 2*13) - 2*13 = 3*35 - 8*13 = 1
but mostly
3*35 - 8*13 = 1..
so -8 is the inverse of 13 in modulo 35.. using that to solve the equation
x = -72
but the back of my book says the inverse is 27, which would make x = 243... where did I go wrong? I can't find my mistake