Purr-fection

What is the smallest perfect square that ends with the four digits 9009?

Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start?

Mod 7

Find the remainder when 3^{2001} is divided by 7.

Pythagoras Mod 5

Stage: 5 Challenge Level:

The problem was to prove that for every right angled triangle that has sides with integer lengths

1. the area of the triangle is even and
2. the length of one of the sides is divisible by 5.

For both parts of the problem modulus arithmetic is useful. As a hint for the first part, if $x$ is any integer then $x^2 \equiv 0,\ 1$ (mod 4), that is it leaves a remainder of 0 or 1 when divided by 4. For the second you could use the fact that $x^2 \equiv -1,\ 0$ or 1 (mod 5).

The problem was solved by Tom from Dr. Challoner's Grammar School, Amersham, Buckinghamshire.

Assume all variables are positive integers unless explicitly stated otherwise.

The sides of any triangle are given by the triple $( x , y , z )$. We only need to prove the result for primitive triples, that is in which HCF$( x , y , z )=1$. If the area of such a triangle is even and one side is a multiple of 5, then all other triangles with triples which are multiples of primitive triples must have even areas and a side which is a multiple of 5.

Say that $x^ 2 + y^ 2 = z^ 2$ and HCF$( x , y , z )=1.$ If $x$ and $y$ are both even then $z$ is also even since an even number squared is even and the sum of two even numbers is even. Hence HCF$( x , y , z )> 1$ violating our supposition. If $x$ and $z$ are even then $y$ is even by similar logic (the difference of two even numbers is even), also violating our supposition, and by symmetry $z$ and $y$ cannot both be even. If $x$ and $y$ are both odd then the sum of $x^2$ and $y^2$ is even, but of the form 2 (mod 4). Now all square numbers are of the form 1 (mod 4) or 0 (mod 4), so $z^ 2$ is no longer a perfect square, violating the supposition that $x ,\ y,\ z$ are integers.

Thus we can see that $x$ and $y$ are not both even or both odd, hence one must be even, say without loss of generality $y$, and one odd, say $x$. This implies that $z$ is odd as $x^2 + y^2 = 4( p^2 + p )+1+4q^2\equiv 1$ (mod 4).

If $z$ is odd and equal to say $2r +1$, and $x = 2p +1$ while $y= 2q$, we see that: as $x^2 + y^2 = z^2$ it follows that $(2p+1)^2 + (2q)^2 = (2r+1)^2$ so $q^2 = r(r+1) - p(p+1)$. But $p$ and $p +1$ are consecutive integers as are $r$ and $r+1$, hence one of each is even, thus $p(p +1)$ is even as is $r(r+1$ and hence $q^2$ is even which implies that $q$ is even. Thus $y$ is divisible by 4.

The area of a triangle is half base times height, that is $0.5 x y$, and as $y$ is divisible by 4, then the area of a triangle with a primitive Pythagorean triple is even, and by the logic earlier all Pythagorean triples represent triangles with even areas.

We could use similar arguments to show that one of the sides must be a multiple of 5. However it is well known (See the articles Pythagorean Triples I and Pythagorean Triples II and Picturing Pythagorean Triples) that every right angled triangle has edge lengths of the form

$$x = p^2 - q^2, \quad y=2pq \quad \rm{and}\quad z = p^2 + q^2$$

for suitable whole numbers $p$ and $q$ where $p> q$ (a result proved using similar arguments to the first part of this solution).

We have shown that $y$ is a multiple of 4 and $x$ and $z$ are odd so $p$ and $q$ have different parity.

If either $p$ or $q$ is a multiple of 5 we are finished so now consider the case that neither is a multiple of 5.

Case 1 $p$ and $q$ congruent to 1 and 2 (mod 5) .
$p^2 \pm q^2$ are congruent to 0 and 3 (mod 5).

Case 2 $p$ and $q$ congruent to 1 and 4 (mod 5).
$p^2 \pm q^2$ are congruent to 0 and 2 (mod 5).

Case 3$p$ and $q$ congruent to 3 and 2 (mod 5).
$p^2 \pm q^2$ are congruent to 0 and 3 (mod 5).

Case 4$p$ and $q$ congruent to 3 and 4 (mod 5).
$p^2 \pm q^2$ are congruent to 0 and 2 (mod 5).

In every case exactly one of the sides is a multiple of 5.
It should be noted that similar maths can be used to show that 3 divides one of $x ,\ y$ or $z$ in all primitive triples, and by the logic at the beginning 5 divides one of $x ,\ y$ or $z$ for every triple.

Other Associated Proofs

1) Every odd number greater than 1 can be put in a primitive Pythagorean triple. Take $x=2s+1$ ($s\neq 0$). We can write $p=s+1$, $q=s$ (notice that since $p$ and $q$ are consecutive they are of different parity, so the rules are obeyed.) Then $y=2s(s+1)$ and $z=2s(s+1) + 1$. For example: $3^ 2 + 4^ 2 = 5^ 2$, $5^ 2 + 12^ 2 = 13^ 2$, $7^ 2 + 24^ 2 = 25^ 2$, $9^ 2 + 40^ 2 = 41^ 2$ etc.

2) Every even number except those in which 2 occurs as a prime factor only once can be written in a primitive triple.

If your target number is even then, as we proved above it must be a multiple of 4, set $p$ to be half your target number and $q$ to be 1 then the triple is $p^2 -1$, $2p$ and $p^2 + 1$.

Thus we see that only numbers like 2,6,10,14, etc. cannot be in primitive triples since the even member of the triple must be a multiple of 4.

Note that these numbers can be in normal triples, e.g. $6^ 2 + 8^ 2 = 10^ 2$ .