Encontrar el número de pares ordenados

Question

Encuentre el número de pares ordenados $(p , q)$ tal que $p , q $ son ambos números primos menores que 50 , y $pq$ +1 es divisible por 12

Editar : Lo que he hecho es escribir todos los primos por debajo de 50 congruentes con el módulo 12. Por ejemplo: 11 $ \equiv$ -3 $(mod 12)$

Answer 1

Sugerencia Tenga en cuenta que $p,q$ no puede ser 2 o 3. Entonces $p,q \equiv \pm 1 \pmod{6}$ .

Tenga en cuenta que $$(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} $$

Por lo tanto, la única posibilidad que queda es $$(6k+1)(6n-1) \equiv 6(n-k)-1 \pmod{12} $$ que es $\equiv -1 \pmod{12}$ si y sólo si $k-n$ está en paz.

Answer 2

Está claro que necesitamos ambos $p$ y $q$ para que sea coprima de $12$ , por lo que no podemos tener $p$ o $q$ igual a $2$ o $3$ .

Esto significa que $\{p,q\}\in\{1,5,7,11\}\bmod 12$ . Podemos calcular rápidamente los productos $\bmod 12$ a través de este conjunto:

\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}

Buscamos $p,q$ pares que dan $11\equiv -1 \bmod 12$ en la tabla anterior para que $12\mid pq{+}1$ . Así que seleccionaríamos los pares de los diferentes conjuntos de clases de residuos de forma adecuada, lo que da una forma de calcular cuántas opciones en total.

Por ejemplo, el conjunto de primos en el rango $\equiv 1 \bmod 12$ (Llama a esto $S_1$ ) se compone únicamente de $\{13,37\}$ . Esto nos da $|S_1|=2$ y de manera similar $|S_5|=4,$ $|S_7|=4,$ y $|S_{11}|=3$ . Así, tendremos $2\cdot 3 + 4\cdot 4 + 4\cdot 4 + 3\cdot 2 = 2\cdot 6+2\cdot 16= \fbox{44 }$ soluciones de pares ordenados.

Answer 3

Como los números están en un rango muy pequeño, escribí un simple script de Python para ello. Toma $ < 1 $ segundo.

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)

La respuesta:

44