Maths Olympiad Prep

Library / /8 of 11

Number theory Difficulty 5.6 AIME, harder Prove it Philippines

Problem:

Find all positive integers nn such that n2n+1n^2 - n + 1 is a multiple of 5n45n - 4.

Solution

Solution:

We are to find all positive integers nn such that 5n45n - 4 divides n2n+1n^2 - n + 1.

Let d=5n4d = 5n - 4. We require dn2n+1d \mid n^2 - n + 1.

This means there exists an integer kk such that:
n2n+1=k(5n4) n^2 - n + 1 = k(5n - 4)
Rewriting:
n2n+15kn+4k=0 n^2 - n + 1 - 5k n + 4k = 0
n2(5k+1)n+(4k+1)=0 n^2 - (5k + 1)n + (4k + 1) = 0
This is a quadratic in nn. For nn to be integer, the discriminant must be a perfect square:
Δ=[(5k+1)]241(4k+1)=(5k+1)24(4k+1) \Delta = [-(5k + 1)]^2 - 4 \cdot 1 \cdot (4k + 1) = (5k + 1)^2 - 4(4k + 1)
=25k2+10k+116k4 = 25k^2 + 10k + 1 - 16k - 4
=25k26k3 = 25k^2 - 6k - 3
We want Δ\Delta to be a perfect square, say m2m^2:
25k26k3=m2 25k^2 - 6k - 3 = m^2
So,
25k26k(m2+3)=0 25k^2 - 6k - (m^2 + 3) = 0
We can try small integer values for kk to see if Δ\Delta is a perfect square.

Try k=0k = 0:
Δ=003=3 \Delta = 0 - 0 - 3 = -3
Not a perfect square.

k=1k = 1:
2563=16 25 - 6 - 3 = 16
1616 is a perfect square (424^2).

So k=1k = 1 works. Let's find nn:

Recall:
n2(5k+1)n+(4k+1)=0 n^2 - (5k + 1)n + (4k + 1) = 0
For k=1k = 1:
n26n+5=0 n^2 - 6n + 5 = 0
n=6±36202=6±42 n = \frac{6 \pm \sqrt{36 - 20}}{2} = \frac{6 \pm 4}{2}
So n=5n = 5 or n=1n = 1.

Check if n=1n = 1 and n=5n = 5 work in the original condition:

For n=1n = 1:
5n4=15n - 4 = 1, n2n+1=1n^2 - n + 1 = 1; 11 divides 11.

For n=5n = 5:
5n4=215n - 4 = 21, n2n+1=255+1=21n^2 - n + 1 = 25 - 5 + 1 = 21; 2121 divides 2121.

Try k=1k = -1:
25(6)3=25+63=28 25 - (-6) - 3 = 25 + 6 - 3 = 28
Not a perfect square.

Try k=2k = 2:
100123=85 100 - 12 - 3 = 85
Not a perfect square.

Try k=2k = -2:
100+123=109 100 + 12 - 3 = 109
Not a perfect square.

Try k=3k = 3:
225183=204 225 - 18 - 3 = 204
Not a perfect square.

Try k=3k = -3:
225+183=240 225 + 18 - 3 = 240
Not a perfect square.

Try k=4k = 4:
400243=373 400 - 24 - 3 = 373
Not a perfect square.

Try k=4k = -4:
400+243=421 400 + 24 - 3 = 421
Not a perfect square.

Thus, the only positive integer solutions are n=1n = 1 and n=5n = 5.

Answer:

All positive integers nn such that n2n+1n^2 - n + 1 is a multiple of 5n45n - 4 are n=1n = 1 and n=5n = 5.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.