It is no longer surprising that there are even pseudoprimes 2n for which 2^(2n) == 2 (mod 2n) specifically, 2n = 161038 (see A006935). 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 Superficially, this appears to be k(m) = 80519, if m = 2 lpf(m-1), if m > 2. where lpf(x) is the least prime factor of x (A020639). I assume we can prove that k = lpf(m-1) satisfies [1], any takers? But maybe things aren't so simple. According to my program, there are some m for which k(m) < lpf(m-1). In particular: k(152) = 143 < 151 = lpf(152-1) k(158) = 77 < 157 = lpf(158-1) k(338) = 161 < 337 = lpf(338-1) k(368) = 77 < 367 = lpf(368-1) k(380) = 299 < 379 = lpf(380-1) k(524) = 437 < 523 = lpf(524-1) k(542) = 143 < 541 = lpf(542-1) k(548) = 77 < 547 = lpf(548-1) k(608) = 407 < 607 = lpf(608-1) k(614) = 611 < 613 = lpf(614-1) k(662) = 581 < 661 = lpf(662-1) k(674) = 319 < 673 = lpf(674-1) k(692) = 377 < 691 = lpf(692-1) k(998) = 161 < 997 = lpf(998-1) ... These may actually be discrepancies, however, there is also the distinct possibility of computational error, so maybe someone could verify or refute these values?