# Thread: congruence equation

1. ## congruence equation

Hi'
I need help in solving the equation:

x^25=2 (mod 133)

2. ## Re: congruence equation

Hi,
Here's some help. If you still have problems, post again.

3. ## Re: congruence equation

If we tart with the second equation we get x=2(mod7) and we lose the other solutions.where is my mistake?

4. ## Re: congruence equation

How do the solutions of the separate equations provide solutions for the original one?

5. ## Re: congruence equation

the solutions 14 and 3 of the second equation are incorrect.

6. ## Re: congruence equation

Suppose $x \equiv 3 \pmod{19}$ and $x \equiv 2 \pmod{7}$. Then, by the Chinese Remainder Theorem, $x \equiv 79 \pmod{133}$. Indeed, $79^{25} \equiv 2 \pmod{133}$. This is a solution (so the solutions 14 and 3 of the second equation are not incorrect... at least 3 is correct).

Suppose $x \equiv 2 \pmod{19}, x\equiv 2 \pmod{7}$. Then, $x \equiv 2\pmod{133}$, and $2^{25} \equiv 128 \pmod{133}$, so this is not a solution.

Suppose $x \equiv 14 \pmod{19}, x\equiv 2\pmod{7}$. Then, $x \equiv 128 \pmod{133}$, and $128^{25} \equiv 79 \pmod{133}$, so again, this is not a solution.

Hence, the only solution is $x \equiv 79 \pmod{133}$.

7. ## Re: congruence equation

How do you compute 79 and 128 from the chineese remainder theorem?sorry'i am not quite famikiar with this subject.

8. ## Re: congruence equation

Use an online Chinese Remainder Theorem Calculator? You need familiarity with the subject to be able to calculate solutions otherwise.

Here is a link to a calculator that will do it for you: Chinese Remainder Theorem Calculator

How it works: Suppose $x \equiv 3 \pmod{19}, x \equiv 2 \pmod{7}$

Then, we know $x = 3+19a$ for some integer $a$. So, the possible equivalence classes of $x \pmod{133}$ are $3, 22, 41, 60, 79, 98, 117$. We check each $\pmod{7}$ and discover that only $79 \equiv 2 \pmod{7}$.

Do the same for $x \equiv 2 \pmod{19}$ or $x \equiv 14 \pmod{19}$.

9. ## Re: congruence equation

so x=79mod(133) is the unique solution of the two equation.theoretically'why should it be the solution of the original equation?

10. ## Re: congruence equation

It is obvious in second tought.
Thank's