Divisible by 11

Stump your fellow simians.
User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Divisible by 11

Post by DanishDynamite » Mon Aug 09, 2004 3:20 pm

Given that

a^2 + b^2 + 9ab

is divisible by 11 (a and b are whole numbers), prove that

a^2 - b^2

is also divisible by 11.

Whim
Posts: 6
Joined: Wed Jul 07, 2004 10:25 pm

Post by Whim » Mon Aug 09, 2004 8:15 pm

<table bgcolor="white"><tr><td>
Assume X = a - b

By substitution:

a^2 + (a + X)^2 + 9a(a +x)

Or:

a^2 + (a^2 + 2aX + X^2) + (9a^2 + 9aX)

Rearranging:

11a^2 + 11aX + X^2

The above equation will only be divisible by 11 when X^2 is divisible by 11. Which means X must be a factor of 11.

Factoring the second equation:

a^2 - b^2 = (a+b)(a-b) = (a+b)X

which will always be divisible by 11 when X is a factor of 11.
</td></tr></table>

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Mon Aug 09, 2004 8:44 pm

Whim wrote:<table bgcolor="white"><tr><td>
Assume X = a - b

By substitution:

a^2 + (a + X)^2 + 9a(a +x)

Or:

a^2 + (a^2 + 2aX + X^2) + (9a^2 + 9aX)

Rearranging:

11a^2 + 11aX + X^2

The above equation will only be divisible by 11 when X^2 is divisible by 11. Which means X must be a factor of 11.

Factoring the second equation:

a^2 - b^2 = (a+b)(a-b) = (a+b)X

which will always be divisible by 11 when X is a factor of 11.
</td></tr></table>
Excellent!

I'd just like to take a bit of issue with your "factor of 11" bit. 11 is a prime. It has no factors other than 1 and 11. It would be more accurate to say "is divisible by 11".

Anyway, great job!

Whim
Posts: 6
Joined: Wed Jul 07, 2004 10:25 pm

Post by Whim » Mon Aug 09, 2004 9:34 pm

I'd just like to take a bit of issue with your "factor of 11" bit. 11 is a prime. It has no factors other than 1 and 11. It would be more accurate to say "is divisible by 11".
Actually, I should have said "multiple of 11". [/quote]

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Tue Aug 10, 2004 11:05 pm

Just had another look at your proof, Whim.

You say X = a - b. You then substitute b in the original equation with (a + X). Somethings wrong with this picture.

If X = a - b, then b = a - X. I.e., b is not equal to a + X.

User avatar
Beleth
Posts: 2867
Joined: Tue Jun 08, 2004 8:55 pm
Location: That Good Night
Has thanked: 9 times
Been thanked: 6 times

Post by Beleth » Tue Aug 10, 2004 11:15 pm

DanishDynamite wrote:Just had another look at your proof, Whim.

You say X = a - b. You then substitute b in the original equation with (a + X). Somethings wrong with this picture.
I noticed that too.

X is defined to be a - b, but the equations use X as if it were equal to b - a.

This doesn't really change much; the factoring of a^2 + b^2 + 9ab comes out the same, but the factoring of a^2 - b^2 comes out to be (a+b)(-X), which still leads to essentially the same conclusion.

Whim
Posts: 6
Joined: Wed Jul 07, 2004 10:25 pm

Post by Whim » Wed Aug 11, 2004 2:15 am

Sorry, my algebra is rusty. (Or maybe it's just my brain in general that is rusty.)

Let's change that to X = b - a.

That will make b = a + X. The rest should work out the same, yes?

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Wed Aug 11, 2004 3:56 pm

Whim wrote:Sorry, my algebra is rusty. (Or maybe it's just my brain in general that is rusty.)

Let's change that to X = b - a.

That will make b = a + X. The rest should work out the same, yes?
Yes, the rest works out.

Just one last quible before I show my proof. When you said...
The above equation will only be divisible by 11 when X^2 is divisible by 11. Which means X must be [divisible by] 11.
...you didn't say why this is true. Just because X^2 is divisible by N doesn't mean X is divisible by N. For example, 6^2 = 36 is divisible by 18, but 6 is not divisble by 18. In other words, you forgot to mention that your deduction was true because 11 was a prime. :)

Anyway, here is the way I solved it:

Eq1 = a^2 + b^2 + 9ab
= a^2 + b^2 + 11ab - 2ab
= a^2 - 2ab + b^2 + 11ab
= (a-b)^2 + 11ab

Since we know Eq1 is divisible by 11, the above shows that (a-b)^2 must also be divisible by 11. As 11 is a prime, we can deduce that (a-b) is also divisible by 11.

The other equation which we need to show is divisible by 11 is:

Eq2 = a^2 - b^2
= (a+b)*(a-b)

Since (a-b) is divisible by 11 so is Eq2.

QED.