# why is this argument about carmichael numbers true

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

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

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

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

If prime numbers $a$ satisfy $a^{N-1}\equiv 1(\bmod N)$ then any number $(n,N)=1$ would have to satisfy $n^{N-1}\equiv 1(\bmod N)$. This is because if $a,b$ satisfy this congruence then $(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 $n$ can be realized as a product of primes it would mean that it itself satisfies the congruence.
• September 10th 2009, 04:51 AM
aidan
Quote:

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

$(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 < $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

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