Maths Olympiad Prep

Library / /220 of 462

Number theory Difficulty 5.8 AIME, harder Prove it Ireland

Find all pairs (n,p)(n, p) of positive integers such that:
* pp is the smallest positive integer that is not a factor of nn, and;
* nn is a factor of 3p2+13p^2 + 1.

Solution

A complete list of solutions is

nn124131428
pp233233
3p2+13p^2 + 1132828132828

Solution:

Solution 1. Any factor of nn is a factor of 3p2+13p^2 + 1. Hence, 33 cannot be a factor of nn. Hence, pp, the smallest non-factor of nn, can only be 22 or 33, as non-factors of 44 and above cannot be the smallest non-factor. If p=2p = 2, nn must be an odd factor of 3p2+1=133p^2 + 1 = 13, i.e. n=1n = 1 or n=13n = 13. If p=3p = 3, then nn must be an even factor of 3p2+1=283p^2 + 1 = 28, i.e. n=2,4,14,28n = 2, 4, 14, 28. This gives the solutions as tabulated above.

Solution 2. Clearly p>1p > 1 as 11 is a factor of all positive integers nn. The minimality of pp implies that p1p-1 is a factor of nn which is a factor of 3p2+13p^2+1, so p13p2+1p-1 \mid 3p^2+1. We also have p13p23=3(p1)(p+1)p-1 \mid 3p^2-3 = 3(p-1)(p+1). By subtraction p14p-1 \mid 4, so p1{1,2,4}p-1 \in \{1, 2, 4\} and p{2,3,5}p \in \{2, 3, 5\} so 3p2+1{13,28,76}3p^2 + 1 \in \{13, 28, 76\}. Checking the factors of {13,28,76}\{13, 28, 76\} for possible values of nn gives the solutions above.

Solution 3. Trying p=2,p=3,p=4p = 2, p = 3, p = 4 and p=5p = 5 and trying in turn each factor of 3p2+13p^2 + 1 as a candidate for nn gives all the solutions stated. If p>5p > 5 then 2,3,4,52, 3, 4, 5 are factors of nn and in particular nn is multiple of 1010, hence 3p2+13p^2 + 1 and 3(3p2+1)=9p2+33(3p^2 + 1) = 9p^2 + 3 as well, i.e. p2+39p2+30(mod10)-p^2 + 3 \equiv 9p^2 + 3 \equiv 0 \pmod{10}. But this means that 33 would have to be a quadratic residue modulo 1010, which is not the case.

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.