Results 1 to 5 of 5

Math Help - eulers theorem problem

  1. #1
    Junior Member
    Joined
    Jun 2009
    Posts
    25

    eulers theorem problem

    show that a^phi(b) + b^phi(a) is congruent to 1 (mod ab), if a and b are relatively prime positive integers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Hint

    Use Euler's theorem to show :

    a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod a
    a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod b

    and conclude that a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod ab.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2009
    Posts
    25
    how can I prove that a^phi(b) + b^phi(a) is congruent to 1 (mod a (or b))?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Euler's theorem: (a,b) = 1 \ \Rightarrow \ a^{\phi (b)} \equiv 1 \ (\text{mod } b)

    Clearly: b \mid b^{\phi (a)} \ \Leftrightarrow \ b^{\phi (a)} \equiv 0 \ (\text{mod } b)

    So: a^{\phi (b)} + b^{\phi (a)} \equiv 1 + 0 \equiv 1 \ (\text{mod } b)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Eulers Theorem problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2009, 04:20 PM
  2. Definition of Eulers Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 7th 2009, 09:05 PM
  3. Proof using Eulers Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2009, 11:10 AM
  4. eulers
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 8th 2009, 12:46 AM
  5. Eulers theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2006, 11:50 PM

Search Tags


/mathhelpforum @mathhelpforum