Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By johng

Math Help - pseudo-prime

  1. #1
    Junior Member
    Joined
    Dec 2012
    From
    Britain
    Posts
    46
    Thanks
    2

    pseudo-prime

    Show that a^{560}=1 mod(561) for all a co-prime to 561. Hint: 561=3 x 17 x 11.

    I thought about trying to show a^{560}=1 (mod 3,17,11), but do not see how this is possible.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2012
    From
    Morocco
    Posts
    26
    Thanks
    1

    Re: pseudo-prime

    561 is a Poulet number and is considered a pseudoprime . So you can apply fermat's little theorem on it.
    Last edited by SMAD; May 14th 2013 at 11:28 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    616
    Thanks
    249

    Re: pseudo-prime

    Hi,
    You need just a few elementary facts:
    1. If a is co-prime (relatively prime in U.S.) to n and p is any divisor of n, a is relatively prime to p.
    2. If a is relatively prime to a prime p, a^{p-1}\equiv1 (\text{mod}\, p)
    3. If p, q and r are primes that divide n, then the product pqr divides n.

    So (a^2)^{280}\equiv1^{280}(\text{mod}\, 3)\equiv1 (\text{mod}\, 3) by 1 and 2.
    (a^{10})^{56}\equiv1^{56}(\text{mod}\, 11)\equiv1 (\text{mod}\, 11)
    (a^{16})^{35}\equiv1^{35}(\text{mod}\, 17)\equiv1 (\text{mod}\, 17)

    Thus 3, 11 and 17 divide a^{560}-1 and by 3, the product 3*11*17 = 561 divides a^{560}-1
    Thanks from Plato13
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2012
    From
    Britain
    Posts
    46
    Thanks
    2

    Re: pseudo-prime

    Thank you; very clear solution
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pseudo inverse of a matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 21st 2011, 09:01 PM
  2. pseudo-sine function?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 25th 2010, 04:58 PM
  3. pseudo-sine function
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 19th 2010, 07:12 AM
  4. help with pseudo code problem please
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 12th 2008, 09:55 AM
  5. Pseudo-Geometric Series
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: October 5th 2008, 03:53 AM

Search Tags


/mathhelpforum @mathhelpforum