mersenneforum.org Good Carmichael Number construction algorithm?
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-04, 07:06 #1 carpetpool     "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(p-1,q-1,r-1)=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(p-1,q-1,r-1)=2). We already know that: q*r = 1 (mod p-1) r*p = 1 (mod q-1) and q*p = 1 (mod r-1) 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(p-1,r-1,q-1) = 2, and r < q < p. One would start by setting up the equivalences: q*r = 1 (mod 4800) q*4801 = 1 (mod r-1) r*4801 = 1 (mod q-1) But from here it seems that I am stuck. Any help? Thanks!
 2018-03-04, 07:38 #2 CRGreathouse     Aug 2006 176316 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,p-6, if(gcd(r,p-1)>1, next); my(q=lift(Mod(1/r,p-1))); if(q>r && q

2, next); my(q=lift(Mod(1/r,p-1))); if(q>r && q

 2018-03-04, 13:19 #3 JM Montolio A   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.
2018-03-04, 13:51   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by JM Montolio A I find some rules on totient(n)=k. Can be we can make the last step. JM M.
totient(n) is multiplicative to distinct prime factors of n.

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 5 2016-10-08 09:05 ixfd64 Hardware 11 2011-11-02 23:54 Erasmus Other Mathematical Topics 12 2010-04-13 23:33 flouran Math 2 2009-05-08 21:37 wpolly Math 0 2004-12-01 11:14

All times are UTC. The time now is 21:17.

Tue Jan 31 21:17:07 UTC 2023 up 166 days, 18:45, 0 users, load averages: 1.45, 1.12, 0.98