2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What have you tried in solving the question? Please include that below your question body (as an edit). $\endgroup$ – Parcly Taxel Jul 24 '18 at 15:53
  • $\begingroup$ you could do this in excel by hand -- what is the problem exactly? $\endgroup$ – gt6989b Jul 24 '18 at 15:56
  • $\begingroup$ @gt6989b Or just by hand, without excel ... $\endgroup$ – Peter Jul 24 '18 at 15:57
  • $\begingroup$ @Peter how? There are going to be a lot of combinations $\endgroup$ – mampuuu Jul 24 '18 at 15:59
  • $\begingroup$ 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. $\endgroup$ – Peter Jul 24 '18 at 16:03
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you get that $(6k+1)(6n+1)≡6(k+n)+1\not\equiv−1$ (mod12)? $\endgroup$ – mampuuu Jul 24 '18 at 16:27
  • $\begingroup$ @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. $\endgroup$ – N. S. Jul 24 '18 at 16:42
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But I guess 1 is not a prime number. $\endgroup$ – mampuuu Jul 24 '18 at 18:48
  • $\begingroup$ 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. $\endgroup$ – Joffan Jul 24 '18 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.