Question #96788
Let p and q be distinct prime numbers. Prove that p
q−1 + q
p−1 ≡ 1 mod pq.
1
Expert's answer
2019-10-21T10:51:59-0400

Proof Of a problem of distinct prime numbers

We need to prove pq1+qp1p^{q -1} + q^ {p-1} \equiv 1 mod (pq)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


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


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

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


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


In the same way, we can also combine


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


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

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


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


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


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



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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS