1
$\begingroup$

I have following congruences, in first congruence I know I have to use the Fermat theorem for finding the solution but I couldn't understand how, because most of the samples in internet using some numbers instead of x. could somebody please explain it for me in simple way?

1) $x^2 \equiv 1 \pmod{3}$

$3x \equiv 6 \pmod{15}$

2) what about the following case? $x^3 \equiv 1 \pmod{3}$

by the way I know this link but as I said it explain by numbers.

$\endgroup$
3
  • $\begingroup$ @Timbuc. I know also x2≡1(3) = x≡(+ - )1(3) and x≡−1(3)=x≡2(3) but why? what about if I have x4≡1(5)? $\endgroup$
    – user140092
    Apr 29, 2015 at 8:36
  • 1
    $\begingroup$ You can write $3x\equiv 6 (15)$ in the expanded equivalent form $3x=6+15n$ - can you solve that for $x$ $\endgroup$ Apr 29, 2015 at 8:37
  • 1
    $\begingroup$ Note that $3x\equiv6\bmod{15}$ is the same as $x\equiv2\bmod5$. $\endgroup$ Apr 29, 2015 at 9:51

2 Answers 2

1
$\begingroup$

For (1) You know by fermat's little theorem that $x$ must be coprime with $3$ and so you have $x=1,2$ and so $x \equiv 1 \pmod 3 \space \textbf{or} \space x \equiv 2 \pmod3$ And you can even try it $1^2 \equiv 1 \pmod3$ $\space$ and $\space $ $2^2 \equiv \pmod 3$

now you have $3x \equiv 6 \pmod{15} $

And since $3,6$ and $15$ are all divisible by $3$ then You can divide the congruence by $3$ to get $x \equiv 2 \pmod5 $ Now how can you use the Chinese remainder theorem ?

$\endgroup$
0
$\begingroup$

the answer is any x =2+5(3k) or x=2+5(1+3k). For the second equation gives x-2=5k or x=2+5k and upon squaring we get k=0 or 1 mod 3. The result follows.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .