Question

Show that if Pand qare distinct prime numbers, then

${\mathit{p}}^{\mathbf{q}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathit{q}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathit{q}\mathbf{)}$

Short answer

It is proved that if pand qare distinct prime numbers, then

$p^{q-1}+q^{p-1}\equiv 1(modpq)$

Step-by-step solution

Important Theorems and Definitions

• Chinese remainder theorem:

A system of linear congruences modulo pairwise relatively prime integers have a unique solution modulo is the product of these moduli.

Let${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{\dots }{\mathit{m}}_{\mathbf{n}}$be pairwise relatively prime positive integers greater than one and${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{\dots }\mathbf{.}{\mathit{a}}_{\mathbf{n}}$arbitrary integers. Then the system

role="math" localid="1668664216894" $\begin{array}{r}\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{1}}\left(mod{m}_1\right)\\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{2}}\left(mod{m}_2\right)\\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{n}}\left(mod{m}_n\right)\end{array}$

has a unique solution modulo$\mathit{m}\mathbf{=}{\mathit{m}}_{\mathbf{1}}{\mathit{m}}_{\mathbf{2}}\mathbf{\dots }{\mathit{m}}_{\mathbf{n}}$. (That is, there is a solution xwith$\mathbf{0}\mathbf{\le }\mathit{x}\mathbf{<}\mathit{m}$, and all other solutions are congruent moduloto this solution.)

• Fermat’s little theorem: If pis prime and p t a, then${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$.

• a = b ( mos m) (ais congruent to bmodulo m): a - bis divisible by.

Proving that

Given in the question

p and q are distinct prime,

Therefore, they are not divisible by each other

Since p is not divisible by q we can apply Fermat’s little theorem

$p^{q-1}\equiv 1(modq)$

Since$q^{p-1}$ is divisible by

$q^{p-1}\equiv 0(modq)$

Therefore,

$\begin{array}{r}{p}^{q-1}+q^{p-1}\equiv 1(modq)+0(modq)\\ p^{q-1}+q^{p-1}\equiv 1(modq)\end{array}$

Similarly,

Since q is not divisible by p we can apply Fermat’s little theorem

$q^{p-1}\equiv 1(modp)$

Since is divisible by

$p^{q-1}\equiv 0(modp)$

Therefore,

$\begin{array}{r}{p}^{q-1}+q^{p-1}\equiv 1(modp)+0(modp)\\ p^{q-1}+q^{p-1}\equiv 1(modp)\end{array}$

Since $p^{q-1}+q^{p-1}\equiv 1(modq)\text{and}{p}^{q-1}+q^{p-1}\equiv 1(modp)$, therefore from Chinese remainder theorem $p^{q-1}+q^{p-1}\equiv 1(modpq)$

Hence it is proved that if pand qare distinct prime numbers, then

$p^{q-1}+q^{p-1}\equiv 1(modpq)$