OFFSET

1,1

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.

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

LINKS

Giovanni Resta, Table of n, a(n) for n = 1..10000

GĂ©rard P. Michon, Weak pseudoprimes to base a

EXAMPLE

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

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 *)

PROG

(Haskell)

import Math.NumberTheory.Moduli (powerMod)

a239452 n = head [m | m <- [2..], powerMod m n n == mod m n]

-- Reinhard Zumkeller, Mar 19 2014

(Python)

L=[];

for n in range(1, 101):

...a=2

...while (a**n - a) % n != 0:

......a+=1

...L=L+[a]

L

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

CROSSREFS

KEYWORD

nonn

AUTHOR

Robert FERREOL, Mar 19 2014

EXTENSIONS

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

STATUS

approved