cp's OEIS Frontend

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

%I A239452 #40 May 22 2025 10:21:37
%S A239452 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 A239452 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 A239452 16,2,31,8,64,5,3,2,17,22,11,2,9,2,37,24,20,21
%N A239452 Smallest integer m > 1 such that m^n == m (mod n).
%C A239452 Composite n are Fermat weak pseudoprimes to base a(n).
%C A239452 If n > 2 is prime then a(n) = 2. The converse is false : a(341) = 2 and 341 isn't prime.
%C A239452 a(n) <= A105222(n). a(n) = A105222(n) if and only if a(n) is coprime to n.
%C A239452 For n > 1, a(n) <= n and if a(n) = n, then A105222(n) = n+1.
%C A239452 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 A239452 Giovanni Resta, <a href="/A239452/b239452.txt">Table of n, a(n) for n = 1..10000</a>
%H A239452 Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm#weak">Weak pseudoprimes to base a</a>
%e A239452 We have 2^4 != 2, 3^4 != 3, but 4^4 == 4 (mod 4), so a(4) = 4.
%p A239452 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 A239452 a[n_] := Block[{m = 2}, While[PowerMod[m, n, n] != Mod[m, n], m++]; m]; Array[a, 100] (* _Giovanni Resta_, Mar 19 2014 *)
%o A239452 (Haskell)
%o A239452 import Math.NumberTheory.Moduli (powerMod)
%o A239452 a239452 n = head [m | m <- [2..], powerMod m n n == mod m n]
%o A239452 -- _Reinhard Zumkeller_, Mar 19 2014
%o A239452 (Python)
%o A239452 L=[];
%o A239452 for n in range(1,101):
%o A239452    a=2
%o A239452    while (a**n - a) % n != 0:
%o A239452       a+=1
%o A239452    L=L+[a]
%o A239452 L
%o A239452 (PARI) a(n)=my(m=2); while(Mod(m,n)^n!=m, m++); m \\ _Charles R Greathouse IV_, Mar 21 2014
%Y A239452 Cf. A105222.
%K A239452 nonn
%O A239452 1,1
%A A239452 _Robert FERREOL_, Mar 19 2014
%E A239452 a(20)-a(77) from _Giovanni Resta_, Mar 19 2014