Find all positive integers a, m, n such that am + 1 divides (a + 1)n.
Solution
Answer: (a, m, n) = (1, m, n), (a, 1, n) or (2, 3, k) where k > 1.
It is obvious that (1, m, n) and (a, 1, n) are solutions, so assume a > 1 and m > 1. We show first that m must be odd.
Suppose there is an odd prime p dividing am + 1. Then p must also divide (a + 1)n and hence (a + 1). So a = -1 mod p, so am + 1 = (-1)m + 1 mod p. Hence m is odd. If there is no such prime p, then am + 1 = 2k for some k. But a and m are assumed to be at least 2, so am + 1 must be at least 5 and hence k ≥ 3. So am = -1 mod 4. But squares can only be 0 or 1 mod 4, so am cannot be a square, so m must be odd.
Suppose p divides m. Then (since m is odd) ap + 1 divides am + 1 and hence (a + 1)n. But p is odd, so a + 1 divides ap + 1 and (ap + 1)/(a + 1) = ap-1 - ap-2 + ap-3 - ... - p + 1 divides (a + 1)n-1. Put f(x) = xp-1 - xp-2 + ... - x + 1. Then f(-1) = p, so f(x) - p = (x + 1) g(x) for some polynomial g(x). Putting x = a, we get f(a) = (a + 1) g(a) + p. If a prime q divides f(a), then since f(a) divides (a + 1)n-1, q must divide (a + 1). Hence q divides p, so q = p. So f(a) = pk for some k ≥ 1. Since f(a) divides (a + 1)n-1, p must divide a + 1.
We show next that k = 1, so f(a) = p. If p2 divides (a + 1), then f(a) = (a + 1) g(a) + p implies that p2 does not divide f(a). If p2 does not divide (a + 1), then (a + 1) = ph (with h not divisible by p). So f(a) = (ap + 1)/(a + 1) = ( (1 + ph - 1)p)/ph = ( 1 - 1 + p2h + terms divisible by p3)/ph = p mod p2, so again p2 does not divide f(a). So in any case f(a) = p.
Now (a2 - a) ≥ 2, (a4 - a3) ≥ 8 and obviously (a2r - a2r-1) ≥ 2 for r ≥ 2. So f(a) ≥ 11 > 5 for p = 5, and hence by a trivial induction f(a) > p for p > 5. So the only possibility is p = 3. Then we have a2 - a + 1 = 3 and hence a = 2.
So far we have established that a = 2 and that m is a power of 3. But (29 + 1) = 513, which is not a power of 3 and so cannot divide (2 + 1)n. But (227 + 1), (281 + 1), ... are all divisible by (29 + 1) and hence are also not powers of 3. So m must be 3. Finally, we require that (am + 1) = 9 divides (2 + 1)n, so n ≥ 2.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002