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.

Rational Round

Stage: 5 Challenge Level:

The following solution came from Alan of Madras College, St Andrew's.

Substituting

$$x = \frac{2k}{k^2 + 1}, y = \frac{k^2 - 1}{k^2 + 1}$$

we get

\eqalign{ x^2 + y^2 &= \left(\frac{2k}{k^2 + 1}\right)^2 + \left(\frac{k^2 - 1}{k^2 + 1}\right)^2 \\ \; &= \frac{(2k)^2 + (k^2 - 1)^2}{(k^2 + 1)^2} \\ \; &= \frac{4k^2 + k^4 - 2k^2 + 1}{(k^2 + 1)^2} \\ \; &= \frac{(k^2 + 1)^2}{(k^2 + 1)^2} \\ \; &= 1.}

So for every integer $k$ the point $(x,y)$ lies on the circle $x^2 + y^2 = 1$. (Note $(k^2 + 1) \neq 0$.)

Assume that it is possible for rational points to lie on the circle $x^2 +y^2 = 3$. For example $$\left(\frac{m}{n}\right)^2 + \left(\frac{k}{l}\right)^2 = 3$$ where $m$, $n$, $k$, $l$ are integers, $n$, $l \neq 0$, gcd $(m,n)$ = 1, gcd $(k,l)$ = 1. This can be rearranged to give $(ml)^2 + (kn)^2 = 3(nl)^2$ and hence

$$(ml)^2 + (kn)^2 \equiv 0 \qquad \qquad (\mbox{mod }3).$$

For any integer $q$ the only possibilities are

\eqalign{ q &\equiv 0 (\mbox{mod }3) \Rightarrow q^2 \equiv 0 (\mbox{mod }3) \\ q &\equiv 1 (\mbox{mod }3) \Rightarrow q^2 \equiv 1 (\mbox{mod }3) \\ q &\equiv 2 (\mbox{mod }3) \Rightarrow q^2 \equiv 4 \equiv 1 (\mbox{mod }3)}

So the only possible way for $(ml)^2 + (kn)^2 \equiv 0$ (mod 3) is for $(ml)^2 \equiv 0$ (mod 3) and $(kn)^2 \equiv 0$ (mod 3).

Case 1: suppose that $m \equiv 0$ (mod 3). Then $n$ not$\equiv 0$ (mod 3) because gcd $(m,n) = 1$, so that $k \equiv 0$ (mod 3). Then $l$ not $\equiv 0$ (mod 3) because gcd $(k,l)$ = 1. We write $m = 3m_1$ and $k = 3k_1$ where $m_1$ and $k_1$ are integers; then as $(ml)^2 + (kn)^2 = 3(nl)^2$ we have $$3(m_1^2l^2 +k_1^2n^2) = (nl)^2.$$ This shows that $nl \equiv 0$ (mod 3) which is a contradiction.

Case 2: suppose that $m$ not$\equiv 0$ (mod 3). Then $l \equiv 0$ (mod 3) and by the same reasoning as before we reach a contradiction.

Our assumption must be wrong, therefore no rational points lie on the circle $x^2 +y^2 = 3$.