2
$\begingroup$

Solve the congruence $x^5\equiv 3 \space mod \space 11$

The solution says that any solution of this equation must satisfy gcd(x,11)=1 and I'm not sure why.

I understand the theorem : "the linear diophantine equation $ax+by=c$ has solutions iff $gcd(a,b)|c$" but in this case the congruence is not linear...

Is it perhaps to do with the fact that if $gcd(x,11) >1$ then the gcd would have to be 11 and that would mean that x is divisible by 11 and thus $x \equiv 0\space mod \space 11$ and thus we would have $(0)^5 \equiv 3 \space mod \space 11$ and in this case we would of course not have any solution?

$\endgroup$
  • 2
    $\begingroup$ Completely correct. $\endgroup$ – Parcly Taxel Jan 13 at 9:57
  • $\begingroup$ The afirmation is true $\endgroup$ – El borito Jan 13 at 10:07
2
$\begingroup$

As you said, if $\gcd(x, 11)>1$ then it is $11$ and if $11|x$ it is easy to see that $x^5$ is congruent with $0$ $\mod {11}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.