# Two problem number-theory

$p$ and $q$ are prime, $p \neq q , a$ is integer:

1)$p^{q-1}+q^{p-1} \equiv 1 \pmod{pq}$

2)$p|(a^p + (p-1)!a)$

-
It would be better to separate these into two questions. At least to me, they seem quite distinct. –  Ross Millikan Nov 30 '12 at 19:15

(1)Using Fermat's Little Theorem, $p\mid (q^{p-1}-1)$ as $(p,q)=1$

$\implies p\mid (p^{q-1}+q^{p-1}-1)$

Similarly, $q\mid (p^{q-1}+q^{p-1}-1)\implies$ lcm$(p,q)\mid (p^{q-1}+q^{p-1}-1)$

and the lcm$(p,q)=pq$ as $(p,q)=1$

(2) By Wilson's Theorem, $(p-1)!\equiv-1\pmod p$

So, $a^p+(p-a)!a\equiv a^p-a\pmod p$, but $a^p\equiv a\pmod p$ for all integer $a$ using Fermat's Little Theorem

-
complete and useful for me. –  geni Nov 30 '12 at 19:37
@ing, thanks.Nice to hear this. –  lab bhattacharjee Nov 30 '12 at 19:44

Hints

1) Work separately modulo $p$ and $q$, using Fermat's Theorem in each case.

2) Use Fermat's Theorem to conclude that $a^p\equiv a\pmod{p}$, then use Wilson's Theorem.

-

Hint  By Fermat $\rm\: p\,\color{#C00}q\mid p^{q-1} \color{#C00}{q^{p-1}}\!-(\color{#C00}{p^{q-1}\!-1})({q^{p-1}\!-1})\, =\, p^{q-1}\!+q^{p-1}\!-1$

and, secondly, $\rm\,\ p\mid \color{#C00}{a^p-a} + a(\color{#0A0}{1\!+(p\!-\!1)!})\ \,$ by $\,\rm\color{#C00}{Fermat},\, \color{#0A0}{Wilson},\,$ resp.

-