Find the inverse modulo m of each integer n below:
a) n=8 and m=35
b) n=51 and m=99
Hello,
Find p such that $\displaystyle 8p=1 \bmod 35$
Euclidian division :
$\displaystyle 35=8 \times 4+3 \implies 3=35-8 \times 4$
$\displaystyle 8=3 \times 3-1 \implies 1=3 \times 3-8=3 \times (35-8 \times 4)-8=3 \times 35-12 \times 8-8=3 \times 35-13 \times 8$
Therefore $\displaystyle (-13) \times 8=1-3 \times 35 =1 \bmod 35$
So the inverse is $\displaystyle -13 \bmod 35$, that is to say $\displaystyle 22 \bmod 35$
Try to do it...b) n=51 and m=99
Okay, there was a trap here...
You're looking for q such that $\displaystyle 51q=1 \bmod 99$
But this is not possible since 51 and 99 are not coprime.
$\displaystyle 51q=1 \bmod 99 \Longleftrightarrow \exists k \in \mathbb{Z} ~,~ 51q-1=99k \implies 1=51q-99k=3(17q-33k)$
So 3 must divide 1, which is not possible.