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

Printable View

- Apr 24th 2009, 01:26 PMFulger85Prime 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 PMTheAbstractionist
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 PMFulger85
Understood.

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

Thanks - Apr 24th 2009, 08:44 PMThePerfectHacker
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$.