Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)n + 1 is divisible by np-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 + p2 - 1/2 p(p - 1)p2 + p(p - 1)(p - 2)/6 p3 - ...
The terms of the form (bin coeff) pi with i >= 3 are obviously divisible by p3, since the binomial coefficients are all integral. Hence the sum is p2 + a multiple of p3. So the sum is not divisible by p3. But for p > 3, pp-1 is divisible by p3, 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