Answer to Question #96788 in Combinatorics | Number Theory for Dina Patel

Question

Let p and q be distinct prime numbers. Prove that p
q−1 + q
p−1 ≡ 1 mod pq.

Answer 1

Proof Of a problem of distinct prime numbers

We need to prove $p^{q -1} + q^ {p-1} \equiv$ 1 $mod \space {(pq)}$

Solution:

Since p and q are different prime numbers, their greatest common divisor = 1

means (p, q) = 1

Here, we can Apply Fermat's little theorem, then

$p^{q -1} \equiv 1$$\space mod \space {(q)}$ and $q^{p -1} \equiv 1 \space mod \space {(p)}$

We know $p^{q -1} \equiv 0 \space mod {(p)}$ and $q^{p -1} \equiv 0 \space mod {(q)}$

Now we can combine $p^{q -1} \equiv 1 \space mod {(q)} \space and \space$$q^{p -1} \equiv 0 \space mod{(q)}$

We get, $p^{q -1} + q^ {p-1} \equiv 1 \space (mod \space q)$

In the same way, we can also combine

$q^{p -1} = 1 \space mod {(p)} \space and \space p^{q -1} = 0 \space (mod\space p)$

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

distinct prime numbers p and q both divides $p^{q -1} + q^ {p-1} - 1$

and also pq divides $p^{q -1} + q^ {p-1} - 1$

So, $p^{q -1} + q^ {p-1} - 1 \equiv 0 (mod \space pq)$

$p^{q -1} + q^ {p-1} \equiv 1 \space (mod \space pq)$

Answer: $p^{q -1} + q^ {p-1} \equiv 1 \space (mod \space pq)$