# modular arithmetic

• Aug 27th 2008, 08:52 PM
Cornflower
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)
• Aug 28th 2008, 12:29 AM
Moo
Hello,
Quote:

Originally Posted by Cornflower
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)}}$

(Evilgrin) (I tried to explain as much as possible, so excuse me if it's too long...)