Go Back > Extra Stuff > Miscellaneous Math

Thread Tools
Old 2018-03-04, 07:06   #1
carpetpool's Avatar
Nov 2016

23·41 Posts
Post 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)


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!
carpetpool is offline   Reply With Quote
Old 2018-03-04, 07:38   #2
CRGreathouse's Avatar
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:

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

findSpecialCar3(4801) \\ none to find

Last fiddled with by CRGreathouse on 2018-03-04 at 07:39
CRGreathouse is offline   Reply With Quote
Old 2018-03-04, 13:19   #3
JM Montolio A
Feb 2018

9610 Posts
Smile 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 Montolio A is offline   Reply With Quote
Old 2018-03-04, 13:51   #4
science_man_88's Avatar
"Forget I exist"
Jul 2009

26·131 Posts

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

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 2016-10-08 09:05
are blade servers good for number crunching? ixfd64 Hardware 11 2011-11-02 23:54
Suggestions on good number theory books??? Erasmus Other Mathematical Topics 12 2010-04-13 23:33
Carmichael Number Paper flouran Math 2 2009-05-08 21:37
Lucas-Carmichael number wpolly Math 0 2004-12-01 11:14

All times are UTC. The time now is 15:16.

Mon Nov 29 15:16:10 UTC 2021 up 129 days, 9:45, 0 users, load averages: 1.91, 1.64, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.