# Thread: why is this argument about carmichael numbers true

1. ## 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$

2. 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.

3. 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

.

4. ## no clear

ThePerfectHacker's answer is not clear.

i cant get why we only need to test primes a from 2 to 19 to find all Carmichael < 10^6