Results 1 to 5 of 5

Math Help - Eulers totient function

  1. #1
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170

    Eulers totient function

    Hi,

    I need to show that [Math]11^{40} + 33^{40} + 51^{40} + 97^{40}[/tex] is 4 in [Math]Z_{100}[/tex] using the totient function. The problem as i see it, is that 100 is not a prime number. i could of course go the long way [Math] (11^{2})^{20} = (21^{2})^{10} [/tex]and so forth but that's a bit tedious...

    /Jones
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Note, \phi (100) = 40 thus if \gcd(a,100) = 1 then a^{\phi(100)} = a^{40} \equiv 1 (\bmod 100).

    Then, \gcd(11,100) = \gcd(33,100) = \gcd(51,100) = \gcd(97,100) = 1.

    Thus, 11^{40}+33^{40}+51^{40} + 97^{40} \equiv 1+1+1+1 = 4(\bmod 100).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    2
    It doesnt have to be prime if you know the zeta function, the two numbers just have to have a gcd of 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by ThePerfectHacker View Post
    Note, \phi (100) = 40 thus if \gcd(a,100) = 1 then a^{\phi(100)} = a^{40} \equiv 1 (\bmod 100).

    Then, \gcd(11,100) = \gcd(33,100) = \gcd(51,100) = \gcd(97,100) = 1.

    Thus, 11^{40}+33^{40}+51^{40} + 97^{40} \equiv 1+1+1+1 = 4(\bmod 100).
    Thank you, how would this be different if we had for example [Math]25^{40} [/tex] when the gcd is not 1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    You would have to treat numbers like 2, 5, 25, 26, ... as special cases and work them out by hand.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 2nd 2011, 09:10 AM
  2. Eulers Totient
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 1st 2011, 08:56 AM
  3. Totient Function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 28th 2011, 07:28 PM
  4. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 09:33 AM
  5. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 22nd 2009, 02:21 AM

Search Tags


/mathhelpforum @mathhelpforum