Maths Olympiad Prep

Library / /29 of 144

Number theory Difficulty 7.8 National olympiad, round 2 Find the answer

Find all positive integers n n such that there exists a unique integer a a such that 0a<n! 0\leq a < n! with the following property:
n!an\plus1 n!\mid a^n \plus{} 1

*

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us consider the problem of finding all positive integers n n for which there exists a unique integer a a such that 0a<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+10(modn!) a^n + 1 \equiv 0 \pmod{n!} , meaning:

an1(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 0a<1!=1 0 \leq a < 1! = 1 , so a=0 a = 0 .
- Then, a1+1=01+1=10(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 (n1)!1(modn) (n-1)! \equiv -1 \pmod{n} , implying for a=n1 a = n-1 , we have:
(n1)n=(n1)n1(n1)(1)n1(n1)10(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 (n1)n+10(modn!) (n-1)^n + 1 \equiv 0 \pmod{n!} .
- Notice if k=n1 k = n-1 , (n1)!1(modn) (n-1)! \equiv -1 \pmod{n} implies:

(n1)n10(modn!). (n-1)^n \equiv -1 \equiv 0 \pmod{n!}.

- Unique a=n1 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=n1 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.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.