Valid argument for Number Theory problem.

Given natural numbers a and b such that a^2 +b^2 is divisible by 21, prove that the same sum of squares is also divisible by 441.

I am not sure if this is a valid argument can someone please comment on the quality of this solution:

Since a^2 +b^2 is divisible by 21 a^2 +b^2 must be divisible by 3 and by 7.

So we must have $a^2 + b^2 = 3k$ for some integer k. Therefore a^2/3 + b^2/3 = k and since a and b are natural numbers and k is an integers it follows that 3|a and 3|b, therefore 9 divides a^2 and b^2.

The same reasoning can be used to deduce that 7|a and 7|b and so 49 divides a^2 and b^2.

Since 49 divides a^2 and b^2 it must divide a^2 + b^2. Since 9 divides a^2 and b^2 it must divide a^2+b^2.

Since a^2+b^2 is divisible by 49 and 9 and gcd(49,9) = 1, a^2+b^2 must be divisible by 441.

Reply 1

RichE

Original post by FXLander

So we must have $a^2 + b^2 = 3k$ for some integer k. Therefore a^2/3 + b^2/3 = k and since a and b are natural numbers and k is an integers it follows that 3|a and 3|b, therefore 9 divides a^2 and b^2.

Your reasoning is dodgy here. You need to think what remainders squares can leave mod 3. Certainly 1+2 is divisible by 3 without 1 and 2 being divisible by 3. You need to show this can't happen though when we're discussed squares.

Reply 2

FXLander

Original post by RichE

The remainders a square can leave mod 3 are 0 or 1. So in order for a^2 +b^2 to be 0 mod 3, both a^2 and b^2 must be divisible by 3. But how do I show that 9|a^2 and 9|b^2?

Reply 3

RichE

Original post by FXLander

The remainders a square can leave mod 3 are 0 or 1. So in order for a^2 +b^2 to be 0 mod 3, both a^2 and b^2 must be divisible by 3. But how do I show that 9|a^2 and 9|b^2?

If a^2 is a multiple of 3 what can you say about a?

Reply 4

FXLander

Original post by RichE

If a^2 is a multiple of 3 what can you say about a?

If a^2 is a multiple of 3 then a^2 = 3k for some integer k. So a = sqrt(3k). Now since a is a natural number we must have k = 3m^2 for some integer m. Therefore a = 3m, and a is a multiple of three so 9|a^2.

Reply 5

Zacken

Original post by FXLander

That works, but a little stronger than you need. Are you familiar with Euclids Lemma? That gives you 3 | a^2 => 3 | a immediately.

Reply 6

FXLander

Original post by Zacken

That works, but a little stronger than you need. Are you familiar with Euclids Lemma? That gives you 3 | a^2 => 3 | a immediately.

I didn't think of that! When using a lemma in a proof, do you just write something like: "Since 3|a^2, 3|a by Euclid's Lemma..."

Reply 7

Zacken

Original post by FXLander

I didn't think of that! When using a lemma in a proof, do you just write something like: "Since 3|a^2, 3|a by Euclid's Lemma..."

That's fine, yeah.

Reply 8

FXLander

So here is my corrected proof:

Since a^2+b^2 is divisible by 21, a^2 + b^2 must be divisible by 3 and by 7.

The possible residues a square number can leave mod 3 are: 0,1. It follows that a^2 and b^2 must both be divisible by 3.

The possible residues a square number can leave mod 7 are: 0,1,2,4. It follows that a^2 and b^2 must both be divisible by 7.

Using Euclid's Lemma 3|a^2 => 3|a and 7|a^2=>7|a. The same can be shown for b.

Therefore 9|a^2,b^2 and 49|a^2,b^2.

Since 49 divides a^2 and b^2 it must divide a^2+b^2. Since 9 divides a^2 and b^2 it must divide a^2 +b^2.

Finally because a^2 +b^2 is divisible by 9 and 49 it must also be divisible by 9*49 =441.

Reply 9

Zacken

Original post by FXLander

Finally because a^2 +b^2 is divisible by 9 and 49 it must also be divisible by 9*49 =441.

Well, 3 | 12 and 6 | 12 but 3 * 6 doesn't divide 12. You ought to mention gcd(9,49) = 1.

Reply 10

Integer123

Original post by RichE

If a^2 is a multiple of 3 what can you say about a?

Is a possible way to say that if a^2 has a factor of 3 then since a is an integer and 3 is prime, it cannot be created via squaring to appear in a^2 without already being in a, and so a is also a multiple of 3?