Divisibility, Primes and Congruences

Problems

Solutions

Solution: PRMO 2013, Q1

Add the three cubes: $$27 + 64 + 125 = 216 = 6^3.$$ So $k = 1$ works, with $a = 6$ and $n = 3$, and no smaller positive integer exists.

The identity $3^3 + 4^3 + 5^3 = 6^3$ is worth remembering. It is the smallest instance of four cubes in that relation, and it is what the question is really about: a reader who starts factorising $216$ into $2^3 \cdot 3^3$ arrives at the same place a moment later.

Answer 1

Solution: PRMO 2014, Q1

The squares nearest $2014$ are $44^2 = 1936$ and $45^2 = 2025$, and $$1936 < 2014 < 2025,$$ so $k = 44$ and no other natural number will do, the squares being increasing.

Factorising, $44 = 2^2 \times 11$, so the largest prime factor is $11$.

Answer 11

Solution: IOQM 2024, Q1

Write $9! = 362880$ in terms of its primes: $$9! = 2^7 \cdot 3^4 \cdot 5 \cdot 7.$$ Any integer whose prime factorisation fits inside this one divides $9!$, and the integers $1$ through $10$ all do: for instance $8 = 2^3$ and $9 = 3^2$ and $10 = 2 \cdot 5$ are covered comfortably. But $11$ is a prime that does not appear in the list at all, so it cannot divide $9!$.

Hence the smallest positive integer that does not divide $9!$ is $11$.

Answer 11

Solution: IOQM 2025 Part SEP, Q7

The multiples of $3$ up to $100$ are $3, 6, \ldots, 99$, and there are $\lfloor 100/3 \rfloor = 33$ of them. Among these, the ones divisible by $2$ are exactly the multiples of $6$, of which there are $\lfloor 100/6 \rfloor = 16$.

So the count is $33 - 16 = 17$.

Answer 17

Solution: IOQM 2025 Part SEP, Q28

A positive integer divisible by no prime other than $2$ and $3$ is precisely one of the form $2^i 3^j$ with $i, j \ge 0$, and $n = 1$ counts, since it has no prime divisor at all. Listing them by the power of $3$: $$\begin{array}{r|l|c} 3^j & \text{numbers } 2^i3^j \le 100 & \text{count} \\ \hline 1 & 1, 2, 4, 8, 16, 32, 64 & 7 \\ 3 & 3, 6, 12, 24, 48, 96 & 6 \\ 9 & 9, 18, 36, 72 & 4 \\ 27 & 27, 54 & 2 \\ 81 & 81 & 1 \end{array}$$ There are $7+6+4+2+1 = 20$ of them.

Answer 20

Solution: IOQM 2026, Q2

Write $M = 256q + r$ with $0 \le r \le 255$. Then $r = M - 256q$ is a difference of two multiples of $4$, so $r$ is a multiple of $4$. And $r \ne 0$, since $r = 0$ would make $M$ a multiple of $256$.

So $r$ is one of $4, 8, 12, \ldots, 252$, and every one of these really occurs, because $M = r$ is divisible by $4$ and not by $256$. The list runs from $4 \cdot 1$ to $4 \cdot 63$, so there are $63$ possible remainders.

Answer 63

Solution: PRMO 2015 Part A, Q4

For example, take $P(x)=x^2+5$: $P(3)-P(1)=14-6=8$ is divisible by $3-1=2$. The constant cancels, and the same factorisation principle works term by term for any integer polynomial.

The tool here is a fact about polynomials with integer coefficients: for any integers $u$ and $v$, the difference $u - v$ divides $P(u) - P(v)$. It follows from $u^k - v^k = (u - v)(u^{k-1} + u^{k-2}v + \cdots + v^{k-1})$ applied term by term, and the coefficients being integers is exactly what makes the resulting factorisation an integer one.

Take $v = 0$. Then $n$ divides $P(n) - P(0)$ for every positive integer $n$. We are told that $n$ also divides $P(n)$, so subtracting, $$n \mid P(0) \qquad \text{for every positive integer } n.$$ Now $P(0)$ is one fixed integer, and no non-zero integer is divisible by every positive integer, since $n$ larger than $|P(0)|$ would already be too big. Therefore $P(0) = 0$.

Note that the condition "$P$ is non-zero" is there to keep the polynomial itself interesting, not to rescue the argument: $P(x) = x$ is a perfectly good example, and its value at $0$ is indeed $0$.

Answer 0

Solution: PRMO 2019, Q4

At each stop the ant turns $160^{\circ}$ to the right, so the angle between the leg it arrives on and the leg it leaves on, measured inside the path, is $180^{\circ} - 160^{\circ} = 20^{\circ}$.

Every stop lies on one circle

Call the anthill $A_0$ and the stops $A_1, A_2, \ldots$ in the order the ant reaches them. Draw the circle through $A_0$, $A_1$ and $A_2$, and let $O$ be its centre. Equal chords of a circle subtend equal angles at the centre, and $A_0A_1 = A_1A_2 = 4$, so the rotation about $O$ that carries $A_0$ to $A_1$ also carries $A_1$ to $A_2$. That is, it carries the first leg of the walk to the second.

The same rotation carries the second leg to the third, because the third leg stands to the second exactly as the second stands to the first: the same length, turned right through the same $160^{\circ}$. Repeating the argument, one fixed rotation about $O$ carries every leg to the next. So every stop lies on that one circle, and consecutive stops are the same distance apart round it.

How far round the circle one leg goes

The angle $\angle A_0A_1A_2 = 20^{\circ}$ stands at the circumference on the arc $A_0A_2$ that does not contain $A_1$, so that arc measures $40^{\circ}$. The rest of the circle, which is $360^{\circ} - 40^{\circ} = 320^{\circ}$, is the arc from $A_0$ to $A_2$ the other way round, through $A_1$, and it is made of two equal steps. Each leg therefore advances the ant $160^{\circ}$ round the circle.

When the ant gets home

After $n$ legs the ant has gone $160n$ degrees round the circle, and it is back at the anthill exactly when that is a whole number of complete laps: $$360 \mid 160n, \qquad\text{which after dividing by } 40 \text{ reads}\qquad 9 \mid 4n.$$ Since $4$ and $9$ share no factor, $9$ must divide $n$, so the first return is at $n = 9$ and the ant walks $$9 \times 4 = 36$$ feet. Nine steps of $160^{\circ}$ come to $1440^{\circ}$, which is four laps, so the ant circles the anthill four times before closing up. The nine stops are equally spaced round the circle, $40^{\circ}$ apart, and the ant visits every fourth one: that is the nine-pointed star in the figure.

Answer 36

Solution: PRMO 2019, Q14

Write $9n + 7 = m^2$ with $m$ a positive integer. Reducing modulo $9$, $$m^2 \equiv 7 \pmod 9.$$ The squares modulo $9$ are $0, 1, 4, 7$, and $m^2 \equiv 7$ happens exactly for

$m \equiv 4$ or $m \equiv 5 \pmod 9$, since $4^2 = 16 \equiv 7$ and $5^2 = 25 \equiv 7$ while the other remainders give $0, 1$ or $4$.

So $m \in \{4, 5, 13, 14, 22, 23, \ldots\}$, and $n = (m^2 - 7)/9$ grows with $m$. Running through them in order and keeping only $n \ge 10$: $$m = 13:\ n = 18, \qquad m = 14:\ n = 21, \qquad m = 22:\ n = 53,$$ the values $m = 4, 5$ giving $n = 1, 2$, which are too small.

Now test the primality of $n + 6$ in that order. For $n = 18$ we get $24 = 2^3 \cdot 3$, not prime. For $n = 21$ we get $27 = 3^3$, not prime. For $n = 53$ we get $59$, which is prime, since it is divisible by none of $2$, $3$, $5$, $7$ and $7^2 = 49 < 59 < 64$. Also $9 \times 53 + 7 = 484 = 22^2$, as required.

The smallest such $n$ is $53$.

Answer 53

Solution: IOQM 2020, Q6

The expression is disguised by its composite bases, and the first move is to rewrite everything in terms of the primes $2$, $3$ and $5$. Since $4 = 2^2$ and $6 = 2 \cdot 3$, $$2^5 \cdot 3^6 \cdot 4^3 \cdot 5^3 \cdot 6^7 = 2^5 \cdot 3^6 \cdot 2^6 \cdot 5^3 \cdot 2^7 \cdot 3^7 = 2^{18} \cdot 3^{13} \cdot 5^{3}.$$

Now the criterion does all the work. A number is a perfect square precisely when each prime occurs to an even power, because a square is a product of two identical factorisations. Here the exponent of $2$ is already even and needs nothing, while the exponents of $3$ and of $5$ are both odd and each needs one more copy of its prime.

Multiplying by $3 \cdot 5 = 15$ therefore does the job, giving $2^{18} \cdot 3^{14} \cdot 5^4$. Nothing smaller can work, because any successful multiplier must supply at least one factor of $3$ and at least one factor of $5$, and the smallest positive integer doing both is $15$.

Answer 15

Solution: IOQM 2020, Q17

For a small example, $12=2^2\cdot3$ has divisors $1,2,3,4,6,12$. We choose the exponent of $2$ in three ways and the exponent of $3$ in two ways, giving $3\cdot2=6$ divisors. This is the pattern behind the divisor-count formula.

The number of divisors of $n = p_1^{e_1} p_2^{e_2} \cdots$ is $(e_1+1)(e_2+1)\cdots$, since a divisor is built by choosing an exponent for each prime independently. For that product to equal $4$ there are only two ways to break $4$ into factors bigger than one, namely $4$ itself and $2 \times 2$. The first gives a single prime with exponent $3$, so $n = p^3$; the second gives two distinct primes each with exponent $1$, so $n = pq$. Every two-digit number with exactly four divisors is therefore of one of these two shapes, and we count each.

The cubes are quickly exhausted. Since $2^3 = 8$ has only one digit and $5^3 = 125$ has three, the only two-digit cube of a prime is $3^3 = 27$.

For the products of two distinct primes, fix the smaller prime and list the larger one: $$\begin{array}{c|l|c} p&\text{possible }q>p\text{ with }10\le pq\le99&\text{count}\\\hline 2&5,7,11,13,17,19,23,29,31,37,41,43,47&13\\ 3&5,7,11,13,17,19,23,29,31&9\\ 5&7,11,13,17,19&5\\ 7&11,13&2 \end{array}$$ There is no row with smaller prime $11$ or above, since $11\cdot13=143$ already exceeds two digits. Adding up, the products contribute $13 + 9 + 5 + 2 = 29$, and the single cube contributes one more, for a total of $30$.

Answer 30

Solution: IOQM 2021 Part A, Q3

We want three distinct primes in arithmetic progression which can be the sides of a genuine triangle, and among all such triples we want the one of least perimeter, so start small and work up. The smallest candidates are $3, 5, 7$, whose common difference is $2$, and they do form a triangle since $3 + 5 > 7$. Nothing smaller is available. These are the three smallest odd primes, so no triple of odd primes has a smaller sum, and a progression using $2$ must have $2$ as its smallest term, since no prime is smaller, so its terms are $2$, $2+d$, $2+2d$, and the largest of those is even and exceeds $2$, so it is not prime. The least perimeter is therefore $L = 3 + 5 + 7 = 15$.

The largest angle lies opposite the longest side, $7$. By the cosine rule, $$\cos\theta = \frac{3^2 + 5^2 - 7^2}{2 \cdot 3 \cdot 5} = \frac{9 + 25 - 49}{30} = \frac{-15}{30} = -\frac12,$$ so $\theta = 120^{\circ}$ and $a = 120$. The clean value of the cosine is a sign that this triple was chosen deliberately.

Therefore $\dfrac{a}{L} = \dfrac{120}{15} = 8$.

Answer 8

Solution: IOQM 2023, Q6

A regular polygon with $k \ge 3$ sides has interior angle $$n = 180 - \frac{360}{k}.$$ Write $d = 360/k$. For $n$ to be an integer, $d$ must be an integer, that is $k$ must divide $360$, and then $d$ is itself a divisor of $360$; and since $180$ is even, $n$ is even exactly when $d$ is even. The constraint $k \ge 3$ becomes $d = 360/k \le 120$, and $n > 0$ is then automatic.

So the task is to count the even divisors of $360$ that are at most $120$. Since $360 = 2^3 \cdot 3^2 \cdot 5$ has $4 \cdot 3 \cdot 2 = 24$ divisors, of which the odd ones are the $3 \cdot 2 = 6$ divisors of $45$, there are $24 - 6 = 18$ even divisors. Exactly two of them exceed $120$, namely $180$ and $360$. That leaves $$18 - 2 = 16$$ admissible values of $d$, and distinct values of $d$ give distinct angles $n = 180 - d$.

A remark on the wording, since it worries people. If "the angle of a regular polygon" were read as the exterior angle $360/k$ instead, the count would be of even divisors of $360$ that are at most $120$ once more, and the answer would be the same $16$. The ambiguity is harmless.

Answer 16

Solution: IOQM 2025 Part SEP, Q28

A sum as large as $240$ from four numbers none above $70$ needs every one of them near the top, so look at the largest primes not exceeding $70$: they are $67, 61, 59, 53, 47, \ldots$, and $$67 + 61 + 59 + 53 = 240$$ exactly. Any other choice of four distinct primes below $70$ replaces one of these by a smaller prime and gives a total below $240$.

So the four primes are forced, and the smallest is $53$.

Answer 53

Solution: IOQM 2025 Part SEP, Q28

The condition involves every $i$ with $i^3 \le n$, and that set of $i$ grows only when $n$ passes a cube. $$\begin{array}{c|c|c|c} \text{range} & \text{divisors } i & \text{multiple of} & \text{count} \\ \hline 1 \le n \le 7 & 1 & 1 & 7 \\ 8 \le n \le 26 & 1, 2 & 2 & 10 \\ 27 \le n \le 63 & 1,2,3 & 6 & 6 \\ 64 \le n \le 100 & 1,2,3,4 & 12 & 3 \end{array}$$ The counts in the last column are the multiples in each range: $8, 10, \ldots, 26$ gives ten numbers; $30, 36, \ldots, 60$ gives six; and $72, 84, 96$ gives three.

The total is $7 + 10 + 6 + 3 = 26$.

Answer 26

Solution: PRMO 2012, Q11

At $n=2$ the factors are $3,5,7,9,11$. They visibly supply both $3$ and $5$, but we must ask which of those factors remain compulsory as the run moves. That question is about the remainders of consecutive odd numbers.

For even $n$ the five factors $n+1, n+3, n+5, n+7, n+9$ are five consecutive odd numbers.

Among any three consecutive odd numbers the remainders modulo $3$ run through all three possibilities, so one of them is a multiple of $3$. Among any five consecutive odd numbers the remainders modulo $5$ likewise run through all five, so one is a multiple of $5$. Hence $15$ divides $P(n)$ always.

Any integer dividing every product must divide the HCF of any samples we choose. We use products that leave different small primes out, so their common factors can be tested. Take $n = 10$ and $n = 12$: $$P(10) = 11 \cdot 13 \cdot 15 \cdot 17 \cdot 19, \qquad P(12) = 13 \cdot 15 \cdot 17 \cdot 19 \cdot 21.$$ The first is $3 \cdot 5 \cdot 11 \cdot 13 \cdot 17 \cdot 19$ and the second is $3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 19$, whose greatest common divisor is $3 \cdot 5 \cdot 13 \cdot 17 \cdot 19$. Bringing in $P(2) = 3 \cdot 5 \cdot 7 \cdot 9 \cdot 11$ kills the $13$, $17$ and $19$, leaving $15$.

So the answer is $$15.$$

Answer 15

Solution: PRMO 2012, Q16

First $f(1) = f(1 \cdot 1) = f(1)^2$, and the only natural number equal to its own square is $1$, since the natural numbers here start at $1$. So $f(1) = 1$, and $f(2) = 2$ gives $f(4) = 4$, $f(8) = 8$, $f(16) = 16$, and in general $f(2^k) = 2^k$.

Now squeeze. Between $f(2) = 2$ and $f(4) = 4$ there is room for exactly one value, and $f$ is strictly increasing, so $f(3) = 3$. Between $f(4) = 4$ and $f(8) = 8$ there are three integers and three values $f(5) < f(6) < f(7)$ to place, so $f(5) = 5$, $f(6) = 6$, $f(7) = 7$. The same argument between $8$ and $16$, where seven values must fill seven places, gives $f(n) = n$ for $n = 9, \ldots, 15$, and once more between $16$ and $32$ for $n$ up to $20$.

So $f$ is the identity on the range we need, and $$\sum_{k=1}^{20} f(k) = \sum_{k=1}^{20} k = \frac{20 \times 21}{2} = 210.$$

The three conditions are exactly enough: drop the increasing condition and any rearrangement of the odd primes would do, drop $f(2) = 2$ and $f(n) = n^2$ would do.

Answer 210

Solution: PRMO 2013, Q18

Writing the run as $a, a+1, \ldots, a+k-1$ with $a \ge 1$, $$ka + \frac{k(k-1)}{2} = 2013, \qquad \text{that is} \qquad k\left(2a + k - 1\right) = 4026.$$ So $k$ divides $4026 = 2 \times 3 \times 11 \times 61$.

The requirement $a \ge 1$ caps $k$: $$2a = \frac{4026}{k} - k + 1 \ge 2 \implies k(k+1) \le 4026 \implies k \le 62.$$

The divisors of $4026$ at most $62$ are $1, 2, 3, 6, 11, 22, 33, 61$, and the largest is $61$. It works: $\tfrac{4026}{61} = 66$, so $2a = 66 - 61 + 1 = 6$ and $a = 3$. Indeed $$3 + 4 + \cdots + 63 = \frac{(3 + 63) \times 61}{2} = 2013.$$

So the maximum is $k = 61$.

Answer 61

Solution: PRMO 2014, Q11

Put $d = \gcd(x,y)$ and $x = da$, $y = db$ with $\gcd(a,b) = 1$ and $a \le b$. The equation $xy = x + y + \gcd(x,y)$ becomes $$d^2ab = d(a + b) + d, \qquad \text{so} \qquad d\,ab = a + b + 1.$$

In particular $ab$ divides $a + b + 1$, so $ab \le a + b + 1$, that is $$(a-1)(b-1) \le 2.$$ With $a \le b$ and $\gcd(a,b) = 1$ that leaves $a = 1$ with any $b$, or $(a,b) = (2,3)$.

• $a = 1$: the condition is $b \mid b + 2$, so $b \mid 2$ and $b \in \{1, 2\}$. For $b = 1$, $d = 3$ gives $(x,y) = (3,3)$; for $b = 2$, $d = \tfrac42 = 2$ gives $(x,y) = (2,4)$.

• $(a,b) = (2,3)$: then $6d = 6$, so $d = 1$ and $(x,y) = (2,3)$.

All three check out: $9 = 3+3+3$, $8 = 2+4+2$ and $6 = 2+3+1$. So there are $3$ pairs.

Answer 3

Solution: PRMO 2014, Q13

Put $d = 9999 - n$, so that $n = 9999 - d$ and $$\frac{8n}{9999-n} = \frac{8(9999 - d)}{d} = \frac{79992}{d} - 8.$$ The expression is an integer exactly when $d$ divides $79992 = 2^3 \times 3^2 \times 11 \times 101$.

Now use the range. As $n$ runs from $1$ to $2014$, the number $d$ runs from $9998$ down to $7985$. Writing $79992 = qd$, the bounds on $d$ become bounds on $q$: $$q = \frac{79992}{d} \in \left[\frac{79992}{9998},\ \frac{79992}{7985}\right] = [8.001\ldots,\ 10.01\ldots],$$ so $q$ is $9$ or $10$. Of these only $9$ divides $79992$, since $79992$ is not a multiple of $5$. That gives $$d = \frac{79992}{9} = 8888, \qquad n = 9999 - 8888 = 1111,$$ and indeed $\tfrac{8 \times 1111}{8888} = 1$.

So exactly $1$ value of $n$ works.

Answer 1

Solution: PRMO 2015 Part A, Q13

We need $n = x \cdot y \cdot (10x+y)$ with $x$, $y$ and $10x + y$ three distinct primes, and $x$, $y$ single digits. A single-digit prime is one of $2, 3, 5, 7$, which cuts the search down to sixteen pairs before any thought at all.

So run through the four values of $x$, and for each list which of the four numbers $10x + y$ is prime. With $x = 7$, for instance, the candidates are $72$, $73$, $75$ and $77$, and only $73$ is prime. Every value of $x$ turns out to leave exactly one choice of $y$: $$\begin{array}{c|c|c|c} x & 10x + y \text{ prime} & y & n = x \cdot y \cdot (10x+y) \\ \hline 2 & 23 & 3 & 138 \\ 3 & 37 & 7 & 777 \\ 5 & 53 & 3 & 795 \\ 7 & 73 & 3 & 1533 \end{array}$$ In each row the three primes are distinct, as required.

The largest is $n = 1533$, and the sum of its digits is $1 + 5 + 3 + 3 = 12$.

Answer 12

Solution: PRMO 2018, Q22

The whole set sums to $1 + 2 + \cdots + 20 = 210$. If the parts each sum to $k$ then $k$ divides $210$.

Two more constraints trim the list. The part containing $20$ has sum at least $20$, so $k \ge 20$. And the subsets must be proper, so there is more than one of them, which rules out $k = 210$.

The divisors of $210 = 2 \cdot 3 \cdot 5 \cdot 7$ lying in $[20, 210)$ are $$21, \quad 30, \quad 35, \quad 42, \quad 70, \quad 105,$$ six of them. Each is genuinely achievable, and here is a splitting for each:

• $k = 21$: the ten pairs $\{1,20\}, \{2,19\}, \ldots, \{10,11\}$.

• $k = 30$: $\{20,10\}$, $\{19,11\}$, $\{18,12\}$, $\{17,13\}$, $\{16,14\}$, $\{15,9,6\}$, $\{1,2,3,4,5,7,8\}$.

• $k = 35$: $\{20,15\}$, $\{19,16\}$, $\{18,17\}$, $\{14,13,8\}$, $\{12,11,10,2\}$, $\{1,3,4,5,6,7,9\}$.

