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)

Printable View

- Aug 27th 2008, 09:52 PMCornflowermodular 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, 01:29 AMMoo
Hello,

Euler's theorem :

Let's multiply :

(1)

Since , we can factorise :

(2), where and hence is an**integer**.

Substituting (2) in (1) :

Rearranging :

Since the last bracket is an integer, we can say that

Therefore

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