# Fermat, Congruences, the CRT, and an exam question

• Jul 12th 2011, 06:47 AM
jsndacruz
Fermat, Congruences, the CRT, and an exam question
Had the following problem on an exam, and couldn't crack it:

Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either (Rofl)
• Jul 12th 2011, 07:30 AM
Also sprach Zarathustra
Re: Fermat, Congruences, the CRT, and an exam question
Quote:

Originally Posted by jsndacruz
Had the following problem on an exam, and couldn't crack it:

Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either (Rofl)

From Fermat's theorem we get:

$\displaystyle p|q^{p-1}-1$ and $\displaystyle q|p^{q-1}-1$

Hence, $\displaystyle pq|(q^{p-1}-1)(p^{q-1}-1)$.

So...

$\displaystyle 0\equiv(q^{p-1}-1)(p^{q-1}-1)=...$

Try to continue.
• Jul 13th 2011, 04:23 AM
chisigma
Re: Fermat, Congruences, the CRT, and an exam question
Quote:

Originally Posted by jsndacruz
Had the following problem on an exam, and couldn't crack it:

Show that if p and q are primes, then p^(q-1) + q^(p-1) == 1 (mod pq)

We know through Fermat each p^(q-1) == 1 (mod q) and q^(p-1) == 1(mod p). However I'm not sure how to combine the two.

I thought the CRT might help if we changed the system to p^(q) == p(mod q) and q^(p) == q (mod p).

If you think the problem easy, feel free to leave a hint rather than a solution so I have to work a bit -- I'd appreciate either (Rofl)

For the 'Fermat little theorem', if p and q are primes then...

$\displaystyle q|(p^{q-1}-1)$

$\displaystyle p|(q^{p-1}-1)$ (1)

Now is...

$\displaystyle (p^{q-1}-1)\ (q^{p-1}-1) = p^{q-1}\ q^{p-1} - p^{q-1}- q^{p-1}+1$ (2)

... and from (1) and (2) You easily derive that...

$\displaystyle p\ q| (p^{q-1}+ q^{p-1}-1)$ (3)

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Jul 24th 2011, 07:49 PM
jsndacruz
Re: Fermat, Congruences, the CRT, and an exam question
Thanks so much, also sprach Zarathustra (didn't know that was the song's name until my latest google of your name) and ChiSigma. Sorry for not thanking earlier!
• Jul 24th 2011, 08:17 PM
Also sprach Zarathustra
Re: Fermat, Congruences, the CRT, and an exam question
Quote:

Originally Posted by jsndacruz
Thanks so much, also sprach Zarathustra (didn't know that was the song's name until my latest google of your name) and ChiSigma. Sorry for not thanking earlier!

Now you just left to read Nietzsche...