Maths Olympiad Prep

Library / /1 of 2

, 2017

Number theory Difficulty 5.8 AIME, harder Prove it Thailand

Find all positive integers nn such that 4n!4n+14n! - 4n + 1 is a perfect square.

Solution

For n6n \le 6, we can easily check that n=1,2,4n = 1, 2, 4 are the only positive integers satisfying the condition.

We will prove that there are no other positive integers which satisfy the condition. Assume to the contrary that there exists a positive integer n>6n > 6 that satisfies the condition.
Let 4n!4n+1=x24n! - 4n + 1 = x^2 for some non-negative integer xx.

So 4n!4n+4=x2+34n! - 4n + 4 = x^2 + 3. Let pp be a prime factor of n1n-1. From (n1)4n!(n-1) \mid 4n! and (n1)4n+4(n-1) \mid -4n + 4, we get that x2+3x^2 + 3 is divisible by pp. This means (3p)=1\left(\frac{-3}{p}\right) = 1 or p=3p = 3. But from the quadratic reciprocity theorem, (3p)=(p3)\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right) which is 1 only when p1(mod3)p \equiv 1 \pmod 3. So every prime factor of n1n-1 is 3 or is congruent to 1 modulo 3. That is n10(mod3)n-1 \equiv 0 \pmod 3.

Case 1 n11(mod3)n-1 \equiv 1 \pmod 3; that is n2(mod3)n \equiv 2 \pmod 3
So 4n!4n+12(mod3)4n! - 4n + 1 \equiv 2 \pmod 3, which contradicts the fact that 4n!4n+14n! - 4n + 1 is a perfect square.

Case 2 n10(mod3)n-1 \equiv 0 \pmod 3; that is n1(mod3)n \equiv 1 \pmod 3
So 4n!4n+10(mod3)4n! - 4n + 1 \equiv 0 \pmod 3 or 3x23 \mid x^2 or 3x3 \mid x. Then 9x2=4n!4n+19 \mid x^2 = 4n! - 4n + 1. But since n>6n > 6, this implies that 9n!9 \mid n!. So 94n+19 \mid -4n + 1 or n7(mod9)n \equiv 7 \pmod 9. Thus n16(mod9)n-1 \equiv 6 \pmod 9, which contradicts our conclusion that all prime factors of n1n-1 are 3 or are congruent to 1 modulo 3.

So the only positive integers satisfying the condition are 1, 2 and 4.

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.