# Prime Power Congruence

• Apr 24th 2009, 02: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, 03: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, $a$ divides $b^{a-1}-1;$ therefore $a$ divides $a^{b-1}+b^{a-1}-1.$

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

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

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

Thanks
• Apr 24th 2009, 09: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 $x|z,y|z$ then $\text{lcm}(x,y) |z$, for $x,y,z\in \mathbb{Z}^+$.
---

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