cp's OEIS Frontend

A208728 Composite numbers n such that b^(n+1) == 1 (mod n) for every b coprime to n.

%I A208728 #76 Feb 16 2025 08:33:16
%S A208728 15,35,255,455,1295,2703,4355,6479,9215,10439,11951,16211,23435,27839,
%T A208728 44099,47519,47879,62567,63167,65535,93023,94535,104195,120959,131327,
%U A208728 133055,141155,142883,157079,170819,196811,207935,260831,283679,430199,560735,576719
%N A208728 Composite numbers n such that b^(n+1) == 1 (mod n) for every b coprime to n.
%C A208728 GCD(b,n)=1 and b^(n+1) == 1 (mod n).
%C A208728 The sequence lists the squarefree composite numbers n such that every prime divisor p of n satisfies (p-1)|(n+1) (similar to Korselt's criterion).
%C A208728 The sequence can be considered as an extension of k-Knödel numbers to k negative, in this case equal to -1.
%C A208728 Numbers n > 3 such that b^(n+2) == b (mod n) for every integer b. Also, numbers n > 3 such that A002322(n) divides n+1. Are there infinitely many such numbers? It seems that such numbers n > 35 have at least three prime factors. - _Thomas Ordowski_, Jun 25 2017
%C A208728 Proof that 15 and 35 are the only numbers with only two prime factors (and so all others have >= 3): Since n is squarefree and composite, it has at least two prime factors, p and q. If these are the only two, n = p*q. Then the criterion is that (p-1)|(n+1) -> (p-1)|pq+1, and q-1|pq+1. Write pq+1 = j*(p-1) = k*(q-1). Rearranging, p*(j-q)=j+1 and q*(k-p)=k+1. Since j = (pq+1)/(p-1), for large n, j~=q, and k~=p. But we see that p divides j+1~=q, and q divides k+1~=p. For large n this is only possible if p and q are roughly equal, so j-q=k-p=1. Otherwise, we have j+1 >= 2*p and k+1 >= 2*q, and which puts upper bounds on p and q. Enumerating these gives (p,q)=(3,5) and (p,q)=(5,7) as the only solutions. - _Alex Meiburg_, Oct 03 2024
%H A208728 Charles R Greathouse IV, <a href="/A208728/b208728.txt">Table of n, a(n) for n = 1..1000</a>
%H A208728 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CarmichaelNumber.html">Carmichael Number</a>
%H A208728 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KorseltsCriterion.html">Korselt's Criterion</a>
%H A208728 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnoedelNumbers.html">Knödel Numbers</a>
%e A208728 6479 is part of the sequence because its prime factors are 11, 19 and 31: (6479+1)/(11-1)=648, (6479+1)/(19-1)=360 and (6479+1)/(31-1)=216.
%p A208728 with(numtheory); P:=proc(n) local d, ok, p;
%p A208728 if issqrfree(n) then p:=factorset(n); ok:=1;
%p A208728 for d from 1 to nops(p) do if frac((n+1)/(p[d]-1))>0 then ok:=0;
%p A208728 break; fi; od; if ok=1 then n; fi; fi; end: seq(P(i),i=5..576719);
%t A208728 Select[Range[2, 576719], SquareFreeQ[#] && ! PrimeQ[#] && Union[Mod[# + 1, Transpose[FactorInteger[#]][[1]] - 1]] == {0} &] (* _T. D. Noe_, Mar 05 2012 *)
%o A208728 (PARI) is(n)=if(isprime(n)||!issquarefree(n)||n<3, return(0)); my(f=factor(n)[, 1]); for(i=1, #f, if((n+1)%(f[i]-1), return(0))); 1 \\ _Charles R Greathouse IV_, Mar 05 2012
%Y A208728 Cf. A002322, A002997, A006972, A033553, A050990, A050992, A050993, A208154-A208158.
%K A208728 nonn
%O A208728 1,1
%A A208728 _Paolo P. Lava_, Mar 01 2012
%E A208728 Definition corrected by _Thomas Ordowski_, Jun 25 2017