A239452 - OEIS

%I #38 Nov 16 2017 02:42:50

%S 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,

%T 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,

%U 16,2,31,8,64,5,3,2,17,22,11,2,9,2,37,24,20,21

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

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

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

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

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

%C 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

%H Giovanni Resta, <a href="/A239452/b239452.txt">Table of n, a(n) for n = 1..10000</a>

%H Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm#weak">Weak pseudoprimes to base a</a>

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

%p 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;

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

%o (Haskell)

%o import Math.NumberTheory.Moduli (powerMod)

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

%o -- _Reinhard Zumkeller_, Mar 19 2014

%o (Python)

%o L=[];

%o for n in range(1,101):

%o ...a=2

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

%o ......a+=1

%o ...L=L+[a]

%o L

%o (PARI) a(n)=my(m=2); while(Mod(m,n)^n!=m, m++); m \\ _Charles R Greathouse IV_, Mar 21 2014

%Y Cf. A105222.

%K nonn

%O 1,1

%A _Robert FERREOL_, Mar 19 2014

%E a(20)-a(77) from _Giovanni Resta_, Mar 19 2014