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

15, 35, 255, 455, 1295, 2703, 4355, 6479, 9215, 10439, 11951, 16211, 23435, 27839, 44099, 47519, 47879, 62567, 63167, 65535, 93023, 94535, 104195, 120959, 131327, 133055, 141155, 142883, 157079, 170819, 196811, 207935, 260831, 283679, 430199, 560735, 576719

Offset: 1

Author

Paolo P. Lava, Mar 01 2012

Keywords

• nonn

Comments

GCD(b,n)=1 and b^(n+1) == 1 (mod n).

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

The sequence can be considered as an extension of k-Knödel numbers to k negative, in this case equal to -1.

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

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

Examples

			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.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Carmichael Number
• Eric Weisstein's World of Mathematics, Korselt's Criterion
• Eric Weisstein's World of Mathematics, Knödel Numbers

Crossrefs

Cf. A002322, A002997, A006972, A033553, A050990, A050992, A050993, A208154-A208158.

Programs

Maple

with(numtheory); P:=proc(n) local d, ok, p;
if issqrfree(n) then p:=factorset(n); ok:=1;
for d from 1 to nops(p) do if frac((n+1)/(p[d]-1))>0 then ok:=0;
break; fi; od; if ok=1 then n; fi; fi; end: seq(P(i),i=5..576719);

Mathematica

Select[Range[2, 576719], SquareFreeQ[#] && ! PrimeQ[#] && Union[Mod[# + 1, Transpose[FactorInteger[#]][[1]] - 1]] == {0} &] (* T. D. Noe, Mar 05 2012 *)

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

Extensions

Definition corrected by Thomas Ordowski, Jun 25 2017