2
$\begingroup$

True or false: If $x^2 \equiv 14 \pmod{15}$ then there exists an $x^2$ that makes this congruent

$0^2\equiv0 \mod 15$

$1^2\equiv1 \mod 15$

$2^2\equiv4 \mod 15$

$3^2\equiv9 \mod 15 $

$4^2\equiv1 \mod 15 $

$5^2\equiv10 \mod 15 $

$6^2\equiv6 \mod 15 $

I don't see this as a proof since there is no obvious pattern but right now my answer is going to be false.

$\endgroup$
  • $\begingroup$ You may also prefer considering this as $x^2\congr -1\mod 15$ $\endgroup$ – user285523 Dec 12 '15 at 5:35
  • $\begingroup$ @0.5772156649..., the $\LaTeX$ symbol for modular equivalence is $\equiv$ given by \equiv. $\endgroup$ – learner Dec 12 '15 at 7:06
  • $\begingroup$ Huh, good to know $\endgroup$ – user285523 Dec 12 '15 at 18:24
5
$\begingroup$

Suppose there is a solution. Now $15 | x^2-14$, which implies $3 | x^2 - 14$. So you have $x^2 = 14 = 2 (mod 3)$, which is not possible. Hence you have no solutions.

$\endgroup$
2
$\begingroup$

You were actually going the right way. If there is an integer solution $x$ to the congruence $x^2\equiv 14\pmod{15}$, then $\exists~k~(-7\leq k\leq 7)~\mid~x\equiv k\pmod{15}$.

All you have to do now is to prove the negation of the above statement, i.e., you have to show the following :

$$x\equiv k\pmod{15}\implies x^2\not\equiv 14\pmod{15}~\forall~k~(-7\leq k\leq 7)$$

Since $x^2\equiv (-x)^2$, it suffices to show that none of $0^2,1^2,2^2,\ldots,7^2$ are congruent to $14$ modulo $15$ to prove that $x^2\equiv 14\pmod{15}$ has no solutions.

You already did it till $6^2$. Just do one more ($7^2$) and you would have a complete proof. It's easy to check that $7^2=49\equiv 4\not\equiv 14\pmod{15}$.

$\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.