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,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.

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

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

Cf. A105222.

Sequence in context: A029640 A029658 A332889 * A368468 A069930 A086327

Adjacent sequences: A239449 A239450 A239451 * A239453 A239454 A239455

Keyword

nonn

Author

Robert FERREOL, Mar 19 2014

Extensions

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

Status

approved