Thread: 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)

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 :





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


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