A102457 Least k >= 2 with n^(kn) == n (mod kn), also n^(kn-1) == 1 (mod k).

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

Offset: 2

Author

David W. Wilson, Jan 09 2005

Keywords

• nonn

Comments

Motivated by even base-2 pseudoprime 161038, I inquired into base-n pseudoprimes kn that are multiples of n, i.e., n^(kn) == n (mod kn). This is equivalent to n^(kn-1) == 1 (mod k) [W. Edwin Clark] and is satisfied by any k dividing n-1 [Michael Reid]. For n >= 3, this guarantees the existence of a(n) with 2 <= a(n) = k <= lpf(n-1) (lpf = least prime factor). For most n, a(n) = lpf(n-1), exceptional n and a(n) are noted in A102458 and A102459.

Links

• Antti Karttunen, Table of n, a(n) for n = 2..12620
• Antti Karttunen, Data supplement: n, a(n) computed for n = 2..100000

Crossrefs

Cf. A102458, A102459.

Cf. A092067. - R. J. Mathar, Aug 30 2008

Programs

Mathematica

Array[Block[{k = 2}, While[PowerMod[#, k # - 1, k] != 1, k++]; k] &, 93, 2] (* Michael De Vlieger, Nov 13 2018 *)

PARI

A102457(n) = { for(k=2, oo, if(1==(Mod(n, k)^((k*n)-1)), return(k)); ); } \\ Antti Karttunen, Nov 10 2018