English Deutsch Français Italiano Español Português 繁體中文 Bahasa Indonesia Tiếng Việt ภาษาไทย
All categories

The problem is:
Prove that there do not exist any Carmichael numbers with two prime factors.

This is what I have so far:

Suppose there exists a Carmichael number n = p1p2 (where p1 and p2 are odd primes not equal to each other).

Then p1 - 1 divides n - 1.
Also, p2 - 1 divides n - 1.

I'm not sure where to go from here

2007-11-15 02:25:33 · 2 answers · asked by 3545 2 in Science & Mathematics Mathematics

2 answers

Have you got, first of all, that n is square free?
So suppose n = p1p2, where p1, p2 are primes
and p1 < p2.
As you wrote, p2-1 divides n-1.
But we can also write
n-1 = p1(p2-1+1) -1 = (p1-1) mod (p2-1 ),
But if you write this congruence out, you will see that
p2-1 divides n yields p2-1 divides p1-1, which is impossible because p1 < p2.

2007-11-15 04:24:39 · answer #1 · answered by steiner1745 7 · 0 0

I tried this
Consider two primes (2p+1)(2q+1) = n where p does not equal q
Then 4pq + 2p + 2q + 1 = n
Then 4pq +2p + 2q) = n-1
This can be factorised as 2p(2q+1 + q/p) where 2q +1 + q/p must be an integer and also as 2q(2p + 1+ p/q) where 2p + 1 + p/q must be an integer.

Therefore p/q must be an integer and q/p must be an integer. This only happens if p=q which contradicts original statement.

2007-11-15 02:50:39 · answer #2 · answered by welcome news 6 · 0 0

fedest.com, questions and answers