# Prime Power Congruence

• Apr 24th 2009, 01:26 PM
Fulger85
Prime Power Congruence
Question:

Let a,b be distinct prime numbers.

Show that (a^(b-1) + b^(a-1) - 1) / (a*b) is an integer.

Should be easy but Im just completly blanked out...

Thank you
• Apr 24th 2009, 02:14 PM
TheAbstractionist
Quote:

Originally Posted by Fulger85
Question:

Let a,b be distinct prime numbers.

Show that (a^(b-1) + b^(a-1) - 1) / (a*b) is an integer.

Should be easy but Im just completly blanked out...

Thank you

Hi Fulger85.

By Fermat’s little theorem, $\displaystyle a$ divides $\displaystyle b^{a-1}-1;$ therefore $\displaystyle a$ divides $\displaystyle a^{b-1}+b^{a-1}-1.$

Similarly $\displaystyle b$ divides $\displaystyle a^{b-1}-1$ and so $\displaystyle b$ divides $\displaystyle b^{a-1}+a^{b-1}-1.$

Hence $\displaystyle \mathrm{lcm}(a,b)=ab$ divides $\displaystyle a^{b-1}+b^{a-1}-1.$
• Apr 24th 2009, 03:06 PM
Fulger85
Understood.

Thank you
• Apr 24th 2009, 03:43 PM
Fulger85
Actually, do you mind elaborating on why lcm(a,b) divides it?

Thanks
• Apr 24th 2009, 08:44 PM
ThePerfectHacker
Quote:

Originally Posted by Fulger85
Actually, do you mind elaborating on why lcm(a,b) divides it?

Thanks

Property of lcm. If $\displaystyle x|z,y|z$ then $\displaystyle \text{lcm}(x,y) |z$, for $\displaystyle x,y,z\in \mathbb{Z}^+$.
---

Your problem can be generalized to $\displaystyle a^{\phi(b)} + b^{\phi(a)} \equiv 1(\bmod ab)$ for relatively prime positive integers $\displaystyle a,b$.