• $k = 42$: $\{20,19,3\}$, $\{18,17,7\}$, $\{16,15,11\}$, $\{14,13,12,2,1\}$, $\{10,9,8,6,5,4\}$.

• $k = 70$: $\{20,19,18,13\}$, $\{17,16,15,14,8\}$, and everything else.

• $k = 105$: $\{20,19,18,17,16,15\}$ and $\{1,2,\ldots,14\}$.

So there are $6$ good numbers.

Answer 6

Solution: PRMO 2019, Q21

A prime larger than $2$ is odd, and the two products here are both at least $5$, so their sum must be odd. A product is odd exactly when every factor is odd, so exactly one of the two parts consists of odd numbers only, that is one part is a non-empty subset of $\{5, 7, 9\}$ and the other contains both $6$ and $8$.

That leaves seven splittings, and each is one multiplication:

$$\begin{array}{lrl} A = \{5\}: & 5 + 6\cdot7\cdot8\cdot9 = 3029 & = 13 \times 233 \\ A = \{7\}: & 7 + 5\cdot6\cdot8\cdot9 = 2167 & = 11 \times 197 \\ A = \{9\}: & 9 + 5\cdot6\cdot7\cdot8 = 1689 & = 3 \times 563 \\ A = \{5,7\}: & 35 + 6\cdot8\cdot9 = 467 & \text{prime} \\ A = \{5,9\}: & 45 + 6\cdot7\cdot8 = 381 & = 3 \times 127 \\ A = \{7,9\}: & 63 + 5\cdot6\cdot8 = 303 & = 3 \times 101 \\ A = \{5,7,9\}: & 315 + 6\cdot8 = 363 & = 3 \times 121 \end{array}$$

Four of the composites are caught by the digit-sum test for $3$, and the two larger ones need a moment: $3029 = 13 \times 233$ and $2167 = 11 \times 197$. As for $467$, it is prime because it is divisible by none of $2, 3, 5, 7, 11, 13, 17, 19$, and $22^2 = 484$ already exceeds it.

So the only prime among these numbers is $N = 467$, which is therefore also the largest, and its digits sum to $4 + 6 + 7 = 17$.

Answer 17

Solution: IOQM 2020, Q14

Begin by factorising the product completely, since a question about writing a number as a product of integers is really a question about how its primes may be distributed: $$55 \times 60 \times 65 = (5 \cdot 11)(2^2 \cdot 3 \cdot 5)(5 \cdot 13) = 2^2 \cdot 3 \cdot 5^3 \cdot 11 \cdot 13.$$

Now suppose, aiming for a contradiction, that all five integers could be kept at $19$ or below. The prime $11$ has to divide one of them, and the only multiple of $11$ that does not exceed $19$ is $11$ itself, so one of the five is exactly $11$; the same reasoning with $13$ pins down a second. Dividing them out leaves three distinct integers whose product is $$\frac{214500}{11 \cdot 13} = 1500 = 2^2 \cdot 3 \cdot 5^3.$$

Those three must carry $5^3$ between them, and none of them can be divisible by $25$, since $25$ already exceeds $19$. Each of the three is therefore divisible by $5$ exactly once, which forces all three to be drawn from $5$, $10$ and $15$, the only multiples of $5$ below $20$ that are not multiples of $25$. Their product is $750$, not $1500$, and the contradiction is complete.

So the largest integer must be at least $20$, and $20$ is attainable: $$5 \times 11 \times 13 \times 15 \times 20 = 214500,$$ with all five factors distinct. The least possible value of the largest is $20$.

Answer 20

Solution: IOQM 2020, Q28

A few small cases show the pattern before any algebra. We have $3 = 1 + 2$, $5 = 2 + 3$, $6 = 1 + 2 + 3$, $9 = 4 + 5$, $10 = 1 + 2 + 3 + 4$ and $12 = 3 + 4 + 5$, but $1$, $2$, $4$ and $8$ resist every attempt. The numbers that resist are the powers of two, and the algebra explains why.

Suppose $n$ is the sum of $r$ consecutive positive integers starting at $m$, with $r \geq 2$. Summing the progression, $$n = m + (m+1) + \cdots + (m+r-1) = \frac{r\left(2m + r - 1\right)}{2},$$ so that $2n = r\left(2m + r - 1\right)$. Read that as it stands: a run of consecutive integers is the number of terms times twice their average, and the useful part is that one of those two factors has to be odd, whatever $n$ is.

Look at the two factors on the right. Their sum is $2m + 2r - 1$, which is odd, so exactly one of $r$ and $2m+r-1$ is even and the other is odd. Since $r \geq 2$ and $m \geq 1$, both factors are at least $2$. So $2n$ has been written as a product of an even number and an odd number greater than one, which means $n$ itself has an odd divisor greater than $1$.

Conversely, suppose $n$ is not a power of two, and write $$n = 2^s q, \qquad q > 1 \text{ odd}.$$ Since $q$ is odd and $2^{s+1}$ is even the two are never equal, so exactly one of the following two constructions applies.

If $q < 2^{s+1}$, take the $q$ consecutive integers centred at $2^s$, namely $$2^s - \frac{q-1}{2}, \quad \ldots, \quad 2^s + \frac{q-1}{2}.$$ There are $q$ of them and their average is $2^s$, so they sum to $2^s q = n$. They are positive because $q$ is odd and less than $2^{s+1}$, so $q \leq 2^{s+1} - 1$ and the first term is at least $1$. And $q \geq 3$, so there are at least two terms.

If $q > 2^{s+1}$, take instead the $2^{s+1}$ consecutive integers starting at $$m = \frac{q - 2^{s+1} + 1}{2},$$ which is a whole number because $q$ is odd, and is positive because $q \geq 2^{s+1} + 1$. Their sum is $$2^{s+1} m + \bigl(0 + 1 + \cdots + (2^{s+1} - 1)\bigr) = 2^s\bigl(q - 2^{s+1} + 1\bigr) + 2^s\bigl(2^{s+1} - 1\bigr),$$ and the two brackets add to $q$, leaving $2^s q = n$.

So the numbers that are not good are exactly those with no odd divisor beyond $1$, which is to say the powers of two.

In the range from $1$ to $100$ the powers of two are $1, 2, 4, 8, 16, 32, 64$, seven numbers in all. Every other number in the range is good, so the count is $100 - 7 = 93$.

Answer 93

Solution: IOQM 2022, Q7

Write $g = \gcd(a,b)$ and $a = gx$, $b = gy$ with $\gcd(x,y) = 1$, so that $\mathrm{LCM}(a,b) = gxy$. The condition becomes $$g + gxy = gx + gy.$$ Dividing by $g$ and rearranging, $xy - x - y + 1 = 0$, that is $$(x-1)(y-1) = 0.$$

So $x = 1$ or $y = 1$, which means $a \mid b$ or $b \mid a$. The whole gcd-and-lcm dressing was hiding a divisibility condition.

Now count ordered pairs from $\{10, 11, \ldots, 30\}$. The pairs with $a = b$ number $21$, one for each value. For the strictly ordered ones, list the pairs $a < b$ with $a \mid b$: since $b \leq 30$ and $a \geq 10$, the quotient can only be $2$ or $3$, giving $$(10,20),\ (10,30),\ (11,22),\ (12,24),\ (13,26),\ (14,28),\ (15,30),$$ which is $7$ pairs, and each contributes two ordered pairs.

The total is $21 + 2 \cdot 7 = 35$.

Answer 35

Solution: IOQM 2023, Q9

A prime has exactly two positive divisors, so if $ab$ is prime then one of $a, b$ equals $1$ and the other is that prime. Condition (c) says $abc$ is squarefree, so all the primes appearing below are distinct. Take the two cases in turn.

Case $b = 1$, $a = p$ prime. Then $bc = c$, and condition (b) says $c$ is a product of two primes, say $c = qr$. Squarefreeness makes $p$, $q$, $r$ three distinct primes, and (d) requires $pqr \le 30$. The smallest product of three distinct primes is $2 \cdot 3 \cdot 5 = 30$, so that is the only possibility, and the three triples are obtained by choosing which prime plays the role of $a$: $$(2, 1, 15), \quad (3, 1, 10), \quad (5, 1, 6).$$ That is $3$ triples.

Case $a = 1$, $b = p$ prime. Then $bc = pc$ must be a product of two primes, which forces $c$ to be a prime $q$, distinct from $p$ by squarefreeness. Condition (d) reads $pq \le 30$. The unordered pairs of distinct primes with product at most $30$ are $$\{2,3\},\ \{2,5\},\ \{2,7\},\ \{2,11\},\ \{2,13\},\ \{3,5\},\ \{3,7\},$$ seven in all, since $3 \cdot 11 = 33$ and $5 \cdot 7 = 35$ already exceed $30$. Here $b$ and $c$ play different roles, so each pair gives two triples, making $14$.

The cases cannot overlap, since $a = b = 1$ would make $ab = 1$, which is not prime. The total is $3 + 14 = 17$.

Answer 17

Solution: IOQM 2024, Q29

With $n = 2^{19}3^{12}$ we have $n^2 = 2^{38}3^{24}$, so $$d(n^2) = 39 \cdot 25 = 975, \qquad d(n) = 20 \cdot 13 = 260.$$

The divisors of $n^2$ come in pairs $\{d, n^2/d\}$, and the two members are equal only for $d = n$. Of the remaining $974$ divisors, exactly one of each pair is less than $n$, so $$\#\{d \mid n^2 : d < n\} = \frac{974}{2} = 487.$$

Among these, the ones that do divide $n$ are precisely the divisors of $n$ other than $n$ itself, of which there are $260 - 1 = 259$. Hence $$M = 487 - 259 = 228,$$ and the last two digits are $28$.

Answer 28

Solution: IOQM 2025 Part SEP, Q28

Let $$K = 2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{5 + \cfrac{1}{6 + \cfrac17}}}},$$ so the left-hand side is $1 - \dfrac1K = \dfrac{K-1}{K}$. Turning that upside down, $$\frac{K-1}{K} = \cfrac{1}{\dfrac{K}{K-1}} = \cfrac{1}{1 + \cfrac{1}{K-1}},$$ since $\dfrac{K}{K-1} = 1 + \dfrac{1}{K-1}$.

Now read off the terms. Comparing with the required shape, $x_1 = 1$, and what remains is $$x_2 + \cfrac{1}{x_3 + \cdots} = K - 1 = 1 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{5 + \cfrac{1}{6 + \cfrac17}}}},$$ because subtracting $1$ from $K$ only changes its leading term from $2$ to $1$. So $x_2 = 1$ and then the rest is read straight off: $$x_3 = 3, \quad x_4 = 4, \quad x_5 = 5, \quad x_6 = 6, \quad x_7 = 7.$$ (This is the unique such expansion, since at each stage the integer part is forced.)

The sum is $1 + 1 + 3 + 4 + 5 + 6 + 7 = 27$.

Answer 27

Solution: IOQM 2025 Part SEP, Q7

For $n$ not divisible by $7$, Fermat’s little theorem gives $n^6 \equiv 1 \pmod 7$. So $$(n+42)^{n+42} \equiv n^{n+42} = n^n \cdot \left(n^{6}\right)^{7} \equiv n^n \pmod 7,$$ and when $7 \mid n$ both sides are $0$. Hence $42$ is a period. The least positive period divides it: if $42=qT+r$ with $0\le r<T$, then $$f(n+r)=f(n+r+qT)=f(n+42)=f(n)$$ for every positive $n$, so a positive $r$ would contradict the minimality of $T$. Thus $r=0$.

