Results 1 to 2 of 2

Math Help - 2-pseudoprime!

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    65

    2-pseudoprime!

    A number m is called a 2-pseudoprime if

    (a) m is composite, and

    (b) 2^(m -1) == 1 mod m (where == is the congruent sign, the triple horizontal bars)

    (it's pseudo because it looks like Fermat's little theorem.

    I need to show that if n is a pseudoprime then m = [2^n] - 1 is also a 2-pseudoprime.

    I have shown that m is composite, now how do I go about showing the other condition? I tried playing around with the mod stuff, but I bring it down to something like this:

    if (2^n - 2) / n is an integer then show that ([2^2^n] - 4) / (2^n - 1) is also an integer. But I'm stuck proving this too. Any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Re: 2-pseudoprime!

    First note that m = 2^n - 1 implies that 2^n \equiv 1 (\bmod. m) , thus in fact 2^r \equiv 2^{ r \bmod n} (\bmod. m) for any r\in \mathbb{Z} (because adding - or substracting- n's to the exponent won't change the result)

    But now, by hypothesis 2^{n-1} \equiv 1 (\bmod. n) thus 2^n \equiv 2 (\bmod. n) ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving a Pseudoprime?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 30th 2010, 01:52 AM
  2. Strong pseudoprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 10th 2010, 10:24 AM
  3. Fermat Pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 31st 2009, 02:52 AM
  4. programming for pseudoprime problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 29th 2009, 03:03 AM
  5. Fermat pseudoprime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum