On Sat, 8 Jan 2005, David Wilson wrote:
This got me to wondering if there were always multiples of This got me to wondering if for any m, there always exists k >= 2 satisfying
[1] m^(km) == m (mod km)
and if so, what would the least such k(m) be?
Empirically, it looks as if k(m) exists for all m, and programmatically I got the following k(m) for 2 <= m <= 100.
80519,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,17,2,19,2,3,2,23,2,5,2,3,2,29,2,31, 2,3,2,5,2,37,2,3,2,41,2,43,2,3,2,47,2,7,2,3,2,53,2,5,2,3,2,59,2,61,2,3,2,5, 2,67,2,3,2,71,2,73,2,3,2,7,2,79,2,3,2,83,2,5,2,3,2,89,2,7,2,3,2,5,2,97,2,3
I assume we can prove that k = lpf(m-1) satisfies [1], any takers?
I agree with all your data. Also the following is easy to prove: Lemma. If d is any integer > 1 dividing m-1 then m^(md) ==m mod md. Hence k(m) is well-defined for m > 2 and at most p where p is the smallest prime dividing m - 1. Proof. d | m-1 means m == 1 mod d. Hence m^(md-1) == 1 mod d Multiplying both sides by m we get the result. QED. Note we may also define k(m) to be the least d such that m^(md-1) == 1 mod d. That is the least d such that gcd(m,d) = 1 and the order of m mod d divides md - 1. Since the order of m mod d is not very predictable in general, it is hard to see how one could find a simple expression for k(m). --Edwin --------------------------------------------------------- W. Edwin Clark, Math Dept, University of South Florida http://www.math.usf.edu/~eclark/ ---------------------------------------------------------