20180304, 07:06  #1 
"Sam"
Nov 2016
5·67 Posts 
Good Carmichael Number construction algorithm?
Suppose you are given a prime p and it is the largest prime factor of n, a Carmichael number with three distinct prime factors: n = p*q*r where gcd(p1,q1,r1)=2?. Or in another case you are given two primes q and r of n and a prime p greater than q and r such that p*q*r is a Carmichael number (and of course gcd(p1,q1,r1)=2).
We already know that: q*r = 1 (mod p1) r*p = 1 (mod q1) and q*p = 1 (mod r1) It is easy (and trivial) to solve any two solutions but solving the third remaining equivalence is a matter of complexity. For example, suppose we are given p = 4801 (the largest prime factor of n) and asked to find primes q and r such that n = p*q*r is a Carmichael number, gcd(p1,r1,q1) = 2, and r < q < p. One would start by setting up the equivalences: q*r = 1 (mod 4800) q*4801 = 1 (mod r1) r*4801 = 1 (mod q1) But from here it seems that I am stuck. Any help? Thanks! 
20180304, 07:38  #2 
Aug 2006
1763_{16} Posts 
Each of the phi(4800) = 1280 residue classes coprime to 4800 are (a priori) possible for q and r. But once you pick one that fixes the other. So you can search like this:
Code:
findCar3(p)=forprime(r=3,p6, if(gcd(r,p1)>1, next); my(q=lift(Mod(1/r,p1))); if(q>r && q<p && isprime(q) && p*q%(r1)==1 && p*r%(q1)==1, return(p*q*r))) findSpecialCar3(p)=forprime(r=3,p6, if(gcd(r^2r,p1)>2, next); my(q=lift(Mod(1/r,p1))); if(q>r && q<p && isprime(q) && p*q%(r1)==1 && p*r%(q1)==1 && gcd(q1, p1)==2 && gcd(q1,r1)==2, return(p*q*r))) findCar3(4801) findSpecialCar3(4801) \\ none to find Last fiddled with by CRGreathouse on 20180304 at 07:39 
20180304, 13:19  #3 
Feb 2018
5·19 Posts 
Question. ¿Someone interested on try to solve the Carmichael conjecture?
I find some rules on totient(n)=k.
Can be we can make the last step. JM M. 
20180304, 13:51  #4 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 3: gcd, lcm & Euclid's algorithm  Nick  Number Theory Discussion Group  5  20161008 09:05 
are blade servers good for number crunching?  ixfd64  Hardware  11  20111102 23:54 
Suggestions on good number theory books???  Erasmus  Other Mathematical Topics  12  20100413 23:33 
Carmichael Number Paper  flouran  Math  2  20090508 21:37 
LucasCarmichael number  wpolly  Math  0  20041201 11:14 