One observation cuts the divisors down: $7$ must divide the period: if it did not, then some multiple of $7$ would be sent to a non-multiple of $7$, turning a value of $0$ into a non-zero one. That leaves $7$, $14$, $21$ and $42$.

Now test the three small ones against actual values, using $f(2) = 2^2 = 4$: Since the powers of $2$ cycle as $2,4,1$ modulo $7$, $$f(9) = 9^9 \equiv 2^9 \equiv 2^{9 \bmod 3} = 2^0 = 1 \pmod 7,$$ which is not $4$, so $T = 7$ fails. Likewise $$f(16) \equiv 2^{16} \equiv 2^{1} = 2 \ne 4,$$ so $T = 14$ fails. For $T = 21$, use $f(3) = 3^3 = 27 \equiv 6$ and $$f(24) \equiv 3^{24} \pmod 7,$$ where $3^1,3^2,\ldots,3^6$ leave remainders $3,2,6,4,5,1$, and $24 \equiv 0 \pmod 6$, so $f(24) \equiv 1 \ne 6$.

Everything smaller having failed, the least period is $T = 42$.

Answer 42

Solution: IOQM 2026, Q25

Factorise: $p^4 + p^2 - 2 = (p^2 - 1)(p^2 + 2)$. The prime $p$ is odd and is not a multiple of $3$.

The first factor is $(p - 1)(p + 1)$, two consecutive even numbers, one of them a multiple of $4$, so $8$ divides it. One of $p - 1$, $p$, $p + 1$ is a multiple of $3$, and it is not $p$, so $3$ divides it too, and $24$ divides $p^2 - 1$. Since $3$ divides $p^2 - 1$, the second factor $p^2 + 2 = (p^2 - 1) + 3$ is a multiple of $3$. So every member of $E$ is a multiple of $24 \times 3 = 72$.

Nothing larger works. With $p = 5$ the member is $648 = 2^3 \cdot 3^4$, and with $p = 7$ it is $2448 = 2^4 \cdot 3^2 \cdot 17$. A number dividing both divides $2^3 \cdot 3^2 = 72$. The answer is $72$.

Answer 72

Solution: PRMO 2014, Q17

If $x^2 + ax + b = 0$ has integer roots then, since their sum is $-a < 0$ and their product is $b > 0$, both roots are negative: write them as $-r$ and $-s$ with $rs = b$ and $a = r + s$.

Different factor pairs give different values of $a$, because a pair is recovered from its sum and product. So $N(b)$ is the number of unordered pairs $\{r, s\}$ with $rs = b$, which is $$N(b) = \left\lceil \frac{d(b)}{2} \right\rceil,$$ where $d(b)$ counts the divisors: the divisors pair up as $r$ with $b/r$, with a middle divisor left over exactly when $b$ is a perfect square.

So $N(b) = 20$ means $d(b) = 39$ or $d(b) = 40$, and we want the smallest such $b$.

Write $b = p_1^{e_1} p_2^{e_2} \cdots$ with the exponents in decreasing order. Then $d(b) = (e_1+1)(e_2+1)\cdots$, so a value of $d(b)$ fixes the exponents up to a factorisation of that value into factors greater than one. For a given list of exponents the smallest $b$ puts the largest exponent on the smallest prime and uses the smallest primes available: swapping a larger exponent $e$ from a prime $p$ onto a smaller prime $q$ carrying $f < e$ divides $b$ by $(p/q)^{e-f} > 1$, and replacing any prime by a smaller unused one shrinks $b$ as well.

That leaves a finite list to inspect. For $d(b) = 40$ the seven factorisations and the smallest number each allows are $$\begin{array}{c|c|c|c|c|c|c} \text{exponents} & 4,1,1,1 & 4,3,1 & 9,1,1 & 7,4 & 9,3 & 19,1 \\ \hline \text{smallest } b & 1680 & 2160 & 7680 & 10368 & 13824 & 1572864 \end{array}$$ together with the single exponent $39$, giving $2^{39}$. For $d(b) = 39$ the only factorisations are $39$ itself and $3 \times 13$, giving $2^{38}$ and $2^{12} \cdot 3^2 = 36864$.

The smallest entry anywhere in those two lists is $$b = 1680 = 2^4 \cdot 3 \cdot 5 \cdot 7,$$ and indeed $d(1680) = 5 \times 2 \times 2 \times 2 = 40$, giving $N(1680) = 20$.

Answer 1680

Solution: PRMO 2014, Q18

Since $999 = 3^3 \times 37$ and $f$ is multiplicative, $$f(999) = f(3)^3\,f(37).$$

Two constraints. First $f(1) = f(1 \times 1) = f(1)^2$, and the only natural number equal to its own square is $1$, since the natural numbers here start at $1$. So $f(1) = 1$, and injectivity then forbids any other value from being $1$: in particular $f(3) \ge 2$ and $f(37) \ge 2$. Second $f(3) \ne f(37)$, again by injectivity.

So we are minimising $u^3 v$ over distinct integers $u, v \ge 2$, which is smallest at $u = 2$, $v = 3$: $$f(999) \ge 2^3 \times 3 = 24.$$

That bound is attained. Send the prime $3$ to $2$, the prime $37$ to $3$, and permute the remaining primes among the primes left over, then extend multiplicatively. A permutation of the primes extends to a one-to-one map of the natural numbers onto themselves, by uniqueness of prime factorisation, so this $f$ is one-to-one and multiplicative, and $f(999) = 8 \times 3 = 24$.

Answer 24

Solution: PRMO 2017, Q28

A condition that holds for every $n$ can be tested one prime factor at a time. Write $m$ for the modulus $3pq$ while we find the general rule. For a small warning about repeated prime factors, try $m=9$ and $n=3$: $3^9-3=3(3^8-1)$ has only one factor of $3$, so it is not divisible by $9$. This suggests starting with squarefreeness.

The criterion

Suppose $m \mid n^m - n$ for every $n$. Then $m$ is squarefree: if $\ell^2 \mid m$ then taking $n = \ell$ gives $\ell^2 \mid \ell(\ell^{m-1} - 1)$, so $\ell \mid \ell^{m-1} - 1$, which is false.

Next, for each prime $\ell \mid m$ we show $\ell - 1 \mid m - 1$. Take any $a$ not divisible by $\ell$. From $\ell \mid a^m - a = a(a^{m-1} - 1)$ we get $a^{m-1} \equiv 1 \pmod \ell$, and Fermat’s little theorem gives $a^{\ell-1} \equiv 1$ as well. So two different exponents send $a$ to $1$, and the first thing to notice is that their gcd does too.

Indeed, if $a^j \equiv 1$ and $a^k \equiv 1$ with $j < k$, then $a^{k-j} \equiv 1$ as well, since multiplying $a^{k-j}$ by $a^j$ gives $a^k$. The exponents that send $a$ to $1$ are therefore closed under subtraction, which makes them exactly the multiples of the smallest of them: subtracting that smallest one repeatedly from any other member leaves a member, and the process cannot halt anywhere above zero. In particular the smallest exponent divides both $m-1$ and $\ell-1$, so it divides their gcd $d$, and hence $$a^{d} \equiv 1 \pmod \ell, \qquad d = \gcd(m-1,\, \ell-1),$$ for every one of the $\ell - 1$ non-zero remainders $a$.

That is a great many solutions of one equation. The next step is to say that an equation of degree $d$ cannot have so many.

How many roots an equation can have modulo a prime

Over the ordinary numbers a polynomial of degree $d$ has at most $d$ roots, and the reason is the factor theorem: a root $r$ lets one write $f(X) = (X-r)g(X)$ with $g$ of degree one less. The same proof works modulo a prime $\ell$, and that is the only property of primes it uses.

Dividing $f$ by $X - r$ leaves $f(X) \equiv (X-r)g(X) + f(r)$, so a root $r$ gives $f(X) \equiv (X-r)g(X)$. If $s$ is another root then $(s-r)g(s) \equiv 0$ with $s - r \not\equiv 0$, and modulo a prime a product vanishes only when one factor does, so $g(s) \equiv 0$. Every root therefore peels off a factor and drops the degree by one, and there can be at most $d$ of them.

Apply this to $X^d - 1$. All $\ell - 1$ non-zero remainders are roots of it, so $\ell - 1 \le d$. But $d$ divides $\ell - 1$, so $d = \ell - 1$ and therefore $\ell - 1 \mid m - 1$.

The criterion, the other way round

Conversely, if $m$ is squarefree and $\ell - 1 \mid m - 1$ for every prime $\ell \mid m$, then each such $\ell$ divides $n^m - n$: when $\ell \mid n$ both terms are multiples of $\ell$, and otherwise $n^{m-1} = \left(n^{\ell-1}\right)^{(m-1)/(\ell-1)} \equiv 1$ by Fermat’s little theorem. Being squarefree, $m$ divides $n^m - n$.

Applying it to $m = 3pq$

Squarefreeness needs $3$, $p$, $q$ distinct. From $\ell = 3$ we need $2 \mid 3pq - 1$, so $3pq$ is odd and neither $p$ nor $q$ is $2$. From $\ell = p$, reduce modulo $p - 1$: since $p \equiv 1$, $$3pq - 1 \equiv 3q - 1 \pmod{p-1}, \qquad \text{so} \qquad p - 1 \mid 3q - 1,$$ and symmetrically $q - 1 \mid 3p - 1$.

The search

Take $p < q$, both odd primes other than $3$. From $q - 1 \mid 3p - 1$ we get $q \le 3p$, so the search is finite.

• $p = 5$: $q - 1 \mid 14$ gives $q \in \{2,3,8,15\}$, none an allowed prime.

• $p = 7$: $q - 1 \mid 20$ allows $q = 11$, but then $p - 1 = 6$ must divide $3q - 1 = 32$, and it does not.

• $p = 11$: $q - 1 \mid 32$ gives $q \in \{2,3,5,9,17,33\}$, and $q = 17$ is prime. Check the other condition: $p - 1 = 10$ divides $3 \times 17 - 1 = 50$. It works.

• $p = 13$: $p - 1 = 12$ would have to divide $3q - 1$, which is never a multiple of $3$. Impossible.

Any remaining pair has $p \ge 17$ and hence $p + q > 28$. So the least value is $$p + q = 11 + 17 = 28.$$

The two conditions established at the start, squarefree and $\ell - 1 \mid m-1$, are Korselt’s criterion. The number $3pq = 3 \times 11 \times 17 = 561$ that comes out of the search is the smallest Carmichael number, the first composite that passes Fermat’s test for every base.

Answer 28

Solution: PRMO 2017, Q29

Let $d = h_n = \gcd(n! + 1, (n+1)!)$.

First, $d$ is coprime to $n!$, because a common factor of $d$ and $n!$ would divide both $n!$ and $n! + 1$, hence divide $1$. Since $(n+1)! = (n+1)\cdot n!$, it follows that $$d \mid n + 1.$$

So $h_n$ is at most $n+1$. When $p=n+1$ is prime, Wilson’s theorem shows that $p$ divides $(p-1)!+1$, and here is the proof of the case we need.

