# Math Help - Carmichael numbers

1. ## A new direction...

I’ve got you to $lcm(a_1,a_2,a_3)|gcd(a_2a_3+a_1a_3+a_1a_2 , a_1+a_2+a_3)$

Now, let’s keep going. Define $g=gcd(a_1,a_2,a_3)$ and let $u_1=a_1/g$ , $u_2=a_2/g$ , $u_3=a_3/g$ .

Then $u_1u_2u_3g|gcd((u_2u_3+u_1u_3+u_1u_2 )g^2, (u_1+u_2+u_3)g)$

Or, alternatively:

$u_1|u_2u_3(gk)+(u_2+u_3)$
$u_2|u_1u_3(gk)+(u_1+u_3)$
$u_3|u_2u_1(gk)+(u_2+u_1)$

In order to satisfy this for all $k$, $u_1u_2u_3|g$ and $u_1u_2u_3|u_1+u_2+u_3$ . This calls for three relatively prime integers whose product divides their sum. I believe $1,2,3$ is the only such arrangement, leading us into a dead end.

However, after looking at some raw data, it looks like $gcd(p_1-1,p_2-1,p_3-1)$ and subsequent $p_1/g, p_2/g, p_3/g$ are all over the map. This leads me to pose another conjecture:

Weak: For any three relatively prime $u_1, there exists a $k$ such that $(u_1k+1) (u_2k+1) (u_3k+1)$ is a three-factor Carmichael Number.

Strong: For any three relatively prime $u_1, there exists an $a,b$ such that $(u_1k+1) (u_2k+1) (u_3k+1)$ is a three-factor Carmichael Number iff $k \equiv b (\bmod a)$ and $u_ik+1$ is prime for all $i$.

Examples:
For $u=(1,2,3), a=6, b=0$ generates Carmichaels 1729, 294409, 56052361, 118901521 …
For $u=(1,3,5), a=30, b=12$ generates Carmichaels 29341, 1152271, 64377911, 775368901 …
For $u=(1,4,7), a=28, b=4$ generates Carmichaels 2465, 6189121, 19384289, 34153717249 …

2. Originally Posted by Media_Man
I’ve got you to $lcm(a_1,a_2,a_3)|gcd(a_2a_3+a_1a_3+a_1a_2 , a_1+a_2+a_3)$

Now, let’s keep going. Define $g=gcd(a_1,a_2,a_3)$ and let $u_1=a_1/g$ , $u_2=a_2/g$ , $u_3=a_3/g$ .

Then $u_1u_2u_3g|gcd((u_2u_3+u_1u_3+u_1u_2 )g^2, (u_1+u_2+u_3)g)$
I'll have to take some time to think about your other conjectures, however you should know that we do not in general have the equality $lcm(a_1,a_2,a_3)=u_1u_2u_3g$, where $g=gcd(a_1,a_2,a_3)$. Notice that having the property $gcd(u_1,u_2,u_3)=1$ does not necessarily imply that $gcd(u_i,u_j)=1$ for each distinct $i,j$.

3. Originally Posted by Media_Man

However, after looking at some raw data, it looks like $gcd(p_1-1,p_2-1,p_3-1)$ and subsequent $p_1/g, p_2/g, p_3/g$ are all over the map.
Suppose $n=p_1p_2p_3$ is a Carmichael and let $D =gcd(p_1-1,p_2-1,p_3-1)$. Try finding out what the number of (approximately) distinct values the ratio $n/D$ can take for all Carmichaels $n$ bounded above by some integer N (ex N=10,000, N=100,000 etc).

What are the smallest and/or average values of $n/D$ for various N?

Page 2 of 2 First 12