Olympiad Maths Prep

Track / Stage 6 / 287 of 400 #1287 of 2000

Problem 1287

National olympiad, first round
Number theory Difficulty 6.5 Find the answer

Find all natural numbers a>1a>1, with the property that every prime divisor of a61a^6-1 divides also at least one of the numbers a31a^3-1, a21a^2-1.

[i]K. Dochev[/i]

Official solution

1. We start with the given expression a61a^6 - 1:
a61=(a31)(a3+1) a^6 - 1 = (a^3 - 1)(a^3 + 1)
Further factorizing a3+1a^3 + 1:
a3+1=(a+1)(a2a+1) a^3 + 1 = (a + 1)(a^2 - a + 1)
Therefore:
a61=(a31)(a+1)(a2a+1) a^6 - 1 = (a^3 - 1)(a + 1)(a^2 - a + 1)

2. We need to consider the prime divisors of a61a^6 - 1. Every prime divisor of a31a^3 - 1 is already a prime divisor of a31a^3 - 1, so we focus on the prime divisors of a+1a + 1 and a2a+1a^2 - a + 1.

3. Consider the prime divisors of a+1a + 1. Any prime divisor pp of a+1a + 1 must also divide:
(a+1)(a1)=a21 (a + 1)(a - 1) = a^2 - 1
Hence, pp divides a21a^2 - 1.

4. Now, consider the prime divisors of a2a+1a^2 - a + 1. Let pp be a prime divisor of a2a+1a^2 - a + 1. We need to check if pp divides a31a^3 - 1 or a21a^2 - 1.

5. Suppose pp divides a31a^3 - 1. Then:
pa(a2a+1)(a31)=a2a1 p \mid a(a^2 - a + 1) - (a^3 - 1) = a^2 - a - 1
Therefore:
p(a2a+1)(a2a1)=2 p \mid (a^2 - a + 1) - (a^2 - a - 1) = 2
This implies p=2p = 2. However, if 2a2a+12 \mid a^2 - a + 1, then 2a(a1)2 \mid a(a - 1), which means 212 \mid 1, a contradiction. Thus, p2p \neq 2.

6. Next, suppose pp divides a21a^2 - 1. Then:
p(a2a+1)(a21)=a2 p \mid (a^2 - a + 1) - (a^2 - 1) = a - 2
Therefore:
pa(a2)(a21)=2a1 p \mid a(a - 2) - (a^2 - 1) = 2a - 1
This implies:
p(2a1)2(a2)=3 p \mid (2a - 1) - 2(a - 2) = 3
Hence, p=3p = 3.

7. We conclude that the only prime divisor of a2a+1a^2 - a + 1 is 33. Let:
a2a+1=3β a^2 - a + 1 = 3^\beta
If β2\beta \geq 2, then a2a+10(mod9)a^2 - a + 1 \equiv 0 \pmod{9}. Checking all residues modulo 9 for aa, we find this is impossible. Therefore, β=1\beta = 1, and:
a2a+1=3 a^2 - a + 1 = 3
Solving this quadratic equation:
a2a2=0 a^2 - a - 2 = 0
Factoring:
(a2)(a+1)=0 (a - 2)(a + 1) = 0
Thus, a=2a = 2 (since a>1a > 1).

The final answer is a=2 \boxed{ a = 2 } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.