Find number of ordered pairs

Question

Find the number of ordered pairs $(p , q)$ such that $p , q $ are both prime numbers less than 50 , and $pq$+1 is divisible by 12

Edit : What i have done is i have written down all the primes below 50 congruent to modulo 12 . For example : 11 $ \equiv$ -3 $(mod 12)$

Answer 1

Hint Note that $p,q$ cannot be 2 or 3. Then $p,q \equiv \pm 1 \pmod{6}$.

Note that $$(6k+1)(6n+1) \equiv 6(k+n)+1 \not\equiv -1 \pmod{12} \\ (6k-1)(6n-1) \equiv -6(k+n)+1 \not\equiv -1 \pmod{12} $$

Therefore, the only posibility left is $$(6k+1)(6n-1) \equiv 6(n-k)-1 \pmod{12} $$ which is $\equiv -1 \pmod{12}$ if and only if $k-n$ is even.

Answer 2

Clearly we need both $p$ and $q$ to be coprime to $12$, so we cannot have $p$ or $q$ equal to either $2$ or $3$.

This means that $\{p,q\}\in\{1,5,7,11\}\bmod 12$. We can quickly calculate the products $\bmod 12$ across this set:

\begin{array}{l|cc} p\ \backslash\ q & 1 & 5 & 7 & 11 \\ \hline 1 & 1 & 5 & 7 & 11 \\ 5 & 5 & 1 & 11 & 7 \\ 7 & 7 & 11 & 1 & 5 \\ 11 & 11 & 7 & 5 & 1 \\ \end{array}

We are looking for $p,q$ pairs that give $11\equiv -1 \bmod 12$ in the above table so that $12\mid pq{+}1$. So we would select the pairs from the different residue class sets appropriately, which gives a way to calculate how many options in total.

For example, the set of primes in range $\equiv 1 \bmod 12$ (call this $S_1$) consists of just $\{13,37\}$. This gives us $|S_1|=2$ and similarly $|S_5|=4,$ $|S_7|=4,$ and $|S_{11}|=3$. Thus we will have $2\cdot 3 + 4\cdot 4 + 4\cdot 4 + 3\cdot 2 = 2\cdot 6+2\cdot 16= \fbox{44 }$ ordered pair solutions.

Answer 3

Since the numbers are in very small range, I wrote a simple Python script for it. Takes $ < 1 $ second.

def is_prime(x):
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3, int(x**0.5) + 1, 2):
        if x % i == 0:
            return False
    return True

ans = 0
for p in range(2, 50):
    if is_prime(p):
        for q in range(2, 50):
            if is_prime(q):
                    ans += (p*q + 1) % 12 == 0
print(ans)

The answer:

44