# why is this argument about carmichael numbers true

• Sep 9th 2009, 12:39 PM
silversand
why is this argument about carmichael numbers true
to find all the carmichael numbers N $\displaystyle < 10^{6}$ , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

$\displaystyle (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N$
• Sep 9th 2009, 07:38 PM
ThePerfectHacker
Quote:

Originally Posted by silversand
to find all the carmichael numbers N $\displaystyle < 10^{6}$ , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

$\displaystyle (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N$

If prime numbers $\displaystyle a$ satisfy $\displaystyle a^{N-1}\equiv 1(\bmod N)$ then any number $\displaystyle (n,N)=1$ would have to satisfy $\displaystyle n^{N-1}\equiv 1(\bmod N)$. This is because if $\displaystyle a,b$ satisfy this congruence then $\displaystyle (ab)^{N-1}\equiv a^{N-1}b^{N-1}\equiv 1(\bmod N)$. Therefore, there products of all these primes would satisfy the congruence. But since $\displaystyle n$ can be realized as a product of primes it would mean that it itself satisfies the congruence.
• Sep 10th 2009, 04:51 AM
aidan
Quote:

Originally Posted by silversand
to find all the carmichael numbers N $\displaystyle < 10^{6}$ , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

$\displaystyle (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N$

You will also find primes as pointed out by ThePerfectHacker, but
how will you distinguish these Carmichael Numbers from primes:
A few Carmichael Numbers < $\displaystyle 10^6$ with smallest factor > 19
252601 = 41 * 61 * 101
294409 = 37 * 73 * 109
399001 = 31 * 61 * 211
410041 = 41 * 73 * 137
488881 = 37 * 73 * 181
512461 = 31 * 61 * 271

.
• Sep 11th 2009, 03:00 AM
silversand
no clear