Maths Olympiad Prep

Track / Stage 7 / 248 of 300 #2288 of 2604

Problem 2288

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.8 Find the answer IMO Shortlist

Find all positive integers n n such that there exists a unique integer a a such that 0≤a<n! 0\leq a < n! with the following property:
n! a n 1\text{n! a n 1}

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

Let us consider the problem of finding all positive integers n n for which there exists a unique integer a a such that 0≤a<n! 0 \leq a < n! and

n!∣an+1. n! \mid a^n + 1.

### Step-by-step Solution:

1. Understand the Divisibility Condition:

We require that an+1≡0(modn!) a^n + 1 \equiv 0 \pmod{n!} , meaning:

an≡−1(modn!). a^n \equiv -1 \pmod{n!}.

2. Explore Special Cases and General Patterns:

**Case n=1 n = 1 :**

- For n=1 n = 1 , we seek 0≤a<1!=1 0 \leq a < 1! = 1 , so a=0 a = 0 .
- Then, a1+1=01+1=1≡0(mod1) a^1 + 1 = 0^1 + 1 = 1 \equiv 0 \pmod{1} , which holds.

Hence, n=1 n = 1 is a solution.

**Case n n is a Prime:**

- Let n n be a prime number.
- Wilson's Theorem states (n−1)!≡−1(modn) (n-1)! \equiv -1 \pmod{n} , implying for a=n−1 a = n-1 , we have:
(n−1)n=(n−1)n−1⋅(n−1)≡(−1)n−1⋅(n−1)≡−1≡0(modn). (n-1)^n = (n-1)^{n-1} \cdot (n-1) \equiv (-1)^{n-1} \cdot (n-1) \equiv -1 \equiv 0 \pmod{n}.
- We need (n−1)n+1≡0(modn!) (n-1)^n + 1 \equiv 0 \pmod{n!} .
- Notice if k=n−1 k = n-1 , (n−1)!≡−1(modn) (n-1)! \equiv -1 \pmod{n} implies:

(n−1)n≡−1≡0(modn!). (n-1)^n \equiv -1 \equiv 0 \pmod{n!}.

- Unique a=n−1 a = n-1 exists and satisfies the conditions for primes.

Thus, all prime numbers n n also satisfy the condition as they create a unique choice for a=n−1 a = n-1 .

3. Check if Further Conditions Can Be Satisfied:

- For composite n n , any a a less than n! n! that works has non-uniqueness due to additional factors canceling divisors.

4. Conclusion:

By examining divisibility and uniqueness conditions, we find that:

All prime numbers or n=1 \boxed{\text{All prime numbers or } n = 1}

These are the solutions where a unique a a can be found satisfying the given condition.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.