mersenneforum.org Good Carmichael Number construction algorithm?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-04, 07:06 #1 carpetpool     "Sam" Nov 2016 22×34 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 3·1,993 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 1408 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
Dumbassville

26×131 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 20:29.

Mon Sep 20 20:29:52 UTC 2021 up 59 days, 14:58, 0 users, load averages: 2.72, 2.66, 2.56