Modulo a prime $p$, every non-zero remainder has a unique multiplicative inverse: multiplication by that remainder permutes the $p-1$ non-zero remainders. The only remainders that are their own inverses are $1$ and $-1$, since $r^2-1=(r-1)(r+1)$ and a prime dividing that product divides one factor. Pair all the others with their inverses. For example, modulo $5$ the pair $2,3$ has product $1$, leaving $1$ and $4=-1$. Every inverse pair has product $1$, so $$(p-1)!\equiv -1\pmod p.$$ For $p=2$ this holds directly as well. Thus $p\mid(p-1)!+1$ and $h_n=p$ in the prime case.

If $n + 1$ is composite, every prime factor of $n+1$ is at most $\tfrac{n+1}{2} \le n$ and so divides $n!$; but $d$ is coprime to $n!$, so $d = 1$. Hence $$h_n = \begin{cases} n+1 & \text{if } n+1 \text{ is prime},\\ 1 & \text{otherwise.} \end{cases}$$

For $n < 100$ we want the largest prime of the form $n + 1$ with $n \le 99$, that is the largest prime at most $100$. That is $97$, from $n = 96$.

Answer 97

Solution: PRMO 2018, Q25

We need a $T$ whose remainders satisfy $T \bmod 11 \in \{7,8,9\}$, and $T \bmod 13 \in \{1,2,3\}$, and $T \bmod 15 \in \{4,5,6\}$.

Start with the last two conditions, which fix $T$ modulo $195 = 13 \times 15$. The numbers below $195$ with remainder $4$ on division by $15$ are $4, 19, 34, \ldots, 184$, and each step of $15$ raises the remainder modulo $13$ by $2$, so their remainders modulo $13$ run $$4,\ 6,\ 8,\ 10,\ 12,\ 1,\ 3,\ 5,\ 7,\ 9,\ 11,\ 0,\ 2.$$ The ones in $\{1, 2, 3\}$ sit at $79$, $94$ and $184$. The same walk from $5$ and from $6$ finds three more each, $80, 170, 185$ and $66, 81, 171$, so nine possibilities in all: $$T \equiv 66,\ 79,\ 80,\ 81,\ 94,\ 170,\ 171,\ 184,\ 185 \pmod{195}.$$

Now test the smallest representative of each against the condition modulo $11$. The first eight values in increasing order are $66, 79, 80, 81, 94, 170, 171, 184$, whose remainders modulo $11$ are $$0,\ 2,\ 3,\ 4,\ 6,\ 5,\ 6,\ 8.$$ Only the last lies in $\{7,8,9\}$. The ninth candidate, $185$, has remainder $9$ and passes as well, but it is the larger of the two. Every other candidate has to be pushed up by at least one full period of $195$, which puts it past $184$.

So $T = 184$, and one checks directly: $184 = 16 \cdot 11 + 8$, $184 = 14 \cdot 13 + 2$, $184 = 12 \cdot 15 + 4$. The sum of the squares of its digits is $$1 + 64 + 16 = 81.$$

Answer 81

Solution: PRMO 2019, Q12

Which $k$ are good

Suppose first that $k = 2$, so $1/\sqrt{a} + 1/\sqrt{b} = 1$ with $a < b$. Then $1/\sqrt a > \tfrac12$, so $a < 4$, and $a = 1$ is impossible since it already exhausts the sum. That leaves two cases, and both fail: $$a = 2: \quad \sqrt b = \frac{1}{1 - 1/\sqrt2} = \sqrt2(\sqrt2 + 1) = 2 + \sqrt2, \quad b = 6 + 4\sqrt2,$$ $$a = 3: \quad \sqrt b = \frac{1}{1 - 1/\sqrt3} = \frac{3+\sqrt3}{2}, \quad b = 3 + \tfrac32\sqrt3,$$ and neither value of $b$ is an integer, $\sqrt2$ and $\sqrt3$ being irrational. So $k = 2$ is not good.

Every $k \ge 3$ is good, and the construction is short. Write $1$ as a sum of $k$ distinct unit fractions $1/n_1 + \cdots + 1/n_k$, then take $a_i = n_i^2$, so that $1/\sqrt{a_i} = 1/n_i$ and the $a_i$ are distinct. Such a decomposition exists for every $k \ge 3$: start from $$1 = \tfrac12 + \tfrac13 + \tfrac16,$$ and to go from $k$ parts to $k+1$ split the smallest part using $\tfrac1n = \tfrac{1}{n+1} + \tfrac{1}{n(n+1)}$, which replaces one denominator by two strictly larger ones and so keeps every denominator distinct.

The good numbers are therefore exactly $3, 4, 5, 6, \ldots$

The sum and the ratio

The first $n$ good numbers are $3, 4, \ldots, n+2$, so $$f(n) = 3 + 4 + \cdots + (n+2) = \frac{n\bigl(3 + (n+2)\bigr)}{2} = \frac{n(n+5)}{2}.$$ Hence $$\frac{f(n+5)}{f(n)} = \frac{(n+5)(n+10)/2}{n(n+5)/2} = \frac{n+10}{n} = 1 + \frac{10}{n},$$ the factor $n + 5$ cancelling, which is the reason the problem shifted by exactly five. This is an integer precisely when $n$ divides $10$, that is $n \in \{1, 2, 5, 10\}$, and $$1 + 2 + 5 + 10 = 18.$$

Answer 18

Solution: PRMO 2019, Q18

Let $g = \gcd(a,b)$ and write $a = gd$, $b = ge$ with $\gcd(d,e) = 1$. Then $\operatorname{lcm}(a,b) = gde$, so the ratio condition says $$\frac{g}{gde} = \frac{1}{495}, \qquad \text{that is} \qquad de = 495.$$

Now $495 = 3^2 \times 5 \times 11$. A coprime splitting $de = 495$ must give each prime power entirely to one side, so there are $2^3 = 8$ ordered pairs and, imposing $d < e$ to match $a < b$, exactly four: $$(d,e) = (1, 495), \quad (5, 99), \quad (9, 55), \quad (11, 45).$$

For each, the constraints are $100 \le gd$ and $ge \le 1000$, since $gd < ge$ makes the other two inequalities automatic.

• $(1,495)$: needs $g \ge 100$ and $g \le 1000/495 = 2.02\ldots$, impossible.

• $(5,99)$: needs $g \ge 20$ and $g \le 1000/99 = 10.1\ldots$, impossible.

• $(9,55)$: needs $g \ge 100/9 = 11.1\ldots$, so $g \ge 12$, and $g \le 1000/55 = 18.1\ldots$, so $g \le 18$. That is $7$ values.

• $(11,45)$: needs $g \ge 100/11 = 9.09\ldots$, so $g \ge 10$, and $g \le 1000/45 = 22.2\ldots$, so $g \le 22$. That is $13$ values.

The two impossible cases are impossible for the same reason: a lopsided splitting forces $b$ to be hundreds of times $a$, and the window from $100$ to $1000$ is only ten-fold. Adding the rest, $$7 + 13 = 20$$ ordered pairs.

Answer 20

Solution: PRMO 2019, Q30

The necessary condition

If $\{1, 2, \ldots, n\}$ splits into three subsets of equal sum, then $3$ divides $1 + 2 + \cdots + n = n(n+1)/2$. Checking the three remainders of $n$ modulo $3$, one finds $n(n+1)/2$ is a multiple of $3$ exactly when $$n \equiv 0 \text{ or } 2 \pmod 3,$$ since $n \equiv 1$ makes both $n$ and $n+1$ prime to $3$.

The construction

Four base cases, each an explicit split into three parts of equal sum: $$\begin{array}{ll} n = 5: & \{5\},\ \{1,4\},\ \{2,3\} \quad \text{(each summing to } 5) \\ n = 6: & \{1,6\},\ \{2,5\},\ \{3,4\} \quad \text{(each } 7) \\ n = 8: & \{4,8\},\ \{5,7\},\ \{1,2,3,6\} \quad \text{(each } 12) \\ n = 9: & \{6,9\},\ \{7,8\},\ \{1,2,3,4,5\} \quad \text{(each } 15) \end{array}$$ And one step: given a valid split of $\{1, \ldots, n\}$, the six new numbers $n+1, \ldots, n+6$ form three pairs of equal sum $2n + 7$, namely $$\{n+1, n+6\}, \quad \{n+2, n+5\}, \quad \{n+3, n+4\},$$ so handing one pair to each subset splits $\{1, \ldots, n+6\}$. Since the four base cases $5, 6, 8, 9$ cover the remainders $5, 0, 2, 3$ modulo $6$, and those are exactly the remainders allowed by the divisibility condition, every $n \ge 5$ satisfying it can be split.

The smallest cases are genuinely excluded and not merely awkward: for $n = 4$ the total is $10$, which is not divisible by $3$ at all, and in general $n$ must be at most a third of the total, which fails below $n = 5$.

The count

So $E$ consists of the $n$ with $4 < n < 100$ and $n \equiv 0$ or $2 \pmod 3$, together with the requirement $n \ge 5$, which excludes nothing further since $n = 4$ already fails the divisibility. Counting from $5$ to $99$: $$n \equiv 0: \ 6, 9, \ldots, 99 \ \text{gives } 32, \qquad n \equiv 2: \ 5, 8, \ldots, 98 \ \text{gives } 32.$$ Hence $|E| = 32 + 32 = 64$.

Answer 64

Solution: IOQM 2020, Q25

Begin by evaluating the four bracketed terms, each time comparing the distances to the squares on either side. For $91$ the neighbours are $81$ and $100$, at distances $10$ and $9$, so $\langle 91 \rangle = 100$. For $120$ the neighbours are $100$ and $121$, at distances $20$ and $1$, so $\langle 120 \rangle = 121$. Similarly $\langle 143 \rangle = 144$, being one below $144$, while $180$ sits between $169$ and $196$ at distances $11$ and $16$, so $\langle 180 \rangle = 169$.

The equation now reads $$100 \cdot 121 \cdot 144 \cdot 169 \cdot \langle N \rangle = 91 \cdot 120 \cdot 143 \cdot 180 \cdot N,$$ and rather than multiply everything out it is far easier to cancel prime by prime. Since $91 = 7 \cdot 13$ and $143 = 11 \cdot 13$, the right side carries $13^2$, which cancels against $169$; one factor of $11$ cancels against $121$; and the remaining $\tfrac{120 \cdot 180}{100 \cdot 144} = \tfrac{21600}{14400} = \tfrac32$ leaves $$\frac{\langle N \rangle}{N} = \frac{7 \cdot 3}{11 \cdot 2} = \frac{21}{22}.$$

So $\langle N \rangle = \tfrac{21}{22}N$, which tells us two things at once. First, $22$ must divide $N$, say $N = 22k$, whence $\langle N \rangle = 21k$. Second, $21k$ has to be a perfect square, and since $21 = 3 \cdot 7$ is square-free this forces $k = 21m^2$. Putting these together, $$N = 462m^2, \qquad \langle N \rangle = 441m^2 = (21m)^2.$$

