# Thread: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

2. ## Re: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

$2^p\equiv 2$ (mod $p$)

3. ## Re: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

We will use Euler's Theorem, so let us first find $\phi(pq)$.

$$\phi(pq) = pq \left(1-\frac{1}{p}\right) \left( 1- \frac{1}{q} \right) = (p-1)(q-1) = (pq+1)-(p+q).$$

Now, since $\gcd{(2,pq)} = 1$ ($p$ and $q$ are odd), by Euler's theorem,
$$2^{(pq+1)-(p+q)} \equiv 1 \mod{pq}.$$

Multiplying by $2^{p+q}$ gives the desired result.