Maths Olympiad Prep

Library / /9 of 27

Number theory Difficulty 5.5 AIME, harder Prove it Croatia

Let pp be a prime number, and let np1n \ge p-1 be an integer. If np+1np+1 is a perfect square, prove that n+1n+1 can be represented as a sum of squares of exactly pp positive integers.

Solution

Let aa be a positive integer such that np+1=a2np + 1 = a^2. Note that a>1a > 1.
We have a21=np, i.e. (a1)(a+1)=np. \text{We have } a^2 - 1 = np, \text{ i.e. } (a-1)(a+1) = np.
Since pp is prime, it follows that pa1p \mid a-1 or pa+1p \mid a+1. We treat these two cases separately:

i) Let pa1p \mid a-1, i.e. let a=kp+1a = kp + 1 for some integer kk.
Then 1+np=(kp+1)2=k2p2+2kp+1, i.e. n=k2p+2k. \text{Then } 1 + np = (kp + 1)^2 = k^2p^2 + 2kp + 1, \text{ i.e. } n = k^2p + 2k.
Now we have:
n+1=k2p+2k+1=k2+2k+1+(p1)k2=(k+1)2+(p1)k2. n + 1 = k^2p + 2k + 1 = k^2 + 2k + 1 + (p-1)k^2 = (k+1)^2 + (p-1)k^2.
Notice that a>1a > 1 implies k>0k > 0, so k+1k+1 and kk are both positive integers.

ii) Let pa+1p \mid a+1, so that a=kp1a = kp - 1 for some integer kk.
Analogously to the first case, we get n+1=(k1)2+(p1)k2n + 1 = (k-1)^2 + (p-1)k^2.
It remains to show that k1k-1 is indeed a positive integer, i.e. that we have k2k \ge 2.
If we assume the contrary (k=1k = 1), it follows that n+1=p1n + 1 = p - 1, i.e. n=p2n = p - 2.
This contradicts the given condition that np1n \ge p - 1.
We conclude that the assertion holds for any choice of nn and pp satisfying the conditions of the problem.

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 and solution reproduced as published; topic and difficulty added by this site.