Maths Olympiad Prep

Library / /63 of 82

Number theory Difficulty 6.2 National olympiad Prove it Croatia

Let nn be an odd positive integer greater than 33. Let kk denote the least positive integer such that kn+1kn+1 is a perfect square and ll denote the least positive integer such that lnln is a perfect square.
Prove that nn is a prime number if and only if k>14nk > \frac{1}{4}n and l>14nl > \frac{1}{4}n.
(V.I. Bernik, I.K. Zhuk, O.V. Melnikov, Collection of Problems in Math. Olympiads)

Solution

If n=pn = p is a prime number, then l=pl = p so it is obvious that l>n4l > \frac{n}{4}. For kk we have: kp=(y1)(y+1)kp = (y - 1)(y + 1), so
{y1=k1,y+1=k2p,y1=k1p,y+1=k2.or \begin{cases} y - 1 = k_1, & y + 1 = k_2p, \\ y - 1 = k_1p, & y + 1 = k_2. \end{cases} \quad \text{or}
In each case, adding these two equations gives us 2y>p2y > p. If 4kp4k \le p (i.e. 4k<p4k < p since pp is prime), then it would be y2=kp+1<p24+1y^2 = kp + 1 < \frac{p^2}{4} + 1, i.e. p2<4y2<p2+4p^2 < 4y^2 < p^2 + 4. This is not possible since there are no perfect squares between p2p^2 and p2+4p^2 + 4.
We will prove that there does not exist an odd composite number n>3n > 3 such that 4l>n4l > n and 4k>n4k > n. Assume on the contrary that such nn exists. We can write nn in the form
n=x2p1ps n = x^2 \cdot p_1 \cdots p_s
with p1,,psp_1, \dots, p_s different prime numbers. Clearly, l=p1psl = p_1 \cdots p_s and we have
4p1ps=4l>n=x2p1ps. 4p_1 \cdots p_s = 4l > n = x^2p_1 \cdots p_s.
Hence x2<4x^2 < 4, so x=1x = 1, i.e.
n=p1ps. n = p_1 \cdots p_s.
Let yy denote the smallest number greater than 11 such that y21y^2 - 1 is divisible by nn (such yy exists since (n+1)21=n(n+2)(n+1)^2 - 1 = n(n+2) is divisible by nn). Clearly kn+1=y2kn + 1 = y^2, and it is easy to see that k>n4    2y>nk > \frac{n}{4} \iff 2y > n.
Now we can write nn in the form n=prn = pr, where p=pip = p_i for some ii, and rr is the product of all pjp_j for jij \neq i. Since nn is a composite number it follows that r>1r > 1.
By the Chinese remainder theorem there exists a unique TT, 0T<n0 \le T < n, such that
T1(modr), T \equiv 1 \pmod{r},
T1(modp). T \equiv -1 \pmod{p}.
Now look at the number S=nTS = n - T. We have:
S1(modr), S \equiv -1 \pmod{r},
S1(modp), S \equiv 1 \pmod{p},
so T2S21(modn)T^2 \equiv S^2 \equiv 1 \pmod{n}. Therefore, both TT and SS are candidates for yy. Clearly, one of them is less than n2\frac{n}{2}, so k<n4k < \frac{n}{4}, which is a contradiction.

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.