Results 1 to 7 of 7

Math Help - Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    5

    Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

    Let a and b be natural numbers greater than or equal to 2. Suppose that a and b are relatively prime. Prove that:

    [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab),

    where,
    phi(a) is the number of elements in the set {1,...,a-1} that are relatively prime to a.
    phi(b) is the number of elements in the set {1,...,b-1} that are relatively prime to b.
    --------------------------------------------------------------------------

    I spent a long time thinking but this question but still couldn't come up with something useful. However, I was told that it would be useful to use the following relation:

    Let a, b, m, n be natural numbers. Assume a and b are relatively prime.
    then if :
    m is congruent to n(mod a)
    m is congruent to n(mod b), then we have that
    m is congruent to n(mod ab)---------->(*)

    I have proved this relation (*) using the fact that there exists integers s and t s.t. sa + tb = 1. to show that in the end we will get
    m is congruent to n (mod ab).

    However, I am not quite sure how I should apply this concept to the question above to show that

    [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab),


    Any help is appreciated.
    Thanks =D
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello rickykkk2000,

    You want to show that with 2 \leq a \leq b, GCD(a, b) = 1, then the following equality holds :

    a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{ab}

    Let us break this problem. Since a and b are relatively prime, the following must hold :

    a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{a}

    a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{b}

    Remember that Fermat Little Theorem and Euler generalization I came up with in your previous topic ? This problem strikingly calls for it. Remember that for any a with GCD(a, p) = 1 and p, we have a^{\varphi{(p)}} \equiv 1 \pmod{p}.

    Thus, the following must hold (because a and b are relatively prime) :

    a^{\varphi{(b)}} \equiv 1 \pmod{b}

    b^{\varphi{(a)}} \equiv 1 \pmod{a}

    Can you see how to finish the question by using (*) now ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    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
    Hello,

    See here and here
    Last edited by Moo; March 14th 2011 at 06:59 AM. Reason: links were down
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2010
    Posts
    5

    thanks again!

    Thanks again Ray! and Moo, too =D
    Now it becomes clear to me.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2011
    Posts
    2
    Hi

    I understand the reasoning behind most of this proof, but could anyone please explain why:
    a^phi(b) + b^phi(a) is congruent to 1 mod a and a^phi(b) + b^phi(a) is congruent to 1 mod b?

    I don't understand why it holds given that a and b are relatively prime.

    (I don't know if Moo's posts would have helped with this but I can no longer access them)

    Thank you
    Follow Math Help Forum on Facebook and Google+

  6. #6
    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
    Hi,

    I changed the links, they're now ok (that's due to some modifications on the forum).

    As for why a^{\varphi(b)} + b^{\varphi(a)} \equiv  1 \bmod a, this is because a^{\varphi(b)}\equiv 0 \bmod a (because it's a multiple of a), and since a and b are relatively prime, Euler's theorem states that b^{\varphi(a)}\equiv 1 \bmod a
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2011
    Posts
    2
    That makes complete sense now thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 5th 2009, 11:11 PM
  2. Replies: 2
    Last Post: October 5th 2009, 03:02 PM
  3. prove a congruent angle with a bisector
    Posted in the Geometry Forum
    Replies: 2
    Last Post: June 18th 2007, 02:12 PM
  4. Replies: 4
    Last Post: November 12th 2006, 05:09 PM
  5. Replies: 4
    Last Post: November 12th 2006, 05:00 PM

Search Tags


/mathhelpforum @mathhelpforum