You may also like

Double Time

Crack this code which depends on taking pairs of letters and using two simultaneous relations and modulus arithmetic to encode the message.

Modular Fractions

We only need 7 numbers for modulus (or clock) arithmetic mod 7 including working with fractions. Explore how to divide numbers and write fractions in modulus arithemtic.

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?

Purr-fection

Age 16 to 18 Challenge Level:

Peter of Madras College, St Andrew's employed an exhaustive search to find the smallest perfect square that ends in 9009 and came up with the answer 1503.

I first noted that the last digit has to be a 3 or a 7 for the square to end in 9. Noting that the last two digits of $x^2$ are only affected by the last two digits of $x$. I then systematically went through all the squares.

I kept a record of the numbers tried in two tree diagrams starting from the units digits 3 and 7. If any of these produced a number that ended in 09 then I marked that as the next branch point on the diagram.

I then went on to further generations looking for numbers ending in 009, and then finally the next generation looking for numbers ending in 9009. I found that there are no numbers with 3 digits or less whose squares end in 9009 and the four digit numbers are 1503, 6503, 2753, 7753, 2247, 7247, 3497 and 8497.

Alternatively suppose $x^2 = 100a + 10b + c$ where $a$, $b$ and $c$ are whole numbers, $a \geq 1$ and $b$ and $c$ are between 0 and 9 inclusive.



$$x^2 - 9 = (x - 3)(x + 3) = \star\star\star\star9000$$

As 10 divides the right hand side of this expression we know 10 divides $x - 3$ or $x + 3$. Thus $x$ ends in a 3 or a 7.

Case 1: c = 3

$(100a + 10b + 3)^2 = 10000a^2 + 200a(10b + 3) + 100b^2 + 60b + 9$ ends in 9009 Subtract 9, then take modulo 100.

$$\eqalign{ \Rightarrow 60b &\equiv 0 \qquad \mbox{(mod 100)}\\ \Rightarrow 3b &\equiv 0 \qquad \mbox{(mod 5)}\\ \Rightarrow b &= 0 \; or \; 5.}$$

If c = 3 and b = 0:

$(100a + 3)^2$ ends in 9009

$$\eqalign{ \Rightarrow 600a &\equiv 9000 \qquad \mbox{(mod 10000)} \\ \Rightarrow 6a &\equiv 90 \qquad \mbox{(mod 100)} \\ \Rightarrow 3a &\equiv 45 \qquad \mbox{(mod 50)} \\ \Rightarrow a &= 15 + 50k \\ \Rightarrow \mbox{smallest} \; a &= 15;\; x = 1503.}$$

If c = 3 and b = 5:

$(100a + 53)^2$ ends in 9009 $10000a^2 + 10600a + 2809$ ends in 9009 $100a^2 + 106a + 28$ ends in 90

$$\eqalign{ \Rightarrow 6a + 28 &\equiv 90 \qquad \mbox{(mod 100)} \\ \Rightarrow 3a &\equiv 31 \qquad \mbox{(mod 50)} \\ \Rightarrow 3a &= 31 + 50k \qquad \mbox{where k and a are non negative integers.} \\ \Rightarrow \mbox{smallest} \; a &= 27;\; x = 2753 \quad \mbox{which is not minimal.}}$$

Case 2: c = 7

$(100a + 10b + 7)^2 = 10000a^2 + 200a(10b + 7) + 100b^2 + 140b + 49$ ends in 9009.

$$\eqalign{ \Rightarrow 40b + 40 &\equiv 0 \qquad \mbox{(mod 100)} \\ \Rightarrow 2b + 2 &\equiv 0 \qquad \mbox{(mod 5)} \\ \Rightarrow b &= 4\; \mbox{or}\; 9}$$

In the cases $c$ = 7 and $b$ = 4 or 9 there are no solutions less than 1503.