# Math Help - Euler's phi function

1. ## Euler's phi function

Use Euler;s Theorem to find all incongruent solutions of each congruence below.

9x is congruent to 21 mod 25.

OK, I know this is an easy computational but my anwser still does not math the books. can someone spot the error:

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

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

3) so then i get x is congruent to 7 mod 25.

and i get the anwser of 4.

I dont know where are my mistakes?

2. Hello,

1) i found the inverse of 9 modulo 25 to be 9^22. multiply both side and get
false
9^23 is not congruent to 1 mod 25

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

3) so then i get x is congruent to 7 mod 25.
9^22 times 21 mod 25 is congruent to 1 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 :
$9x \equiv 21 \bmod 25$
That is to say $9x-21=25k$.
$3(3x-7)=25k$
Since 3 & 25 are coprime, $3x-7$ divides 25, that is to say $\boxed{3x \equiv 7 \bmod 25}$.
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 $3a \equiv 1 \bmod 25$. 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.

$25=3*8+1 \implies 3*(-8)=1-25 \equiv 1 \bmod 25$
thus $a \equiv -8 \bmod 25$, $a \equiv 17 \bmod 25$.
That is the inverse of 3.

So $x \equiv 17 \cdot 7 \bmod 25$

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

$\varphi(25)=\varphi(5^2)=5 \cdot (5-1)=20$ (in general, if p is prime, then $\varphi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$). Thus for any number coprime with 25, for example 9, we have $9^{20} \equiv 1 \bmod 25$

$9^{20}=9 \cdot 9^{19}$. Therefore $9^{19}$ is the inverse of 9 mod 25 !

Does this help ?

3. There is an easy way to get the inverse.
$9x\equiv 1 ~ (25)$
If and only if,
$9x\equiv -24 ~ (25)$
If and only if,
$3x\equiv -8 ~ (25)$
If and only if,
$3x\equiv 42 ~ (25)$
If and only if,
$x\equiv 14 ~ (25)$