Categories

# Number of ordered triples – Duke Math Meet 2009 Team Round Problem 7 solution

How many ordered triples of integers (a, b, c) are there such that $1 \le a, b, c \le 70$ and $a^2 + b^2 + c^2$ is divisible by 28.

Any square quantity is 0 or 1 modulo 4

Now sum of three square quantities are 0 or 1 mod 4. Since 28 is 0 mod 4, there fore none of the three squares can be 1 mod 4.

Thus a, b, c are even.

Again a square quantity is always 0, 1, 4, 2 mod 7

Since we want the three squares to add up to 0 mod 7 (28 is 0 mod 7), the possibilities are (0, 0, 0) mod 7 and (1, 4, 2) mod 7

So we have following cases:

Case 1

a, b, c are all even multiples of 7. There are 5 of them. Since we are looking for ordered triplet there are $5^3 = 125$ of these\$

Case 2

a, b, c are all even numbers. with 1, 6 mod 7, 2 , 5 mod 7 and 3, 4 mod 7

1 mod 7 – 10 elements
6 mod 7 – 10 elements

Hence there are 20 numbers which are 1 or 6 mod 7. 10 of these are even.

Similarly there are 20 numbers which are 2 or 5 mod 7 and 20 numbers which are 3 or 4 mod 7. Half of each of which we will take.

So 10 choices for each set. $10^3 = 1000$ choices. Now since we are taking ordered pairs, we must consider all the 3! = 6 permutations. So there are 6000 cases.

Hence answer is 6000 + 125 = 6125

## By Ashani Dasgupta

Ph.D. in Mathematics from University of Wisconsin Milwaukee (USA)
Founder - Faculty at Cheenta