Results 1 to 4 of 4

Thread: Carmichael number

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

    Carmichael number

    Show that if $\displaystyle n = p_{1} \cdots p_{k} $, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j $ and for every $\displaystyle i, p_{i}-1 \mid n-1 $, then $\displaystyle 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
    10
    Quote Originally Posted by chiph588@ View Post
    Show that if $\displaystyle n = p_{1} \cdots p_{k} $, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j $ and for every $\displaystyle i, p_{i}-1 \mid n-1 $, then $\displaystyle n $ is a Carmichael number.
    We will show that if $\displaystyle a>0$ and $\displaystyle \gcd(a,n)=1$ then $\displaystyle a^{n-1}\equiv 1(\bmod n)$. Define the group $\displaystyle G = \mathbb{Z}_n^{\times} \simeq \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times}$. Now $\displaystyle x\in \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times}$ then $\displaystyle x^n$ is the identity because $\displaystyle \mathbb{Z}_{p_i}^{\times} \simeq \mathbb{Z}_{p_i-1}$ and $\displaystyle (p_i - 1)|(n-1)$. Therefore, if $\displaystyle b\in G$ then we see that $\displaystyle b^n$ is the identity. Thus, $\displaystyle 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 $\displaystyle n = p_{1} \cdots p_{k} $, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j $ and for every $\displaystyle i, p_{i}-1 \mid n-1 $, then $\displaystyle n $ is a Carmichael number.
    suppose $\displaystyle \gcd(a,n)=1.$ then $\displaystyle \gcd(a,p_i)=1,$ for all $\displaystyle i.$ let $\displaystyle n-1=k_i(p_i-1), \ i=1, \cdots , k.$ by Fermat's little theorem: $\displaystyle a^{n-1}=(a^{p_i -1})^{k_i} \equiv 1 \mod p_i,$ for all $\displaystyle i.$ thus $\displaystyle \forall \ i: \ p_i \mid a^{n-1} - 1.$

    so, since $\displaystyle p_1, \cdots , p_k$ are distinct, we'll have $\displaystyle 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: Oct 7th 2010, 12:59 PM
  2. Question about Carmichael number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 8th 2009, 12:15 PM
  3. program to find carmichael number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 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: Oct 17th 2008, 10:42 AM

Search Tags


/mathhelpforum @mathhelpforum