## Factorisation of Carmichael numbers

Expand Messages
• By inspection of a list of the first few Carmichael numbers, e.g. http://www.kobepharma-u.ac.jp/~math/notes/note02.html I have come to the following
Message 1 of 7 , May 27, 2010
By inspection of a list of the first few Carmichael numbers, e.g.
http://www.kobepharma-u.ac.jp/~math/notes/note02.html
I have come to the following

Conjecture: If n is a Carmichael number divisible by 3,
then all the other prime factors of n are congruent to 5 mod 6.

Does anyone know whether this result is well-known - or even true?
There doesn't seem to be an obvious proof.

Mike
• ... There are 1967 Carmichael numbers less than 10^18 that are divisible by 3 and your conjecture holds for all of them. David
Message 2 of 7 , May 27, 2010
"mikeoakes2" <mikeoakes2@...> wrote:

> Conjecture: If n is a Carmichael number divisible by 3,
> then all the other prime factors of n are congruent to 5 mod 6.

There are 1967 Carmichael numbers less than 10^18 that
are divisible by 3 and your conjecture holds for all of them.

David
• Well, if a Carmichael number C is divisible by both 3 and a prime of the form 6n+1, then you have a problem with fulfilling: a^C == a (modulo 6n+1) If a is a
Message 3 of 7 , May 27, 2010
Well, if a Carmichael number C is divisible by both 3 and a prime
of the form 6n+1, then you have a problem with fulfilling:

a^C == a (modulo 6n+1)

If a is a non-cubic-residue modulo 6n+1, this obviously can't
work, and note that all primes of the form 6n+1 have non-cubic-residues.

I think that's the outline of a proof -- I know I'm handwaving a little,
but I think you could fill in the blanks.

mikeoakes2 wrote:
> By inspection of a list of the first few Carmichael numbers, e.g.
> http://www.kobepharma-u.ac.jp/~math/notes/note02.html
> I have come to the following
>
> Conjecture: If n is a Carmichael number divisible by 3,
> then all the other prime factors of n are congruent to 5 mod 6.
>
> Does anyone know whether this result is well-known - or even true?
> There doesn't seem to be an obvious proof.
>
> Mike
>
>
>
>
> ------------------------------------
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
• If a Carmichael number n has a prime divisor p = 6k+1, then, since p-1 | n-1 (Korselt s criterion, cf. Wikipedia) we have that 6k | n-1, such that n = 1 (mod
Message 4 of 7 , May 27, 2010
If a Carmichael number n has a prime divisor p = 6k+1,
then, since p-1 | n-1 (Korselt's criterion, cf. Wikipedia)
we have that 6k | n-1, such that n = 1 (mod 3).

This means that a Carmichael number cannot be divisible by 3 if it has a prime factor p = 1 (mod 6).

Therefore, if 3 | n, then it cannot have a prime divisor = 1 mod 6.

Maximilian

>
>
>
> "mikeoakes2" <mikeoakes2@> wrote:
>
> > Conjecture: If n is a Carmichael number divisible by 3,
> > then all the other prime factors of n are congruent to 5 mod 6.
>
> There are 1967 Carmichael numbers less than 10^18 that
> are divisible by 3 and your conjecture holds for all of them.
>
> David
>
• ... Thanks for such a speedy verification. Now, based more on intuition than much experimental evidence, here is another Conjecture: If n is a Carmichael
Message 5 of 7 , May 27, 2010
>
> "mikeoakes2" <mikeoakes2@> wrote:
>
> > Conjecture: If n is a Carmichael number divisible by 3,
> > then all the other prime factors of n are congruent to 5 mod 6.
>
> There are 1967 Carmichael numbers less than 10^18 that
> are divisible by 3 and your conjecture holds for all of them.

Thanks for such a speedy verification.

Now, based more on intuition than much experimental evidence, here is another

Conjecture: If n is a Carmichael number divisible by 3, and p is any other prime factor, so that by definition (p-1) divides (n-1), then (p+1) never divides (n^2-1).

Mike
• ... Thanks, Maximilian! This means that Mike will not have to write to a civil servant at 2 Eldon Road, Cheltenham, Glos GL52 6TU, UK, asking whether this is
Message 6 of 7 , May 27, 2010
"maximilian_hasler" <maximilian.hasler@...> wrote:

> If a Carmichael number n has a prime divisor p = 6k+1,
> then, since p-1 | n-1 (Korselt's criterion, cf. Wikipedia)
> we have that 6k | n-1, such that n = 1 (mod 3).
> This means that a Carmichael number cannot be divisible by 3 if
> it has a prime factor p = 1 (mod 6).
> Therefore, if 3 | n, then it cannot have a prime divisor = 1 mod 6.

Thanks, Maximilian!

This means that Mike will not have to write to a "civil servant" at
2 Eldon Road, Cheltenham, Glos GL52 6TU, UK,
asking whether this is an "official secret" in the UK :-)

David
• ... Doh! (Is an immediate corollary of the first conjecture, proved so elegantly by Maximilian.) Mike
Message 7 of 7 , May 27, 2010
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
> Conjecture: If n is a Carmichael number divisible by 3, and p is any other prime factor, so that by definition (p-1) divides (n-1), then (p+1) never divides (n^2-1).

Doh!
(Is an immediate corollary of the first conjecture, proved so elegantly by Maximilian.)

Mike
Your message has been successfully submitted and would be delivered to recipients shortly.