Results 1 to 3 of 3

Math Help - carmichael numbers

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    123

    Post carmichael numbers

    question

    Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number. Find the smallest Carmichael number of this form.

    Thank you very much.
    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 Jenny20 View Post
    question

    Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number. Find the smallest Carmichael number of this form.

    Thank you very much.
    First I need to explain what a Carmichael number is.

    Any prime satisfiers this (Fermat's little theorem):
    a^{p}\equiv a (\mbox{mod } p)
    For any integer a.

    However, the converse fails.
    For example,
    2^{341}\equiv 2 (\mbox{mod }341).
    This is an example of a pseudoprime (to base two) for which the converse fails.

    A pseudoprime to all base is call a Carmichaeal number.
    ----
    Since p,2p-1,3p-2 are all primes we have.
    Let \gcd(a,p)=\gcd(a,2p-1)=\gcd(a,3p-2)=1.
    Then, Fermat's Elegant theorem (different version than above)
    a^{p-1} \equiv 1 (\mbox{mod }p)
    a^{2p-2}\equiv 1 (\mbox{mod }2p-1)
    a^{3p-3}\equiv 1 (\mbox{mod }3p-2)
    Thus,
    (a^{p-1})^{6p^2-(p-1)}\equiv 1(\mbox{mod }p)
    (a^{2p-2})^{3p^2-(p-1)/2}\equiv 1(\mbox{mod }2p-1)
    (a^{3p-3})^{2p^2-(p-1)/3}\equiv 1(\mbox{mod }3p-2)

    Important Note (p-1)/2 is an integer because primes are odd (usually) and we require for (p-1)/3 to be an integer we need that p\equiv 1(\mbox{mod }3).

    Now, because of relative primeness in the moduli we have,
    a^{6p^3-7p^2+2p-1}\equiv 1(\mbox{mod }p(2p-1)(3p-2)=6p^3-7p^2+2p)
    Thus,
    a^{6p^3-7p^2+2p}\equiv a(\mbox{mod }6p^3-7p^2+2p).

    Thus, if p\equiv 1(\mbox{mod }3).
    And, p,2p-1,3p-2 are primes.
    Then,
    p(2p-1)(3p-2) is a Carmichael number.
    ---
    I am supprised, where did you get this theorem from? First time I hear of it. It is really interesting.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Rewrite

    Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number.
    Substitute p=6k+1, so p(2p-1)(3p-2)=(6k+1)(12k+1)(18k+1). QED.

    Carmichael Number -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with carmichael numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 15th 2009, 08:28 PM
  2. two definitions of Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2009, 11:18 AM
  3. why is this argument about carmichael numbers true
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 11th 2009, 04:00 AM
  4. Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: April 21st 2009, 10:09 PM
  5. Carmichael Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2007, 06:09 AM

Search Tags


/mathhelpforum @mathhelpforum