It remains to check that $(21m)^2$ really is the nearest square to $462m^2$, since we derived the form from an equation, while the bracket has a meaning of its own, the nearest square. Taking the smallest case $m = 1$, we have $N = 462$ lying between $441 = 21^2$ and $484 = 22^2$, at distances $21$ and $22$ respectively, so the nearest square is indeed $441$. The smallest positive $N$ is therefore $462$, and the sum of the squares of its digits is $4^2 + 6^2 + 2^2 = 16 + 36 + 4 = 56$.

Answer 56

Solution: IOQM 2021 Part B, Q2

Which $n$ are impossible

Since $-2 \equiv 1 \pmod 3$, every power $(-2)^{i-1}$ is congruent to $1$, so for any permutation $\sigma$, $$\sum_{i=1}^{n}\sigma(i)(-2)^{i-1} \equiv \sum_{i=1}^{n}\sigma(i) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} \pmod 3.$$ The right-hand side is a multiple of $3$ unless $n \equiv 1 \pmod 3$, in which case it is $\equiv 1$. So for $n \equiv 1 \pmod 3$ the sum can never be zero, whatever the permutation.

Which $n$ work

Every other $n$ does work, by induction in steps of three.

The two smallest cases are explicit. For $n = 2$ take $\sigma = (2,1)$, giving $2 - 2 = 0$. For $n = 3$ take $\sigma = (2,3,1)$, giving $2 - 6 + 4 = 0$.

To extend a working list, shift its entries up by $3$ and move it two positions to the right. Its old zero sum stays zero, multiplied by $(-2)^2$, but the added $3$s contribute a geometric sum. The unused values $1,2,3$ can cancel that correction: put $2,3$ first and $1$ last. For example, $(2,1)$ extends to $(2,3,5,4,1)$, whose weighted sum is $2-6+20-32+16=0$.

Now suppose a permutation $\sigma$ of $1,\ldots,m$ works. The same arrangement for $m+3$ is: $$\tau(1) = 2, \qquad \tau(2) = 3, \qquad \tau(m+3) = 1,$$ $$\tau(i) = \sigma(i-2) + 3 \quad \text{ for } 3 \le i \le m+2.$$ This is a permutation of $1, \ldots, m+3$: the values $2$, $3$, $1$ are used once each and the rest are $\sigma$ shifted up by $3$.

Its sum splits into the shifted copy of the old sum and a correction. The shifted copy contributes $$\sum_{i=3}^{m+2}\bigl(\sigma(i-2)+3\bigr)(-2)^{i-1} = (-2)^{2}\underbrace{\sum_{j=1}^{m}\sigma(j)(-2)^{j-1}}_{=\,0} + 3\sum_{i=3}^{m+2}(-2)^{i-1},$$ and the geometric series evaluates as $$3\sum_{i=3}^{m+2}(-2)^{i-1} = 3 \cdot \frac{(-2)^{m+2} - (-2)^{2}}{-2 - 1} = -\left((-2)^{m+2} - 4\right).$$ Adding the three special terms $2 \cdot 1 + 3 \cdot (-2) + 1 \cdot (-2)^{m+2}$, $$\sum_{i=1}^{m+3}\tau(i)(-2)^{i-1} = 2 - 6 + (-2)^{m+2} - (-2)^{m+2} + 4 = 0.$$

So from $n = 2$ and $n = 3$ the construction reaches every larger $n$ congruent to $2$ or $0$ modulo $3$, and the answer is $$n \equiv 0 \ \text{ or } \ 2 \pmod 3.$$

Answer proof

Solution: IOQM 2022, Q8

Move everything to expose the factorisations: $$q^2 - q = 197p^2 - 3p, \qquad \text{that is} \qquad q(q-1) = p(197p - 3).$$ The prime $p$ divides the right side, so it divides $q(q-1)$, hence $p = q$ or $p \mid q - 1$. The case $p = q$ gives $q^2 - q = 197q^2 - 3q$, so $196q^2 = 2q$, which has no prime solution.

So write $q - 1 = kp$ with $k$ a positive integer. Substituting $q = kp+1$, $$(kp+1)(kp) = p(197p - 3) \quad\Longrightarrow\quad k^2 p + k = 197p - 3,$$ and gathering the terms in $p$ gives $p\left(197 - k^2\right) = k + 3$.

Since $p$ and $k+3$ are positive, we need $k^2 < 197$, so $k \leq 14$, and $p = \dfrac{k+3}{197 - k^2}$ must be a prime. For $k \le 13$ the denominator is at least $197 - 169 = 28$ while the numerator is at most $16$, so $p$ would be less than $1$. That leaves only $k = 14$: $$p = \frac{17}{197 - 196} = 17,$$ which is prime. Then $q = 14 \cdot 17 + 1 = 239$, also prime.

Finally $\dfrac{q}{p} = \dfrac{239}{17} = 14 + \dfrac{1}{17}$, so $l = 14$, $m = 1$, $n = 17$, and $l + m + n = 32$.

Answer 32

Solution: IOQM 2022, Q17

If $p$ is the smallest prime factor of $n$, then the largest proper divisor is $g(n) = n/p$, so $$f(n) = n - \frac{n}{p} = n \cdot \frac{p-1}{p}.$$ In particular $f(n) = n/2$ for even $n$, and for odd $n$ the factor $\tfrac{p-1}{p}$ has an odd denominator. Rather than search forwards we invert the map three times, starting from $97$.

Solving $f(m) = 97$

If $m$ is even then $m/2 = 97$ and $m = 194$. If $m$ is odd with least prime $p$, then $m = \tfrac{97p}{p-1}$, and since $p-1$ is coprime to $p$ we need $p - 1 \mid 97$, so $p = 2$, which is not odd, or $p = 98$, which is not prime. So $m = 194$ uniquely.

Solving $f(k) = 194$

Even $k$ gives $k = 388$. Odd $k$ needs $p - 1 \mid 194$, so $p \in \{2, 3, 98, 195\}$, of which only $p = 3$ is an odd prime, giving $k = \tfrac{194 \cdot 3}{2} = 291 = 3 \cdot 97$, whose least prime really is $3$. So $k \in \{388,\ 291\}$.

Solving $f(N) = 388$ or $f(N) = 291$

From $388$: even $N$ gives $776$; odd $N$ needs $p-1 \mid 388$, so $p \in \{2,3,5,98,195,389\}$. Here $p = 3$ would give the even number $582$, a contradiction; $p = 5$ gives $N = \tfrac{388 \cdot 5}{4} = 485 = 5 \cdot 97$, valid; and $p = 389$ gives $N = 389$, a prime, for which $f(389) = 389 - 1 = 388$, also valid. From $291$: even $N$ gives $582$, and odd $N$ needs $p - 1 \mid 291$, which offers no odd prime.

The candidates are $776$, $582$, $485$ and $389$, so the smallest is $N = 389$. Since $19^2 = 361$ and $20^2 = 400$, the largest integer not exceeding $\sqrt{389}$ is $19$.

Answer 19

Solution: IOQM 2022, Q18

Write $g = \gcd(m,n)$ with $m = ga$ and $n = gb$, where $\gcd(a,b) = 1$, so that $\mathrm{LCM}(m,n) = gab$. The equation becomes $$ga + 3gb - 5 = 2gab - 11g,$$ that is, $$g\bigl(a + 3b - 2ab + 11\bigr) = 5.$$ Since $g$ is a positive integer dividing $5$, either $g = 1$ or $g = 5$, and the bracket takes the complementary value.

The case $g = 5$, which is where the maximum lives

Here $a + 3b - 2ab + 11 = 1$, so $2ab - a - 3b = 10$. Multiplying by $2$ to make it factor, $4ab - 2a - 6b = 20$, and adding $3$ to both sides, $$(2a - 3)(2b - 1) = 23.$$ As $23$ is prime, the positive possibilities are $(2a-3, 2b-1) = (1, 23)$ or $(23, 1)$. The first gives $a = 2$, $b = 12$, which fails because $\gcd(2,12) \neq 1$. The second gives $a = 13$, $b = 1$, which is coprime, so $m = 65$ and $n = 5$, and $m + n = 70$.

The case $g = 1$

Now $a + 3b - 2ab + 11 = 5$, and the same manipulation gives $(2a-3)(2b-1) = 15$. Here $2b - 1$ is positive, so $2a - 3$ is too, and the four factorisations of $15$ give $$(a, b) = (2, 8), \quad (3, 3), \quad (4, 2), \quad (9, 1).$$ The first three share a factor, so only $a = 9$, $b = 1$ is coprime, giving $m = 9$, $n = 1$ and $m + n = 10$.

The larger of the two is $70$.

Answer 70

Solution: IOQM 2023, Q29

Suppose $n = a_1 a_2 \cdots a_k = a_1 + a_2 + \cdots + a_k$. The factors equal to $1$ do not affect the product, and each adds $1$ to the sum, so a representation is completely described by the factors that exceed $1$, listed with repeats and in no particular order: if those are $b_1, \ldots, b_j$ with product $n$ and sum $t$, the number of ones is forced to be $n - t$.

That number of ones is never negative. For $j \ge 2$ factors each at least $2$, $$b_1b_2\cdots b_j \ge b_1 + b_2 + \cdots + b_j,$$ which for two factors is $(b_1-1)(b_2-1) \ge 1$ and follows for more factors by repeating the step. So every factorisation of $n$ into two or more factors, each at least $2$, gives exactly one valid representation, and every representation arises this way.

Uniqueness therefore means: $n$ has exactly one factorisation into two or more factors greater than $1$. A prime has none at all, so primes are not beautiful. If $n$ has three prime factors counted with multiplicity, say $n = pqr$, then $n = p \cdot qr$ and $n = p \cdot q \cdot r$ are two different factorisations, so $n$ is not beautiful; and the same applies with more factors. That leaves exactly the numbers with two prime factors counted with multiplicity, $n = pq$, whose only factorisation is $p \cdot q$.

So the beautiful numbers are the products of two primes. Checking downwards from $99$: $99 = 3^2 \cdot 11$ has three prime factors, $98 = 2 \cdot 7^2$ has three, $97$ is prime, $96$ has many, and $$95 = 5 \cdot 19$$ is a product of two primes. The largest beautiful number below $100$ is $95$.

The example in the problem is worth revisiting with this in hand: $8 = 2^3$ has the two factorisations $2 \cdot 4$ and $2 \cdot 2 \cdot 2$, which are exactly the two representations displayed there.

Answer 95

Solution: IOQM 2023, Q30

The first few divisor counts and running sums show where the parity changes: $$\begin{array}{c|rrrrrrrrr} n&1&2&3&4&5&6&7&8&9\\\hline d(n)&1&2&2&3&2&4&2&4&3\\ \sum_{i=1}^n d(i)&1&3&5&8&10&14&16&20&23 \end{array}$$ The running sum changes parity at $1,4,9$, the squares. Divisor pairing explains that pattern.

Divisors come in pairs $e$ and $m/e$, and the two coincide only when $m$ is a perfect square. So $d(m)$ is odd exactly when $m$ is a perfect square, and therefore $$\sum_{i=1}^{n} d(i) \equiv \#\{\text{perfect squares} \le n\} = \lfloor \sqrt n \rfloor \pmod 2.$$ The sum is odd exactly when $\lfloor \sqrt n \rfloor$ is odd.

Now count such $n \le 2023$. The integers with $\lfloor \sqrt n \rfloor = k$ are those from $k^2$ to $(k+1)^2 - 1$, and there are $2k+1$ of them. Since $44^2 = 1936 \le 2023 < 2025 = 45^2$, the value of $k$ runs from $1$ to $44$, and the largest odd $k$ is $43$, whose block ends at $44^2 - 1 = 1935$, comfortably inside the range. So no block with odd $k$ is cut short, and $$r = \sum_{\substack{k \text{ odd} \\ 1 \le k \le 43}} (2k+1).$$ There are $22$ odd values of $k$, and their sum is $1 + 3 + \cdots + 43 = 22^2 = 484$, so $$r = 2 \cdot 484 + 22 = 990.$$

The sum of the digits of $990$ is $9 + 9 + 0 = 18$.

Answer 18

Solution: IOQM 2024, Q18

Write $r = 100p + q$. Then $$r = 100(p+q) - 99q,$$ so $p + q$ divides $r$ exactly when $p+q$ divides $99q$. Now $\gcd(p+q, q) = \gcd(p,q) = 1$, so

this happens exactly when $$(p+q) \mid 99.$$

The divisors of $99$ are $1, 3, 9, 11, 33, 99$. Both $p$ and $q$ are two-digit, so $p + q \ge 20$, leaving only $33$ and $99$.

To make $r$ large we want $p$ as large as possible, and $p + q = 99$ allows a much larger $p$ than $p+q = 33$ does, where $p \le 22$ and hence $r \le 2211$. So take $p + q = 99$ and work downward from the largest admissible $p$, remembering that $q$ must be two-digit and not a multiple of $10$, and that $\gcd(p,q) = 1$: $$p = 88,\ q = 11: \gcd = 11; \qquad p = 87,\ q = 12: \gcd = 3;$$ $$p = 86,\ q = 13: \gcd = 1.$$ So the largest printed number is $N = 8613$, and a check confirms $8613 = 99 \cdot 87$.

The last two digits are $13$.

Answer 13

Solution: IOQM 2024, Q23

The move that decides this problem is worth naming before it is used. We are not trying to work out what the fourth powers modulo $n$ actually are. We are trying to manufacture two different numbers in the range $1$ to $14$ that are forced to share a fourth power, because one such pair kills that value of $n$ outright.

The cheapest manufacturer is $(n-x)^4 \equiv x^4 \pmod n$, so any $n$ for which two of $1, \ldots, 14$ add up to $n$ is ruled out at once. For $15 \le n \le 27$ take the pair $14$ and $n - 14$, which are distinct and both in range. That disposes of everything from $15$ to $27$, and $n \le 13$ is impossible because fourteen numbers cannot have fourteen distinct remainders modulo $13$ or less, while $n = 14$ falls to the pair $1$ and $13$.

Three cases remain below $31$.

• $n = 28$: $13^4 - 1^4 = (13^2-1)(13^2+1) = 168 \cdot 170$, and $168 = 6 \cdot 28$, so $1$ and $13$ collide.

• $n = 29$: here $12^2 = 144 = 5 \cdot 29 - 1 \equiv -1$, so $(12x)^4 = \left(12^2\right)^2 x^4 \equiv x^4$. Hence $x$, $-x$, $12x$ and $-12x$ all share a fourth power, and for $x \not\equiv 0$ these four are distinct, since $1$, $-1$, $12$ and $-12$ are distinct modulo $29$. The $28$ non-zero remainders therefore fall into seven groups of four, leaving only seven possible fourth powers, which cannot accommodate fourteen numbers.

• $n = 30$: $7^4 = 2401 = 80 \cdot 30 + 1$, so $7$ and $1$ collide.

Now take $n = 31$, and suppose $t^4 \equiv 1$. Then $\left(t^2\right)^2 \equiv 1$, and modulo a prime $u^2 \equiv 1$ forces $u \equiv \pm 1$, so $t^2 \equiv \pm 1$. The minus sign is impossible, because it would give $$t^{30} = \left(t^2\right)^{15} \equiv (-1)^{15} = -1,$$ contradicting Fermat’s little theorem. So $t^2 \equiv 1$ and $t \equiv \pm 1$. To finish without dividing remainders, suppose $x^4\equiv y^4\pmod{31}$ for $1\le x<y\le14$. Then $$(x-y)(x+y)(x^2+y^2)\equiv0\pmod{31}.$$ The prime $31$ divides neither $x-y$ nor $x+y$, since $0<y-x<31$ and $x+y\le27$. It must therefore divide $x^2+y^2$, giving $x^2\equiv-y^2$. Raising to the fifteenth power gives $x^{30}\equiv-y^{30}$, but Fermat’s theorem makes these two sides $1$ and $-1$. This contradiction shows that no two such fourth powers coincide. So the fourteen fourth powers are distinct modulo $31$, and $31$ is the smallest such $n$.

Answer 31

Solution: IOQM 2024, Q28

First factorise. Treating it as a quadratic in $n^4$, $$n^8 + 3n^4 - 4 = (n^4 + 4)(n^4 - 1),$$ and each part factors further: $n^4 - 1 = (n-1)(n+1)(n^2+1)$, while completing a square gives $$n^4+4=(n^2+2)^2-(2n)^2=(n^2+2n+2)(n^2-2n+2).$$ So $$\tfrac12\left(n^8+3n^4-4\right) = \tfrac12 (n-1)(n+1)(n^2+1)(n^2+2n+2)(n^2-2n+2).$$

For the whole thing to be squarefree, no odd prime may divide two factors or occur twice in one factor. For $2$, the division by $2$ removes one copy, so we must count its copies before cancelling. Two obstructions recur.

The prime $2$: for odd $n$, both $n-1$ and $n+1$ are even and $n^2+1$ is even as well, so $8$ divides the product and a single division by $2$ cannot rescue it. That rules out every odd $n$ at a stroke, in particular $21, 23, 25, 27, 29$.

That leaves the four even values $22, 24, 26, 28$, and each falls to a single visible square: $$n = 22: \ 5 \mid 485 = n^2+1 \text{ and } 5 \mid 530 = n^2+2n+2;$$ $$n = 24: \ n+1 = 25;$$ $$n = 26: \ n-1 = 25; \qquad n = 28: \ n-1 = 27 = 3^3.$$

Now test $n = 20$: $$\tfrac12 \cdot 19 \cdot 21 \cdot 401 \cdot 442 \cdot 362 = 19 \cdot 3 \cdot 7 \cdot 401 \cdot (2 \cdot 13 \cdot 17) \cdot 181,$$ after cancelling the $2$, and every prime here, namely $2, 3, 7, 13, 17, 19, 181, 401$, occurs once. So the value is squarefree and the answer is $$n = 20.$$

Answer 20

Solution: IOQM 2025 Part SEP, Q28

Set $j = n^2$, so the condition is $m^2 + j^2 = 2^k$ for some $k$.

Suppose $m$ and $j$ are both odd. Then $m^2 \equiv j^2 \equiv 1 \pmod 8$, so their sum is $2 \pmod 8$, which is a power of two only if the sum is $2$ itself, giving $m = j = 1$. If one is odd and the other even, the sum is odd and larger than $1$, which is impossible. So they are both even, and dividing the equation by $4$ returns the same problem for $m/2$ and $j/2$.

Descending in this way, we reach the odd case, so $$m = j = 2^s$$ for some $s \ge 0$. Since $j = n^2$, that means $n^2 = 2^s$, so $s$ is even, and writing $s = 2r$ gives $$n = 2^r, \qquad m = 2^{2r} = n^2.$$

Finally the bounds. We need $m = 4^r \le 20000$, and $4^7 = 16384$ while $4^8 = 65536$, so $r$ runs from $0$ to $7$; the condition on $n = 2^r$ is then automatic. That is $8$ ordered pairs.

Answer 8

Solution: IOQM 2025 Part SEP, Q28

The two brackets are linked by repeated quotient and remainder. Write $U=abcd+ab+ad+cd+1$, $V=bcd+b+d$ and $W=cd+1$. Then $$U=aV+W,\qquad V=bW+d,\qquad W=cd+1.$$ Dividing the first equation by $V$, then using the other two to read $V/W$, gives a sequence of reciprocals. This is why a continued fraction is useful. Build it from the inside: $$c + \frac1d = \frac{cd+1}{d}, \qquad b + \frac{d}{cd+1} = \frac{bcd + b + d}{cd+1},$$ $$a + \frac{cd+1}{bcd+b+d} = \frac{abcd + ab + ad + cd + 1}{bcd+b+d}.$$ The numerator and denominator on the right are exactly the two brackets in the problem, so the given equation says $$a + \cfrac{1}{b + \cfrac{1}{c + \cfrac{1}{d}}} = \frac{20}{17}.$$

Now expand $\tfrac{20}{17}$ as a continued fraction, which is just repeated division: $$\frac{20}{17} = 1 + \frac{3}{17} = 1 + \cfrac{1}{\tfrac{17}{3}} = 1 + \cfrac{1}{5 + \tfrac23} = 1 + \cfrac{1}{5 + \cfrac{1}{1 + \tfrac12}}.$$ So $a = 1$, $b = 5$, $c = 1$, $d = 2$, and this is the only expansion with four positive integer terms, since at each stage the integer part is forced.

Hence $$a^2+b^2+c^2+d^2 = 1 + 25 + 1 + 4 = 31.$$

Answer 31

Solution: IOQM 2025 Part SEP, Q28

Write each integer as $k t^2$ with $k$ squarefree; the number $k$ is its squarefree part. Then $mn$ is a perfect square precisely when $m$ and $n$ have the same squarefree part, because $mn = k_mk_n (t_mt_n)^2$ and $k_mk_n$ is a square only when $k_m = k_n$, both being squarefree.

So sort $1, \ldots, 50$ into classes by squarefree part. A class with squarefree part $k$ consists of the numbers $k, 4k, 9k, \ldots$ up to $50$, and only $k \le 12$ can give a class with more than one member: $$\begin{array}{r|l|c} k & \text{class} & \binom{|class|}{2} \\ \hline 1 & 1,4,9,16,25,36,49 & 21 \\ 2 & 2,8,18,32,50 & 10 \\ 3 & 3,12,27,48 & 6 \\ 5 & 5,20,45 & 3 \\ 6 & 6,24 & 1 \\ 7 & 7,28 & 1 \\ 10 & 10,40 & 1 \\ 11 & 11,44 & 1 \end{array}$$ Every other class is a single number and contributes nothing.

Adding up, the number of pairs with $m < n$ is $$21 + 10 + 6 + 3 + 1 + 1 + 1 + 1 = 44.$$

Answer 44

Solution: IOQM 2025 Part SEP, Q28

Modulo $7$ we have $2^3 = 8 \equiv 1$, so $2^n$ depends only on $n$ modulo $3$; and $n^2$ depends only on $n$ modulo $7$. So whether $7 \mid 2^n - n^2$ depends only on $n$ modulo $21$, and since $105 = 5 \cdot 21$, it is enough to count the good remainders in one block of $21$ and multiply by $5$.

The two tables are short. The powers cycle as $$2^n \equiv 2, 4, 1 \quad \text{for } n \equiv 1, 2, 0 \pmod 3,$$ and the squares are $$n^2 \equiv 0,1,4,2,2,4,1 \quad \text{for } n \equiv 0,1,\ldots,6 \pmod 7.$$ Each value $1$, $2$, $4$ that $2^n$ can take is a square for exactly two remainders modulo $7$, so for each remainder of $n$ modulo $3$ there are two good remainders modulo $7$: $$\begin{array}{c|c|c} n \bmod 3 & 2^n \bmod 7 & n \bmod 7 \text{ with } n^2 \equiv 2^n \\ \hline 0 & 1 & 1, 6 \\ 1 & 2 & 3, 4 \\ 2 & 4 & 2, 5 \end{array}$$ A remainder modulo $3$ and one modulo $7$ cannot belong to two different numbers in one block of $21$: their difference would be divisible by both $3$ and $7$, hence by $21$. The six numbers listed below realise all six allowed combinations, so the good remainders number $3 \times 2 = 6$. In $1, \ldots, 21$ they are $$n = 2,\ 4,\ 5,\ 6,\ 10,\ 15.$$ For instance $n = 4$ gives $2^4 \equiv 2$ and $4^2 = 16 \equiv 2$, while $n = 7$ gives $2^7 \equiv 2$ but $7^2 \equiv 0$.

Hence the count up to $105$ is $6 \cdot 5 = 30$.

Answer 30

Solution: IOQM 2026, Q29

Since $4^{31} = 2^{62}$, the definition says $3n = 2^{62} - 1$, so $2^{62} = 3n + 1$ leaves remainder $1$ on division by $n$. Every power $\bigl(2^{62}\bigr)^m$ then leaves remainder $1$ as well, being a product of numbers each one more than a multiple of $n$.

Now look at $n - 1$: $$n - 1 = \frac{4^{31} - 1}{3} - 1 = \frac{4^{31} - 4}{3} = 4 \cdot \frac{4^{30} - 1}{3}.$$ The fraction is a whole number, since $4^{30} - 1$ is a multiple of $4 - 1 = 3$, so $n - 1$ is even. It is also a multiple of $31$. Since $2^5 = 32 = 31 + 1$, the power $4^{30} = (2^5)^{12}$ leaves remainder $1$ on division by $31$, so $31$ divides $4^{30} - 1$, and as $31$ shares no factor with $3$ it divides $(4^{30} - 1)/3$.

So $62$ divides $n - 1$. Writing $n - 1 = 62m$, the number $2^{n-1} = \bigl(2^{62}\bigr)^m$ leaves remainder $1$ on division by $n$.

Answer 1

Solution: PRMO 2019, Q20

This question was discounted by the organisers, and the reason is visible as soon as the conditions are unpicked. The official key prints a dash against it.

Start with what the conditions allow. Let the remainders be $r_1$, $r_2$, $r_3$ on division by $11$, $12$, $13$, so $r_1 \le 10$, $r_2 \le 11$ and $r_3 \le 12$. They are to be distinct primes forming an arithmetic progression in that order, so $r_1 + r_3 = 2r_2$. The primes available are $2, 3, 5, 7$ for $r_1$ and $2, 3, 5, 7, 11$ for the other two. The prime $2$ cannot appear: as $r_1$ or $r_3$ it would make $r_1 + r_3$ odd, and as $r_2$ it would need $r_1 + r_3 = 4$ from two distinct primes. With odd primes only, $r_2 = 3$ would need $r_1 + r_3 = 6$ from distinct primes, which is impossible; $r_2 = 5$ needs $r_1 + r_3 = 10$, giving $3$ and $7$ in either order; $r_2 = 7$ needs $14 = 3 + 11$, and $r_1 \le 10$ puts the $3$ first; $r_2 = 11$ needs $22$, which no two allowed primes reach. That leaves exactly three triples: $$(3,5,7), \qquad (7,5,3), \qquad (3,7,11).$$

Each triple has a representative, checked directly: $$1697=11\cdot154+3=12\cdot141+5=13\cdot130+7,$$ $$29=11\cdot2+7=12\cdot2+5=13\cdot2+3,$$ $$1675=11\cdot152+3=12\cdot139+7=13\cdot128+11.$$ Any two numbers giving the same triple have a difference divisible by $11$, $12$ and $13$, hence by their product $1716$, since the three moduli are pairwise coprime. Thus the three possibilities are $$n \equiv 1697, \qquad n \equiv 29, \qquad n \equiv 1675 \pmod{1716}.$$

And here the question breaks. The set $E$ is the union of three remainder classes modulo $1716$, each of which is infinite: if $n$ lies in $E$ then so do $n + 1716$, $n + 3432$ and every further step. So $E$ has no largest element, and the phrase “the largest number in $E$” does not refer to anything.

The intended reading was surely one full cycle, that is the largest $n$ below $1716$, which is $1697$ and has digit sum $1 + 6 + 9 + 7 = 23$. It is worth writing that out because the working above is a perfectly good exercise in the Chinese remainder theorem. But an answer of $23$ needs a hypothesis the paper never states, and the discounting was correct.

Answer none

Solution: IOQM 2020, Q30

The two conditions pull in different directions, so the aim is to make them meet. Since $a+1$ divides $b-1$, write $b = k(a+1) + 1$. Since $b$ divides $a^2+a+2$, write $a^2 + a + 2 = mb$ for some positive integer $m$. The useful observation is that $$a^2 + a + 2 = a(a+1) + 2 \equiv 2 \pmod{a+1},$$ while $b \equiv 1 \pmod{a+1}$ by construction. Reducing $a^2+a+2 = mb$ modulo $a+1$ therefore gives $m \equiv 2 \pmod{a+1}$, so $m = 2 + j(a+1)$ for some integer $j \geq 0$.

Now show that $j$ has to be zero. Substituting both expressions into $a(a+1) + 2 = mb$ and expanding, $$a(a+1) + 2 = \bigl(2 + j(a+1)\bigr)\bigl(k(a+1)+1\bigr),$$ whose right-hand side expands to $$2k(a+1) + 2 + jk(a+1)^2 + j(a+1),$$ and cancelling the $2$ from each side and then dividing through by $a+1$ leaves $$a = 2k + j + jk(a+1).$$ If $j \geq 1$ and $k \geq 1$ then the single term $jk(a+1)$ already exceeds $a$, which is impossible, and $k = 0$ would make $b = 1$ rather than a three-digit number. So $j = 0$, meaning $m = 2$ and $$b = \frac{a^2 + a + 2}{2}.$$

What is left is arithmetic. Requiring $b$ to have three digits means $100 \leq \tfrac{a^2+a+2}{2} \leq 999$, that is $198 \leq a^2 + a \leq 1996$, which holds exactly for $14 \leq a \leq 44$. Finally we must not forget the first condition, which has not yet been fully used: we need $a+1$ to divide $b - 1 = \tfrac{a(a+1)}{2}$, and dividing gives $a/2$, so $a$ must be even.

The even values of $a$ from $14$ to $44$ inclusive are $14, 16, \ldots, 44$, and there are $\tfrac{44-14}{2} + 1 = 16$ of them, each giving exactly one $b$. So there are $16$ pairs.

Answer 16

Solution: IOQM 2025 Part SEP, Q7

Write $g = \gcd(a,c)$ and $h = \gcd(b,c)$, so that $\operatorname{lcm}(a,c) = ac/g$ and $\operatorname{lcm}(b,c) = bc/h$. Dividing the given equation by $c$, $$\frac ag + \frac bh = \frac{26}{27}(a+b), \qquad \text{that is} \qquad a\left(\frac1g - \frac{26}{27}\right) + b\left(\frac1h - \frac{26}{27}\right) = 0.$$ The bracket equals $\tfrac1{27}$ when the gcd is $1$ and is at most $\tfrac12 - \tfrac{26}{27} < 0$ otherwise. Two positive brackets cannot sum to zero, nor can two negative ones, so exactly one of $g, h$ is $1$.

Say $g = 1$, and handle the other case by symmetry at the end. Then $$\frac{a}{27} = b\left(\frac{26}{27} - \frac 1h\right), \qquad a = 26b - \frac{27b}{h}.$$ Write $b = hs$, which is legitimate because $h$ divides $b$. Then $$a = 26hs - 27s = s\,(26h - 27).$$ Since $h \ge 2$ we get $26h - 27 \ge 25$, and $h \ge 3$ would already give $a \ge 51 > 50$. So $h = 2$, $b = 2s$ and $a = 25s$, leaving $s \in \{1,2\}$.

The case $s = 2$ dies at once: it gives $a = 50$ and $b = 4$, and $h = \gcd(4,c) = 2$ forces $c$ even, whereupon $\gcd(50, c) \ge 2$, contradicting $g = 1$.

So $s = 1$, that is $a = 25$ and $b = 2$. The conditions on $c$ are $$\gcd(2,c) = 2 \ \Rightarrow\ c \text{ even}, \qquad \gcd(25,c) = 1 \ \Rightarrow\ 5 \nmid c.$$ Among $1 \le c \le 50$ there are $25$ even numbers, of which the $5$ multiples of $10$ are excluded, leaving $20$ values of $c$.

By the symmetry that swaps $a$ with $b$, the case $h = 1$ contributes another $20$ triples, and the two families are disjoint. The total is $$20 + 20 = 40.$$

Answer 40

Solution: IOQM 2025 Part SEP, Q28

Put $g = \gcd(a,b)$ and $a = gx$, $b = gy$ with $\gcd(x,y) = 1$, so that $\operatorname{lcm}(a,b) = gxy$. The equation becomes $$g^2xy = 406 + 11gxy + 7g, \qquad \text{that is} \qquad gxy\,(g-11) = 406 + 7g.$$

The right-hand side is positive, so $g \ge 12$. And since $xy \ge 1$, $$g(g-11) \le 406 + 7g, \qquad g^2 - 18g - 406 \le 0,$$ whose positive root is $9 + \sqrt{487}$. Since $23^2 = 529 > 487$, that root is less than $32$, so $g \le 31$.

Now $g(g-11)$ must divide $406 + 7g$. Rather than test twenty values of $g$, substitute $d = g - 11$, so that $1 \leq d \leq 20$ and the condition reads $$d(d+11) \mid 7d + 483.$$ In particular $d$ divides $7d + 483$, so $d$ divides $483 = 3 \cdot 7 \cdot 23$. The divisors of $483$ are $1, 3, 7, 21, 23, 69, 161, 483$, and only the first three are at most $20$. So three values of $g$ survive, and substituting each settles it: $$\begin{array}{c|c|c|c|c} d & g & d(d+11) & 7d + 483 & \text{divides?} \\ \hline 1 & 12 & 12 & 490 & \text{no} \\ 3 & 14 & 42 & 504 & \text{yes, quotient } 12 \\ 7 & 18 & 126 & 532 & \text{no} \end{array}$$

So $g = 14$ and $xy = 12$ with $\gcd(x,y) = 1$, leaving $\{x,y\} = \{1,12\}$ or $\{3,4\}$. Then $$a + b = g(x+y) = 14 \cdot 13 = 182 \qquad \text{or} \qquad 14 \cdot 7 = 98.$$

The smallest is $98$, from $(a,b) = (42,56)$, which checks out: $42 \cdot 56 = 2352 = 406 + 11 \cdot 168 + 7 \cdot 14$.

Answer 98