Results 1 to 4 of 4

Math Help - Carmichael number

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Carmichael number

    Show that if  n = p_{1} \cdots p_{k} , where  p_{i} \neq p_{j} \; \forall \; i \neq j and for every  i, p_{i}-1 \mid n-1 , then  n is a Carmichael number.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by chiph588@ View Post
    Show that if  n = p_{1} \cdots p_{k} , where  p_{i} \neq p_{j} \; \forall \; i \neq j and for every  i, p_{i}-1 \mid n-1 , then  n is a Carmichael number.
    We will show that if a>0 and \gcd(a,n)=1 then a^{n-1}\equiv 1(\bmod n). Define the group G = \mathbb{Z}_n^{\times} \simeq \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times}. Now x\in \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times} then x^n is the identity because \mathbb{Z}_{p_i}^{\times} \simeq \mathbb{Z}_{p_i-1} and (p_i - 1)|(n-1). Therefore, if b\in G then we see that b^n is the identity. Thus, a^n \equiv 1(\bmod n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Is there a way to do it without fields?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by chiph588@ View Post
    Show that if  n = p_{1} \cdots p_{k} , where  p_{i} \neq p_{j} \; \forall \; i \neq j and for every  i, p_{i}-1 \mid n-1 , then  n is a Carmichael number.
    suppose \gcd(a,n)=1. then \gcd(a,p_i)=1, for all i. let n-1=k_i(p_i-1), \ i=1, \cdots , k. by Fermat's little theorem: a^{n-1}=(a^{p_i -1})^{k_i} \equiv 1 \mod p_i, for all i. thus \forall \ i: \ p_i \mid a^{n-1} - 1.

    so, since p_1, \cdots , p_k are distinct, we'll have n=p_1p_2 \cdots p_k \mid a^{n-1} - 1. \ \Box
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Carmichael Number Question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 7th 2010, 12:59 PM
  2. Question about Carmichael number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 8th 2009, 12:15 PM
  3. program to find carmichael number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 8th 2009, 08:45 AM
  4. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 06:52 PM
  5. Carmichael number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2008, 10:42 AM

Search Tags


/mathhelpforum @mathhelpforum