# Math Help - modular arithmetic

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)

2. Hello,
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)}}$

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