1
$\begingroup$

I came across this in proving that the $\sqrt{3}$ is irrational

$\endgroup$

marked as duplicate by abiessu, MJD, BlackAdder, Adam Hughes, user147263 Sep 5 '14 at 3:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ $p^2$ has two factors, $p$ and $p$, therefore a $3$ must come from $p$ or $p$. Hey... there's a $3$ in $p$, therefore $3|p$ $\endgroup$ – Dane Bouchie Sep 5 '14 at 2:37
  • $\begingroup$ $q$ is a prime if and only if $q\mid ab$ implies $q\mid a$ or $q\mid b$. $\endgroup$ – Frudrururu Sep 5 '14 at 2:43
2
$\begingroup$

Take the contrapositive statement: Prove that if $p$ is not divisible by $3$, then $p^2$ is not divisible by $3$.

$\endgroup$
0
$\begingroup$

Try proof by contrapositive:

Assume that for some $p$, $3 \nmid p$, then the only two cases are: $p \equiv 1\pmod{3}$ and $p \equiv 2\pmod{3}$. Calcualte $p^2 \mod 3$ and get the conclusion.

$\endgroup$
0
$\begingroup$

Even if you don't know (don't remember) any number theory, you can always write $p=3m+k$ where $m$ is an integer and $k\in\{0,1,2\}$. Then, $$ p^2=(3m+k)^2=9m^2+6mk+k^2. $$ In other for this to be divisible by $3$, $k^2$ has to be divisible by $3$. You can manually check that only $k=0$ works.

$\endgroup$
0
$\begingroup$

I would take an approach by looking at the prime factorization of $p^2$. Since it's a square, the powers of its prime factorization must all be even numbers. Since it's divisible by $3$, it has a $3$ raised to some nonzero even number.

It follows from this that $p$ must also have $3$ in its prime factorization.

$\endgroup$
0
$\begingroup$

This is a particular instance of the Euclid's lemma. It is an easy consequence of prime factorization, but without assuming prime factorization slightly less easy.

$\endgroup$

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