Results 1 to 2 of 2

Math Help - modular arithmetic

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    1

    modular arithmetic

    Let x, y be relatively prime integers.
    Prove that x^(phi(y)) + y^(phi(x)) is congruent to 1 mod(xy)

    (phi is Euler's function)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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,
    Quote Originally Posted by Cornflower View Post
    Let x, y be relatively prime integers.
    Prove that x^(phi(y)) + y^(phi(x)) is congruent to 1 mod(xy)

    (phi is Euler's function)
    Euler's theorem :

    x^{\varphi(y)} \equiv 1 \bmod y \Leftrightarrow x^{\varphi(y)}-1=k \cdot y ~,~k \in \mathbb{Z}

    y^{\varphi(x)} \equiv 1 \bmod x \Leftrightarrow y^{\varphi(x)}-1=k' \cdot x ~,~k' \in \mathbb{Z}

    Let's multiply :
    kk' \cdot (xy)=(x^{\varphi(y)}-1) \cdot (y^{\varphi(x)}-1)=x^{\varphi(y)} \cdot y^{\varphi(x)}-\left(x^{\varphi(y)}+y^{\varphi(x)}\right)+1 (1)

    Since \varphi(x)~,~\varphi(y)~\ge 1, we can factorise :
    x^{\varphi(y)} \cdot y^{\varphi(x)}=(xy) \cdot (x^{\varphi(y)-1} \cdot y^{\varphi(x)-1}) (2), where \varphi(y)-1 \text{ and } \varphi(x)-1 \ge 0 and hence (x^{\varphi(y)-1} \cdot y^{\varphi(x)-1}) is an integer.


    Substituting (2) in (1) :
    kk' \cdot (xy)=(xy) \cdot (x^{\varphi(y)-1} \cdot y^{\varphi(x)-1})-\left(x^{\varphi(y)}+y^{\varphi(x)}\right)+1

    Rearranging :
    \left(x^{\varphi(y)}+y^{\varphi(x)}\right)=1+\bigg[(xy) \cdot (x^{\varphi(y)-1} \cdot y^{\varphi(x)-1})-kk' \cdot (xy)\bigg]

    \left(x^{\varphi(y)}+y^{\varphi(x)}\right)=1+(xy) \cdot \bigg[(x^{\varphi(y)-1} \cdot y^{\varphi(x)-1})-kk'\bigg]

    Since the last bracket is an integer, we can say that (xy) \cdot \bigg[(x^{\varphi(y)-1} \cdot y^{\varphi(x)-1})-kk'\bigg]\equiv 0 \bmod (xy)


    Therefore \boxed{\left(x^{\varphi(y)}+y^{\varphi(x)}\right) \equiv 1 \bmod{(xy)}}


    (I tried to explain as much as possible, so excuse me if it's too long...)
    Last edited by Moo; March 14th 2011 at 07:00 AM. Reason: latex has changed...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  2. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 08:44 AM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum