Let f(n) = 1 + 2n + 3n2 + ... + (p - 1)np-2, where p is an odd prime. Prove that if f(m) = f(n) (mod p), then m = n (mod p).
Solution
Clearly if n = 0 (mod p), then f(n) = 1 (mod p). Similarly, if n = 1 (mod p), then f(n) = 1 + 2 + ... + (p - 1) = p(p - 1)/2 = 0 (mod p).
Otherwise we have (1 - n) f(n) = 1 + n + n2 + ... + np-2 - (p-1)np-1. Hence (1 - n)2 f(n) = 1 - pnp-1 + (p - 1)np = 1 + (p-1)np = 1 + (p-1)n = 1 - n (mod p). Since we are assuming n ≠ 1, 1 - n is invertible and we have f(n) = (1 - n)-1. Note that this cannot have the value 1 (because (1 - n)-1 = 1 implies 1.(1 - n) = 1 implies n = 0) or 0 (because we cannot have 0.(1 - n) = 1).
So suppose f(n) = f(m) (mod p). If the common value is 0 or 1, then n and m are both 1 (mod p) or both 0 (mod p) and hence equal. If the common value is not 0 or 1, then (1 - n)-1 = (1 - m)-1 (mod p), hence (1 - n) = (1 - m) (mod p) and n = m (mod p).
© John Scholes
jscholes@kalva.demon.co.uk
16 Jan 2001