1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Carmichael numbers

  1. Mar 5, 2013 #1
    1. The problem statement, all variables and given/known data

    A Carmichael number is a composite integer n greater than or equal to 2 such that [itex] b^{n-1} \equiv 1 [/itex] (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 [itex](p-1)\mid (n-1)[/itex] for every prime divisor p of n, then n is a Carmichael number.

    2. Relevant equations

    3. The attempt at a solution

    My first question actually comes up on the proof itself, I have that by fermats little theorem [itex] b^{p_i-1}\equiv 1 (\textrm{mod} p_i)[/itex] for all the [itex]p_i[/itex] that divide n. but then I have that this means that [itex] b^{n-1}\equiv 1 (\textrm{mod} p_i) [/itex] 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?
  2. jcsd
  3. Mar 5, 2013 #2

    I like Serena

    User Avatar
    Homework Helper

    Hey Arcana! o:)

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

    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}##. :biggrin:)
    Last edited: Mar 5, 2013
  4. Mar 6, 2013 #3
    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?
  5. Mar 6, 2013 #4

    I like Serena

    User Avatar
    Homework Helper

    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. :wink:
  6. Mar 6, 2013 #5

    I like Serena

    User Avatar
    Homework Helper

    Since ##(p_i - 1)|(n-1)## it follows that there is some integer k such that ##k(p_i - 1)=(n-1)##.
    $$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?
  7. Mar 6, 2013 #6
    Thats okay, I know how to end the proof. It was that one step I didn't follow. Thanks for spelling it out :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted