# Thread: Primes and divisibility

1. ## Primes and divisibility

Let $p$ and $q$ be different primes. Prove that $pg | p^{q-1} + q^{p-1} - 1$.

2. Try using Fermat's Little Theorem, which says that $a^{p-1} \equiv 1 \ (mod \ p)$ for some prime $p$ and integer $a$ with $(a,p)=1$

Also, $a \equiv b \ (mod \ c) \Leftrightarrow c \ | \ a-b$

Also, $a|a^x$ with $x \geq 1$

Last thing you'll need is that if $p|a$ and $q|a$ then $pq|a$

Hope that helps ... if you still can't see how I did it, just ask for more details

3. Originally Posted by Bingk
Try using Fermat's Little Theorem, which says that $a^{p-1} \equiv 1 \ (mod \ p)$ for some prime $p$ and integer $a$ with $(a,p)=1$

Also, $a \equiv b \ (mod \ c) \Leftrightarrow c \ | \ a-b$

Also, $a|a^x$ with $x \geq 1$

Last thing you'll need is that if $p|a$ and $q|a$ then $pq|a$

Hope that helps ... if you still can't see how I did it, just ask for more details
Thx, that was easy ...

4. Originally Posted by strelc
Let $p$ and $q$ be different primes. Prove that $pg | p^{q-1} + q^{p-1} - 1$.

Generalize this. Let $n,m$ be positive integers with $(n,m)=1$ prove that $nm | n^{\phi(m)}+m^{\phi(n)} - 1$.