Results 1 to 3 of 3

Math Help - Mods

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Mods

    1.) By using mods: for any pos. integer n, show n^5 has the same last digit as n.

    2.) Again, using mods, show if gcd(n,100) = 1, then n^41 has the same last 2 digits as n. Explain if it is true for ALL n, that n and n^41 have the same last 2 digits.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    1.) By using mods: for any pos. integer n, show n^5 has the same last digit as n.

    .
    When you are working with the last digits you work mod 10.

    When, let n be any arbitary integer.
    Thus, (by division algorithm),
    N=0,1,2,3,4,5,6,7,8,9 (mod 10).

    Meaning, N has to be congruent to exaclty one of those numbers, i.e. that are the possible endings for the integer.

    Then, by inspection, we see that, by mod 10,
    0^5 = 0
    1^5 = 1
    2^5 = 2
    3^5 = 3
    4^5 = 4
    5^5 = 5
    6^6 = 6
    7^5 = 7
    8^5 = 8
    9^5 = 9

    Hence, n^5 is congruent to the same number under mod 10.

    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post

    2.) Again, using mods, show if gcd(n,100) = 1, then n^41 has the same last 2 digits as n. Explain if it is true for ALL n, that n and n^41 have the same last 2 digits.
    By Euler Elegant Generalization of the Super Little Theorem of the Cool Fermat, we have that,

    a^{phi(n)} = 1 (mod n)

    In this case let n=100.
    Thus, phi(100)=40.
    Thus,
    a^{40} = 1 (mod 100)
    Where gcd(a,n)=100.
    Then, multiplication by "a" yield,
    a^{41} = a (mod 100}
    Thus they have the same last two digits for they are congruent to each other.

    ----
    Consider n=2. The last two digits are 02 (if that is how you want to think of it).

    Then, n^41=2199023255552
    Where the last two digits are 52.
    It fails.

    Note gcd(2,100) not = 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mods Help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 27th 2010, 12:38 AM
  2. Mods help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 21st 2010, 08:22 AM
  3. Mods and BN
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 17th 2010, 12:58 PM
  4. mods
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 23rd 2010, 04:08 AM
  5. mods
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 2nd 2009, 04:42 AM

Search Tags


/mathhelpforum @mathhelpforum