Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By Petek

Math Help - Show that 16^560 = 1 (mod 561) even though 561 is not a prime

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Show that 16^560 = 1 (mod 561) even though 561 is not a prime

    a) Show that 16^{560} \equiv 1 \pmod{561} even though 561 is not prime. (This shows that the converse of Fermat's Theorem is false.)
    b) (Harder) Show that a^{561} \equiv a \pmod{561} for all integers a.


    a) \phi(561) = 320 and gcd(16, 561) = 1, then according to Euler's Theorem 16^{560} = 16^{320} 16^{240} = 16^{240} \pmod{561}. I do not know what to do next.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

    In case : \gcd(a,561)=1 it is sufficient to show that 561 is a Carmichael number using Korselt's criterion
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

    Thanks. But my class hasn't covered Carmichael number. There must be another way to solve this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2010
    Posts
    56
    Thanks
    16

    Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

    For part (a), you need to show that 16^{240} \equiv 1 \pmod {561} to complete the proof. Hint: Show that

    16^{240} \equiv 1 \pmod{3}
    16^{240} \equiv 1 \pmod{11}
    16^{240} \equiv 1 \pmod{17}

    and then argue why this implies the needed congruence. For part (b), try to apply the above hint, modified as necessary.
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

    Thank you.

    If gcd(a,b) = 1 and a | n and b | n, then ab | m.

    We have ax + by = 1 for some integers x,y due to Bezout's identity. Multiply both sides by n we get axm + bym = m. The LHS can be divided by ab.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Show that n^5 + n^4 + 1 is not prime for n>1
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: July 24th 2013, 08:18 PM
  2. Show co-prime...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 25th 2011, 12:38 PM
  3. Show that 2k+1 cannot be a prime unless...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 2nd 2010, 08:04 PM
  4. Replies: 1
    Last Post: December 14th 2009, 05:13 PM
  5. If n>1 , show that n^4 + 4^n is never a prime?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 6th 2008, 09:41 AM

Search Tags


/mathhelpforum @mathhelpforum