# Proving that $3|x^2 \implies 3|x$.

Given a positive integer $x$, I would like to show that $3|x^2 \implies 3|x$. This is my missing step in the proof that $\sqrt{3}$ is irrational. My thoughts so far:

Assuming $3|x^2,$ then since $3$ is a prime number, we have that the prime factorization of $x^2$ is $m3^n$, where $n\geq 1$ and $\gcd(m,3) = 1.$ Then it follows that the prime factorization of $x$ is $r3^{n/2},$ where $\gcd(r,3) = 1$. I now want to show that $n$ must be even, so I can try to assume $n$ is odd and derive a contradiction...just not sure how to proceed.

Another way is by contradiction, assume $3\not |x$ then there are $a,b$ such that $$3a+bx=1$$ now multiply by $x$ to get $$3xa+bx^2=x$$ and $3$ divides the left by assumption so it divides the right contradiction.

• I agree I was about to edit. – Rene Schipperus Sep 4 '14 at 22:10

This should get you started: suppose $x$ contains $n'$ factors of $3$, then how many factors of $3$ does $x^2$ contain? (I don't want to deprive you of the fun of working the rest out yourself :-P)

Due to the fundamental theorem of arithmetic, we are allowed to let the prime factorization of $x$ be $x =p_1 p_2 \cdots p_k \Rightarrow x^2 = p_1^2 p_2^2 \cdots p_k^2$. Since $3|x^2$ we have that $p_i=3$ (for some $1 \leq i \leq k$). But that means $3|x$ as well because the same $p_i$ is in the factorization of $x$ too

• You are implcitly using uniqueness of prime factorizations. For the proof to be complete/correct you need to make that explicit. – Bill Dubuque Sep 4 '14 at 21:47
• Can you suggest how that can done? Thanks. – Sheheryar Zaidi Sep 4 '14 at 21:55
• I imagine he is asking you to state that "Due to unique prime factorization, we know" etc$\dots$ – Display Name Sep 4 '14 at 22:19
• Please explain how you deduced $\,3\mid (p_1\cdots p_k)^2\Rightarrow\,$ some $\,p_i = 3.\$ – Bill Dubuque Sep 4 '14 at 22:22
• @Sheheryar Then you should explicitly mention how you used it because, not too infrequently, students write such arguments thinking that no justification is needed, e.g. that is is "obvious", wrongly believing that neither FTA nor related results are needed. Without further elaboration, there is no way to know which argument was intended, the correct one, or the incorrect one. – Bill Dubuque Sep 5 '14 at 16:34

Here's an answer I just thought of, using the lemma from number theory that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(a, bc) = 1.$

Using the above lemma, if $\gcd(3,x) = 1$, then $\gcd(3, x^2) = 1.$ Then by the contrapositive, if $\gcd(3, x^2) \neq 1,$ then $\gcd(3, x) \neq 1.$ But since $3$ is prime, we can reword that assertion as $3|x^2 \implies 3|x.$

Your original post basically does it! When you get to $$x = r3^{n/2}$$

and you know that $x, r$ and $n$ are integers, it follows that $\frac{n}{2}$ is an integer too. Hence $\frac{n}{2} = k$, for some integer $k$ and $n = 2k$, so $n$ is even.