A239452 Smallest integer m > 1 such that m^n == m (mod n).

2, 2, 2, 4, 2, 3, 2, 8, 8, 5, 2, 4, 2, 7, 4, 16, 2, 9, 2, 5, 6, 11, 2, 9, 7, 13, 26, 4, 2, 6, 2, 32, 10, 17, 6, 9, 2, 19, 12, 16, 2, 7, 2, 12, 8, 23, 2, 16, 18, 25, 16, 9, 2, 27, 10, 8, 18, 29, 2, 16, 2, 31, 8, 64, 5, 3, 2, 17, 22, 11, 2, 9, 2, 37, 24, 20, 21

Offset: 1

Author

Robert FERREOL, Mar 19 2014

Keywords

• nonn

Comments

Composite n are Fermat weak pseudoprimes to base a(n).

If n > 2 is prime then a(n) = 2. The converse is false : a(341) = 2 and 341 isn't prime.

a(n) <= A105222(n). a(n) = A105222(n) if and only if a(n) is coprime to n.

For n > 1, a(n) <= n and if a(n) = n, then A105222(n) = n+1.

It seems that a(n) = n if and only if n = 2^k with k > 0, a(n) = n-1 if and only if n = 3^k with k > 0, a(2n) = n if and only if n = p^k where p is an odd prime and k > 0. - Thomas Ordowski, Oct 19 2017

Examples

			We have 2^4 != 2, 3^4 != 3, but 4^4 == 4 (mod 4), so a(4) = 4.
		

Links

• Giovanni Resta, Table of n, a(n) for n = 1..10000
• Gérard P. Michon, Weak pseudoprimes to base a

Crossrefs

Cf. A105222.

Programs

Haskell

import Math.NumberTheory.Moduli (powerMod)
a239452 n = head [m | m <- [2..], powerMod m n n == mod m n]
-- Reinhard Zumkeller, Mar 19 2014

Maple

L:=NULL:for n to 100 do for a from 2 while a^n - a mod n !=0 do od; L:=L,a od: L;

Mathematica

a[n_] := Block[{m = 2}, While[PowerMod[m, n, n] != Mod[m, n], m++]; m]; Array[a, 100] (* Giovanni Resta, Mar 19 2014 *)

PARI

a(n)=my(m=2); while(Mod(m,n)^n!=m, m++); m \\ Charles R Greathouse IV, Mar 21 2014

Python

L=[];
for n in range(1,101):
   a=2
   while (a**n - a) % n != 0:
      a+=1
   L=L+[a]
L

Extensions

a(20)-a(77) from Giovanni Resta, Mar 19 2014