# Thread: Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

1. ## Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

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

2. Hello rickykkk2000,

You want to show that with $\displaystyle 2 \leq a \leq b$, $\displaystyle GCD(a, b) = 1$, then the following equality holds :

$\displaystyle a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{ab}$

Let us break this problem. Since $\displaystyle a$ and $\displaystyle b$ are relatively prime, the following must hold :

$\displaystyle a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{a}$

$\displaystyle a^{\varphi{(b)}} + b^{\varphi{(a)}} \equiv 1 \pmod{b}$

Remember that Fermat Little Theorem and Euler generalization I came up with in your previous topic ? This problem strikingly calls for it. Remember that for any $\displaystyle a$ with $\displaystyle GCD(a, p) = 1$ and $\displaystyle p$, we have $\displaystyle a^{\varphi{(p)}} \equiv 1 \pmod{p}$.

Thus, the following must hold (because $\displaystyle a$ and $\displaystyle b$ are relatively prime) :

$\displaystyle a^{\varphi{(b)}} \equiv 1 \pmod{b}$

$\displaystyle b^{\varphi{(a)}} \equiv 1 \pmod{a}$

Can you see how to finish the question by using (*) now ?

3. Hello,

See here and here

4. ## thanks again!

Thanks again Ray! and Moo, too =D
Now it becomes clear to me.

5. Hi

I understand the reasoning behind most of this proof, but could anyone please explain why:
a^phi(b) + b^phi(a) is congruent to 1 mod a and a^phi(b) + b^phi(a) is congruent to 1 mod b?

I don't understand why it holds given that a and b are relatively prime.

(I don't know if Moo's posts would have helped with this but I can no longer access them)

Thank you

6. Hi,

I changed the links, they're now ok (that's due to some modifications on the forum).

As for why $\displaystyle a^{\varphi(b)} + b^{\varphi(a)} \equiv 1 \bmod a$, this is because $\displaystyle a^{\varphi(b)}\equiv 0 \bmod a$ (because it's a multiple of a), and since a and b are relatively prime, Euler's theorem states that $\displaystyle b^{\varphi(a)}\equiv 1 \bmod a$

7. That makes complete sense now thank you!