# Find number of ordered pairs

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)$

• What have you tried in solving the question? Please include that below your question body (as an edit). Commented Jul 24, 2018 at 15:53
• you could do this in excel by hand -- what is the problem exactly? Commented Jul 24, 2018 at 15:56
• @gt6989b Or just by hand, without excel ... Commented Jul 24, 2018 at 15:57
• @Peter how? There are going to be a lot of combinations Commented Jul 24, 2018 at 15:59
• We have $15$ primes below $50$, making $105$ pairs. Moreover $2$ and $3$ can be omitted because a number of the form $2k+1$ is odd and a number of the form $3k+1$ not disivisble by $3$. So, the number of pairs decreases to $78$. With a bit patience, well feasible by hand. Commented Jul 24, 2018 at 16:03

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.

• How did you get that $(6k+1)(6n+1)≡6(k+n)+1\not\equiv−1$ (mod12)? Commented Jul 24, 2018 at 16:27
• @mampuuu Just open the brackets and use the fact that $36 \equiv 0 \pmod{12}$. For the last non-equality, note that $6(k+n) \equiv 0,6 \pmod{12}$, depending if $k+n$ is even or odd. Commented Jul 24, 2018 at 16:42

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)


44

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.

• But I guess 1 is not a prime number. Commented Jul 24, 2018 at 18:48
• No it isn't; you're looking (in that case) for the prime numbers that fit $p\equiv 1 \bmod 12$. Similarly in the other cases you're looking for the sets of prime numbers $\equiv 5,7,11 \bmod 12$. Example added to answer. Commented Jul 24, 2018 at 18:51