Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)^{n} + 1 is divisible by n^{p-1}.

**Answer**

(1, p) for any prime p; (2, 2); (3, 3).

**Solution**

*by Gerhard Woeginger, Technical University, Graz*

Answer: (1, p) for any prime p; (2, 2); (3, 3).

Evidently (1, p) is a solution for every prime p. Assume n > 1 and take q to be the smallest prime divisor of n. We show first that q = p.

Let x be the smallest positive integer for which (p - 1)^{x} = - 1 (mod q), and y the smallest positive integer for which (p - 1)^{y} = 1 (mod q). Certainly y exists and indeed y < q, since (p - 1)^{q-1} = 1 (mod q). We know that (p - 1)^{n} = -1 (mod q), so x exists also. Writing n = sy + r, with 0 ≤ r < y, we conclude that (p - 1)^{r} = -1 (mod q), and hence x ≤ r < y (r cannot be zero, since 1 is not -1 (mod q) ).

Now write n = hx + k with 0 ≤ k < x. Then -1 = (p - 1)^{n} = (-1)^{h}(p - 1)^{k} (mod q). h cannot be even, because then (p - 1)^{k} = -1 (mod q), contradicting the minimality of x. So h is odd and hence (p - 1)^{k} = 1 (mod q) with 0 ≤ k < x < y. This contradicts the minimality of y unless k = 0, so n = hx. But x < q, so x = 1. So (p - 1) = -1 (mod q). p and q are primes, so q = p, as claimed.

So p is the smallest prime divisor of n. We are also given that n ≤ 2p. So either p = n, or p = 2, n = 4. The latter does not work, so we have shown that n = p. Evidently n = p = 2 and n = p = 3 work. Assume now that p > 3. We show that there are no solutions of this type.

Expand (p - 1)^{p} + 1 by the binomial theorem, to get (since (-1)^{p} = -1): 1 + -1 + p^{2} - 1/2 p(p - 1)p^{2} + p(p - 1)(p - 2)/6 p^{3} - ...

The terms of the form (bin coeff) p^{i} with i >= 3 are obviously divisible by p^{3}, since the binomial coefficients are all integral. Hence the sum is p^{2} + a multiple of p^{3}. So the sum is not divisible by p^{3}. But for p > 3, p^{p-1} is divisible by p^{3}, so it cannot divide (p - 1)^{p} + 1, and there are no more solutions.

© John Scholes

jscholes@kalva.demon.co.uk

7 Sep 1999

Last corrected/updated 19 Aug 03