- **Miscellaneous Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=56*)

- - **Good Carmichael Number construction algorithm?**
(*https://www.mersenneforum.org/showthread.php?t=23126*)

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! |

Each of the phi(4800) = 1280 residue classes coprime to 4800 are ([i]a priori[/i]) 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<p && isprime(q) && p*q%(r-1)==1 && p*r%(q-1)==1, return(p*q*r))) findSpecialCar3(p)=forprime(r=3,p-6, if(gcd(r^2-r,p-1)>2, next); my(q=lift(Mod(1/r,p-1))); if(q>r && q<p && isprime(q) && p*q%(r-1)==1 && p*r%(q-1)==1 && gcd(q-1, p-1)==2 && gcd(q-1,r-1)==2, return(p*q*r))) findCar3(4801) findSpecialCar3(4801) \\ none to find[/code] |

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

[QUOTE=JM Montolio A;481534]I find some rules on totient(n)=k.
Can be we can make the last step. JM M.[/QUOTE] totient(n) is multiplicative to distinct prime factors of n. |

All times are UTC. The time now is 11:50. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.