Maths Olympiad Prep

Library / /29 of 87

Number theory Difficulty 6.0 AIME, harder Prove it Russia

Find all positive integers nn for which there exists an even positive integer aa such that (a1)(a21)(an1)(a-1)(a^2-1)\dots(a^n-1) is a perfect square.

Solutions — 2

Solution 1

Ответ. For n=1n=1 and n=2n=2.

For n=1n=1, any even aa of the form m2+1m^2+1 works, for example, a=2a=2.

For n=2n=2, any even aa of the form m21m^2-1 works, for example, a=8a=8.

Assume that for n=3n=3, such a number aa exists. Then the number (a1)(a21)(a31)=(a1)3(a+1)(a2+a+1)(a-1)(a^2-1)(a^3-1) = (a-1)^3(a+1)(a^2+a+1) must be a perfect square. Since a2+a+1=a(a+1)+1a^2+a+1 = a(a+1)+1, the numbers a+1a+1 and a2+a+1a^2+a+1 are coprime. Because a+1a+1 is odd, the numbers a+1a+1 and a1a-1 are also coprime. Therefore, both a+1a+1 and (a1)(a2+a+1)(a-1)(a^2+a+1) must be perfect squares. In particular, a+1a + 1 modulo 3 can only be 0 or 1, and thus a1a - 1 is not divisible by 3. Hence,
gcd(a1,a2+a+1)=gcd(a1,(a+2)(a1)+3)==gcd(a1,3)=1, \begin{align*} \gcd(a - 1, a^2 + a + 1) &= \gcd(a - 1, (a + 2)(a - 1) + 3) = \\ &= \gcd(a - 1, 3) = 1, \end{align*}
meaning that both a1a-1 and a2+a+1a^2+a+1 must be perfect squares.
However, the latter cannot be a square, since a2<a2+a+1<(a+1)2a^2 < a^2+a+1 < (a+1)^2. This is a contradiction.

It remains to prove that no such aa exists for n4n \geq 4. Suppose such an aa exists. Take a natural number k2k \geq 2 such that 2kn<2k+12^k \leq n < 2^{k+1}. Since a2k1=(a2k1)(a2k+1)a^{2^k} - 1 = (a^{2^k} - 1)(a^{2^k} + 1), the number (a1)(a21)(an1)(a - 1)(a^2 - 1) \dots (a^n - 1) can be expressed as the product of a2k1+1a^{2^k} - 1 + 1 and several other factors of the form am1a^m - 1, where 1mn1 \leq m \leq n and m2km \neq 2^k.
We will show that the factor a2k1+1a^{2^{k-1}} + 1 is coprime with all other factors in this decomposition. Suppose a2k1+1a^{2^{k-1}} + 1 and am1a^m - 1 share a common divisor dd. Then gcd(a2k1,am1)\gcd(a^{2^k} - 1, a^m - 1) is divisible by dd. But gcd(a2k1,am1)=agcd(2k,m)1\gcd(a^{2^k} - 1, a^m - 1) = a^{\gcd(2^k,m)} - 1. Since m2km \neq 2^k and mn<2k+1m \leq n < 2^{k+1}, the number mm cannot be divisible by 2k2^k. Thus, gcd(2k,m)\gcd(2^k, m) is a power of two not exceeding 2k12^{k-1}. Therefore, a2k11a^{2^{k-1}-1} divides gcd(a2k1,am1)\gcd(a^{2^k}-1, a^m-1), and hence also divides dd. Because aa is even, the numbers a2k11a^{2^{k-1}-1} and a2k1+1a^{2^{k-1}}+1 have no common divisors other than 1, so d=1d=1, as required.
The factor a2k1+1a^{2^{k-1}} + 1 is coprime with all other factors in the product, which is a perfect square, so it must itself be a perfect square. Then a2k1+1a^{2^{k-1}} + 1 and a2k1a^{2^{k-1}} are perfect squares differing by 1, which is impossible. Therefore, our assumption is false, and no such aa exists for n4n \geq 4.

