Carmichael Number

Author

Eric W. Weisstein
August 31, 2015

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/CarmichaelNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/CarmichaelNumber.html.

©2015 Wolfram Research, Inc. except for portions noted otherwise

Code

CarmichaelQ::usage="CarmichaelQ[n] returns True if n is a Carmichael number (odd composite which is a pseudoprime to every realtively prime base less than n).";

CarmichaelQ[n_Integer?EvenQ]:=False
CarmichaelQ[n_Integer?PrimeQ]:=False
CarmichaelQ[n_Integer?OddQ]:=Module[{a=2},
While[a<n&&(GCD[a,n]≠1||Mod[a^(n-1)-1,n]==0),a++];
(a==n)
]

Enumeration

Position[Range[10^4],_?CarmichaelQ]//Flatten//Timing

Position[Range[10^5],_?CarmichaelQ]//Flatten//Timing

Table[Count[{561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361},_?(#<10^n&)],{n,5}]

l={0,0,1,7,16,43,105,255,646,1547,3605,8241,19279,44706,105212,246683};

Dubner

Something is wrong here

factors=With[{k=133752260 3003 10^1604},{(6k+1),(12k+1),(18k+1)}];

{Digits[Times@@factors],Digits/@factors}

PrimeQ/@factors

Primes

3-factor

4-factor

Broadhurst 2003

https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1508&L=NMBRTHRY&P=6285

In this carefully constructed case, all 4  BLS primality proofs for P,Q,R,S were easy:

http://primes.utm.edu/primes/page.php?id=26046
http://primes.utm.edu/primes/page.php?id=26043
http://primes.utm.edu/primes/page.php?id=63685
http://primes.utm.edu/primes/page.php?id=63686

m=990134653314716678714869901*2^16008;
P=6*m+1;
Q=12*m+1;
R=2052776910*m+1;
S=(R*(9*(8*m+1)^2-1)-8)/98216+1;
C4=P*Q*R*S;

IntegerLength[C4]

IntegerLength/@{P,Q,R,S}

Print[Timing[PrimeQ[#]]]&/@{P,Q,R,S};

TimeConstrained[PrimeQ[C4],60]//Timing

6-factor

Primorial[k_]:=Times@@Prime[Range[PrimePi[k]]]

Broadhurst 2003

https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1508&L=NMBRTHRY&P=R628

http://primes.utm.edu/primes/page.php?id=63867
http://primes.utm.edu/primes/page.php?id=63866
http://primes.utm.edu/primes/page.php?id=63865
http://primes.utm.edu/primes/page.php?id=63872
http://primes.utm.edu/primes/page.php?id=63871
http://primes.utm.edu/primes/page.php?id=63870

P=((((122325527 131834679855478128279035589802534760964641 Primorial[31] 15 2^3337+19)^2-1) 122325527 131834679855478128279035589802534760964641 Primorial[31] 5 2^3329/3+146901611060987)^2-146901611060987^2) 40389706714951606997880073568/377974016181285958115511+1;

Q=((((122325527 131834679855478128279035589802534760964641 Primorial[31] 15 2^3337+19)^2-1) 122325527 131834679855478128279035589802534760964641 Primorial[31] 5 2^3329/3+146901611060987)^2-146901611060987^2) 16/1889870080906429790577555+1;

R=((122325527 131834679855478128279035589802534760964641 Primorial[31] 15 2^3337+19)^2-1) 122325527 131834679855478128279035589802534760964641 Primorial[31] 2^3331/705127733092737+1;

S=122325527 131834679855478128279035589802534760964641 Primorial[31] 15 2^3336+1;

T=122325527 131834679855478128279035589802534760964641 Primorial[31] 5 2^3335+1;

U=122325527 131834679855478128279035589802534760964641 Primorial[31] 5 2^3334+1;

C6=P Q R S T U;

IntegerLength[C6]

IntegerLength/@{P,Q,R,S,T,U}

Print[Timing[PrimeQ[#]]]&/@{P,Q,R,S,T,U};

TimeConstrained[PrimeQ[C6],60]//Timing