A254444 Largest k such that p = prime(n) satisfies b^(p-1) == 1 (mod p^k) for some base b with 1 < b < p.

1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 3, 2, 2, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1

Offset: 2

Author

Felix Fröhlich, May 04 2015

Keywords

• nonn

Comments

a(n) > 1 iff p is in A134307.

Meyer proved in 1902 that for any prime p exactly p - 1 bases b with b < p^k exist such that b^(p-1) == 1 (mod p^k) (cf. Keller, Richstein, 2005, page 930).

a(30) = 3 is the first term with a value > 2, corresponding to prime(30) = 113 (see the comment from 2011 in A134307). This is the first case where A249275(n) < A000040(n).

Do the values of this sequence have an upper bound or, more formally, does this sequence have a supremum?

Examples

			With p = 113: For all bases b with 1 < b < 113, p (trivially) satisfies b^112 == 1 (mod 113^k) for k = 1 and for no k > 1, with the single exception of b = 68, where p satisfies the congruence for k = 3 (and hence for k = 1 and k = 2). Since 3 is the largest value of k for all 1 < b < 113, a(30) = 3.
		

Links

• Felix Fröhlich, Table of n, a(n) for n = 2..10000
• W. Keller and J. Richstein, Solutions of the congruence a^p-1 == 1 (mod p^r), Math. Comp., 74 (2005), 927-936.

Crossrefs

Cf. A134307.

Programs

PARI

forprime(p=3, 400, k=1; maxk=0; for(b=2, p-1, while(Mod(b, p^k)^(p-1)==1, k++); if(k-1 > maxk, maxk=k-1)); print1(maxk, ", "))