Hello,

false1) i found the inverse of 9 modulo 25 to be 9^22. multiply both side and get

9^23 is not congruent to 1 mod 25

correct reasoning2) x is congruent to 9^22 times 21 mod 25

9^22 times 21 mod 25 is congruent to 1 mod 253) so then i get x is congruent to 7 mod 25.

----------------------------

Anyway, this looks naaasty ! In order to find the multiplicative inverse of the number, use the extended Euclidian algorithm.

But first of all, let's play a little with the equation :

That is to say .

Since 3 & 25 are coprime, divides 25, that is to say .

In further exercises, you can directly "simplify" by 3, since it divides 9x, 21, but not 25. If it were 24, you would have had to divide by 3 too.

Now, find the inverse of 3 mod 25. Since 3 and 25 are coprime, there exists a such that . But since 3 and 25 are coprime, we can also say that their gcd is 1. And we know that at a moment, we'll get their gcd as a remainder in the Euclidian algorithm. So let's do it and you will see that thereafter.

thus , .

That is the inverse of 3.

So

-----------------------------------

Now, if you have to use Euler's totient function (phi) :

(in general, if p is prime, then ). Thus for any number coprime with 25, for example 9, we have

. Therefore is theinverseof 9 mod 25 !

Does this help ?