Let a and b be natural numbers greater than or equal to 2. Suppose that a and b are relatively prime. Prove that:

[ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab),

where,

phi(a) is the number of elements in the set {1,...,a-1} that are relatively prime to a.

phi(b) is the number of elements in the set {1,...,b-1} that are relatively prime to b.

--------------------------------------------------------------------------

I spent a long time thinking but this question but still couldn't come up with something useful. However, I was told that it would be useful to use the following relation:

Let a, b, m, n be natural numbers. Assume a and b are relatively prime.

then if :

m is congruent to n(mod a)

m is congruent to n(mod b), then we have that

m is congruent to n(mod ab)---------->(*)

I have proved this relation (*) using the fact that there exists integers s and t s.t. sa + tb = 1. to show that in the end we will get

m is congruent to n (mod ab).

However, I am not quite sure how I should apply this concept to the question above to show that

[ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab),

Any help is appreciated.

Thanks =D