Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$'

I need to prove this statement. I think it is true and also the converse is true.

I took some examples such as $\gcd(2,5)=1$, and $\gcd(4,25)=1$...

But how can I prove this? I know that $1=ax+by$ for some $4x,y\in \mathbb{Z}$.. But not sure

How to go from there..

Any clue?

share|cite|improve this question

marked as duplicate by Git Gud, Old John, Vedran Šego, Jyrki Lahtonen, azimut Dec 7 '13 at 20:37

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.

Try cubing both sides of that equation. – Tobias Kildetoft Dec 7 '13 at 19:13
This might help you:… – Stefan4024 Dec 7 '13 at 19:13
And the converse is also true. – 1015 Dec 7 '13 at 20:11

Write down the prime factorization of $a^2$ in terms of that for $a,$ and similarly for $b^2.$

share|cite|improve this answer
It looks like OP wants a proof using Bezout's Lemma, not UPF. – Tim Ratigan Dec 7 '13 at 19:16
I am not sure I can use prime factorization because it is coming next chapter in my textbook. – Wes Dec 7 '13 at 19:18
What CAN you use? – Igor Rivin Dec 7 '13 at 19:19
That is a good question. I can use linear combination if it helps. – Wes Dec 7 '13 at 19:20

There exists $x,y \in \mathbb{Z}$, we have $ax+by=1$. Hence, $$a^2x^2 + b^2 y^2 + 2abxy = 1 \implies a^2X + bY = 1 \implies \gcd(a^2,b) = 1$$ Similarly, $(a,b^2) =1$. Hence, we have $$(a,b) = 1 \implies (a^2,b) = 1 \text{ and }(a,b^2)=1$$ Since $(a^2,b) = 1$ replacing $a$ by $a^2$ in the above argument, we have $$(a^2,b) = 1 \implies (a^4,b) = 1 \text{ and }(a^2,b^2)=1$$ And we are done.

share|cite|improve this answer
Nice. But cubing would do the trick faster than squaring. – 1015 Dec 7 '13 at 20:20

Hint: If $p$ is a prime then $p\mid a^{2}\iff p\mid a$

share|cite|improve this answer
Again, OP does not have UPF at his disposal – Tim Ratigan Dec 7 '13 at 19:20
@TimRatigan Not needed here. He can start with: If $\gcd\left(a^{2},b^{2}\right)\neq1$ then some prime $p$ must exists with $p\mid a^{2}$ and $p\mid b^{2}$. I do think he has primes at his disposal. – drhab Dec 7 '13 at 19:25
He may have primes, but I think it's even unlikely that he has every integer decomposes into a product of primes. – Tim Ratigan Dec 7 '13 at 19:32
@TimRatigan Then he should start with that immediately. This is for later. – drhab Dec 7 '13 at 19:38
I don't know, I think it's better to prove UPF in one fell swoop once you have $a|bc\land \gcd(a,b)=1\Rightarrow a|c$, which of course follows from Bezout. – Tim Ratigan Dec 7 '13 at 19:41

Use decomposition in powers of primes. If gcd$(a,b)=1$, they have no common primes in their decomposition. Now, squaring a number doesn't change the primes in the decomposition, just their exponent. If $$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$$then $$n^2=p_1^{2a_1}p_2^{2a_2}...p_k^{2a_k}$$ Therefore gcd$(a,b)=1$ if and only if gcd$(a^2,b^2)=1$

share|cite|improve this answer
OP does not want a UPF proof! – Tim Ratigan Dec 7 '13 at 19:20
@TimRatigan Answers can still be useful to people other than OP. – Daenerys Naharis Dec 7 '13 at 20:31

Here I will use the shorthand $(x,y):=\gcd(x,y)$.

$$\begin{align}1-ax&=by\\ 1-2ax+a^2x^2&=b^2y^2\\ 1-2ax&=a^2(-x^2)+b^2y^2 \end{align}$$

Note that we can write $2a^2(-x^2)+(-ax)(1-2ax)=-ax$, but $(-ax,1-2ax)=1$. Since $(-a^2x^2,1-2ax)$ divides any linear combination of the two terms inside the gcd, $(-a^2x^2,1-2ax)=1$. Similarly, $$(-a^2x^2,b^2y^2)|1-2ax\Rightarrow (-a^2x^2,b^2y^2)|(1-2ax,-a^2x^2)\Rightarrow(-a^2x^2,b^2y^2)=1$$

share|cite|improve this answer
Let's be glad that there are other ways here. – drhab Dec 7 '13 at 19:37
I'm sure there's a cleaner way to do this proof, point is that it doesn't rely on anything more than Bezout – Tim Ratigan Dec 7 '13 at 19:38
@drhab user17762 has got the right idea. I have no illusions that my proof is uglier than his or yours, only that my proof is more fundamental than yours. – Tim Ratigan Dec 7 '13 at 19:40
I think $2a^2(-x^2)+(-ax)(1-2ax)=ax$ should be replaced by $\color{red}{2a^2(-x^2)+(-ax)(1-2ax)=-ax}$ – learner Dec 9 '13 at 11:11

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