0

Question

Let a and b be natural numbers. If $\gcd(a,b) > 1$, then $\gcd(a^2, b^2) > 1$.

My Attempt

Contradiction: If $\gcd(a,b) > 1$, then $\gcd(a^2, b^2) = 1$ (since $\gcd$ cannot be less than $1$) for any natural numbers $a$ and b.

Let $a = 2$ and $b = 4$. This implies that $gcd(a,b) = 2$ and $2 > 1$.

However, $a^2 = 4$ and $b^2 = 16$ and gcd$(a^2, b^2) = 4$ and $4$ does not equal $1$.

Therefore, we can make the argument that since the contradiction statement has a counterexample (as mentioned above), then it is not true for any set of two natural numbers a and b that satisfy the condition that gcd$(a,b) > 1$.

Thus, the initial statement is true.

Saransh Jain
  • 33
  • 1
    All you have done is proved your original statement for $a=2$ and $b=4$, not the general theorem – QC_QAOA Aug 18 '19 at 16:59
  • Please add appropriate tags, e.g. elementary-number-theory – Bill Dubuque Aug 18 '19 at 17:45
  • Hint $\ c\mid a,b,\Rightarrow, c\mid a^2,b^2\ \ $ – Bill Dubuque Aug 18 '19 at 18:22
  • 1
    The proof by contradiction is flawed from the get go. A correct attempt would be to assume there exist $a,b$ such that $\gcd(a,b)>1$ yet $\gcd(a^2,b^2)>1$. And to derive a contradiction from that. However, as others explained there is no need for a proof by contradiction. – quid Aug 18 '19 at 23:55

2 Answers2

1

You don't need a proof by contradiction for such a statement: if $d=\gcd(a,b)$, $d$ divides a, hence it trivially dids $a^2$. Similarly, it divides $b^2$, hence, it divides $\gcd(a^2, b^2)$, and it is greater than $1$…

Bernard
  • 175,478
  • I'm pretty sure that OP must have taken the problem down incorrectly. The problem was probably the converse. – Rushabh Mehta Aug 18 '19 at 17:00
  • @DonThousand: maybe the O..P. messed up among proofs by contradiction, or by contrapositive. As ir is stated, it's fairly elementary. – Bernard Aug 18 '19 at 17:45
  • @Bernard: so my solution is incorrect? – Matteo Aug 18 '19 at 18:01
  • Nor at all: it just pointed out that it's not one of the formulæ everyone is supposed to know – it depends on the O.P.'s mathematical level. – Bernard Aug 18 '19 at 18:10
0

Let $d=\gcd(a,b)$ with $d>1$. Because of the proprieties of $\gcd(a,b)$, I have: $(d\mid a) \land (d\mid b)$. Squaring, I obtain: $(d^2\mid a^2) \land (d^2\mid b^2)$. $d$ is the $\gcd(a,b)$ so also $d^2$ is the $\gcd(a^2,b^2)$. Thus $d^2>1$ and $\gcd(a^2,b^2)>1$.

Bernard
  • 175,478
Matteo
  • 6,581