Carmichael Numbers: Prove Product of Primes is a Carmichael Number

[ArcanaNoir]

Homework Statement

A Carmichael number is a composite integer n greater than or equal to 2 such that b^{n-1} \equiv 1 (mod n) for all integers b that re relatively prime to n.

Let n be a Product of at least 3 distinct odd primes. Prove that if (p-1)\mid (n-1) for every prime divisor p of n, then n is a Carmichael number.

Homework Equations

The Attempt at a Solution

My first question actually comes up on the proof itself, I have that by fermats little theorem b^{p_i-1}\equiv 1 (\textrm{mod} p_i) for all the p_i that divide n. but then I have that this means that b^{n-1}\equiv 1 (\textrm{mod} p_i) and I don't know why that's true.

My second question is for ILS if he sees this post, can I apply Eulers theorem to do this proof instead?

 

[I like Serena]

Homework Statement

A Carmichael number is a composite integer n greater than or equal to 2 such that b^{n-1} \equiv 1 (mod n) for all integers b that re relatively prime to n.

Let n be a Product of at least 3 distinct odd primes. Prove that if (p-1)\mid (n-1) for every prime divisor p of n, then n is a Carmichael number.

Homework Equations

The Attempt at a Solution

My first question actually comes up on the proof itself, I have that by fermats little theorem b^{p_i-1}\equiv 1 (\textrm{mod} p_i) for all the p_i that divide n. but then I have that this means that b^{n-1}\equiv 1 (\textrm{mod} p_i) and I don't know why that's true.

My second question is for ILS if he sees this post, can I apply Eulers theorem to do this proof instead?

Hey Arcana!


I don't see how Euler's theorem can be used, but I certainly see how the Chinese Remainder Theorem can be used.

Suppose $\displaystyle n=\prod_{i=1}^m p_i$ with $p_i$ distinct primes.
Then according to CRT, we have that $\psi$ given by:
$$\psi: (\mathbb Z/n \mathbb Z)^* \to (\mathbb Z/p_1 \mathbb Z)^* \times (\mathbb Z/p_2 \mathbb Z)^* \times ... \times (\mathbb Z/p_m \mathbb Z)^*$$
$$\psi: (x \text{ mod } n) \mapsto (x \text{ mod } p_1, ~x \text{ mod } p_2, ~ ... ,~x \text{ mod } p_m)$$
is an isomorphism.

Now what if we fill in $x=b^{n-1}$?



(In other words: $\text{Fermat} \prec \text{Euler} \prec \text{CRT}$. )

 

[ArcanaNoir]

How do you know everything ILS? I have not yet asked a question which you did not seem to be an expert on. Surely even if you did learn everything the knowledge must leak out of your brain after a while; you can't possible always remember everything you've learned... How do you do it?

 

[I like Serena]

How do you know everything ILS? I have not yet asked a question which you did not seem to be an expert on. Surely even if you did learn everything the knowledge must leak out of your brain after a while; you can't possible always remember everything you've learned... How do you do it?

I keep thinking what an amazing coincidence it is that you seem to be interested in exactly the topics that I know a little about.

 

[I like Serena]

My first question actually comes up on the proof itself, I have that by fermats little theorem b^{p_i-1}\equiv 1 (\textrm{mod} p_i) for all the p_i that divide n. but then I have that this means that b^{n-1}\equiv 1 (\textrm{mod} p_i) and I don't know why that's true.

Since $(p_i - 1)|(n-1)$ it follows that there is some integer k such that $k(p_i - 1)=(n-1)$.
So
$$b^{n-1} \equiv b^{k(p_i - 1)}\equiv (b^{p_i - 1})^k \equiv 1^k \equiv 1 \pmod{p_i}$$

The next step would be that:
$$b^{n-1} = 1 + k_1 p_1$$
$$b^{n-1} = 1 + k_2 p_2$$
$$...$$
$$b^{n-1} = 1 + k_m p_m$$

Now what can you conclude from that?

 

[ArcanaNoir]

Thats okay, I know how to end the proof. It was that one step I didn't follow. Thanks for spelling it out :)