Solution 2

For n=1n=1 and n=2n=2.

For n=1n=1, any even number aa of the form m2+1m^2 + 1 works, for example, a=2a = 2.

For n=2n = 2, any even number aa of the form m21m^2 - 1 works, for example, a=8a = 8.

Assume that for n=3n = 3, such a number aa exists. Then the number (a1)(a21)(a31)=(a1)3(a+1)(a2+a+1)(a-1)(a^2-1)(a^3-1) = (a-1)^3(a+1)(a^2+a+1) must be a perfect square. Since a2+a+1=a(a+1)+1a^2+a+1 = a(a+1)+1, the numbers a+1a+1 and a2+a+1a^2+a+1 are coprime. As a+1a+1 is odd, the numbers a+1a+1 and a1a-1 are also coprime. Therefore, both a+1a+1 and (a1)(a2+a+1)(a-1)(a^2+a+1) must be perfect squares. In particular, a+1a+1 modulo 33 can only be 00 or 11, and thus a1a-1 is not divisible by 33. Hence,
gcd(a1,a2+a+1)=gcd(a1,(a+2)(a1)+3)==gcd(a1,3)=1, \begin{aligned} \gcd(a-1, a^2+a+1) &= \gcd(a-1, (a+2)(a-1)+3) = \\ &= \gcd(a-1, 3) = 1, \end{aligned}
meaning that both a1a-1 and a2+a+1a^2+a+1 must be perfect squares. However, the latter cannot be a square, since a2<a2+a+1<(a+1)2a^2 < a^2+a+1 < (a+1)^2. This is a contradiction.

It remains to prove that no such aa exists for n4n \ge 4. Suppose such an aa exists. Take a natural number k2k \ge 2 such that 2kn<2k+12^k \le n < 2^{k+1}. Since a2k1=(a2k11)(a2k1+1)a^{2^k} - 1 = (a^{2^{k-1}} - 1)(a^{2^{k-1}} + 1), the number (a1)(a21)(an1)(a-1)(a^2-1)\dots(a^n-1) can be expressed as the product of a2k1+1a^{2^{k-1}} + 1 and several other factors of the form am1a^m - 1, where 1mn1 \le m \le n and m2km \ne 2^k.

We will show that the factor a2k1+1a^{2^{k-1}} + 1 is coprime with all other factors in this decomposition. Suppose a2k1+1a^{2^{k-1}} + 1 and am1a^m - 1 share a common divisor dd. Then gcd(a2k1,am1)\gcd(a^{2^k} - 1, a^m - 1) is divisible by dd. But gcd(a2k1,am1)=agcd(2k,m)1\gcd(a^{2^k} - 1, a^m - 1) = a^{\gcd(2^k,m)} - 1. Since m2km \ne 2^k and mn<2k+1m \le n < 2^{k+1}, the number mm cannot be divisible by 2k2^k. Thus, gcd(2k,m)\gcd(2^k, m) is a power of two not exceeding 2k12^{k-1}. Therefore, a2k11a^{2^{k-1}-1} divides gcd(a2k1,am1)\gcd(a^{2^k} - 1, a^m - 1), and hence also divides dd. Because aa is even, the numbers a2k11a^{2^{k-1}-1} and a2k1+1a^{2^{k-1}} + 1 have no common divisors other than 11, so d=1d = 1, as required.

The factor a2k1+1a^{2^{k-1}} + 1 is coprime with all other factors in the product, which is a perfect square, so it must itself be a perfect square. Then a2k1+1a^{2^{k-1}} + 1 and a2k1a^{2^{k-1}} are perfect squares differing by 11, which is impossible. Therefore, our assumption is false, and no such aa exists for n4n \ge 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 reproduced verbatim; metadata (topic, difficulty) added by this project.