Hay siempre un número entero positivo $a$ tanto $a^2-4$ $a^2+4$ son cuadrática no residuos de $\bmod p$?

Question

Me gustaría probar (refutar si mal) la siguiente declaración:

Para todos los impares, números primos, excepto para $p=3,5$ o $13$, existe un integer $a>0$ tanto $a^2-4$ e $a^2+4$ son cuadrática no residuo $\bmod p$.

Aquí es lo que he hecho: supongamos que $p \notin \{3,5,13\}$ y considerar los diferentes casos:

Caso I: $p \equiv 3 \bmod 4$. Tenemos $q$ es residuo cuadrático (QR) iff $-q$ es cuadrática no-residuo (QNR).

Desde $p \neq 5$, entonces cualquiera de las $5$ es QNR (caso I-i) o $5$ es QR (caso I-ii).

En caso de que (I-i) no existe $b$ tal que $b^2 \equiv -5 \bmod p$ y obviamente $-b^2+4 \equiv 3^2 \bmod p$ e $-b^2-4 \equiv 1 \bmod p$, $b^2-4$ e $b^2+4$ son QNR. Basta con retirar $a=b$.

Considere ahora el caso (I-ii). Desde $p \neq 13$, luego

(I-ii-1) $13$ es cuadrática no-residuo (QNR) mod $p$

(I-ii-2) $13$ es residuo cuadrático (QR) mod $p$

En caso de que (I-ii-1), $65=5\cdot 13$ es QNR y existe $c$ tal que $c^2 \equiv -65 \bmod p$ y obviamente $-c^2-16 \equiv 7^2 \bmod p$ e $-c^2+16 \equiv 9^2 \bmod p$.

Deje $d=\frac{c}{2}$, $e=\frac{7}{2}$ e $f=\frac{9}{2}$ en $ \mathbb{Z}/p\mathbb{Z}$.

A continuación, $-d^2-4 \equiv e^2 \bmod p$ e $-d^2+4 \equiv f^2 \bmod p$ y tanto $d^2+4$ e $d^2-4$ son QNR. Basta con retirar $a=d$.

En el caso (I-ii-2) donde $5$ e $13$ son QR, no veo cómo proceder.

En el caso (II) donde $p \equiv 1 \bmod 4$, tenemos $q$ es residuo cuadrático (QR) iff $-q$ es residuo cuadrático (QNR) y aquí de nuevo el método anterior no funciona.

Yo también estoy interesado en cualquier sharp límite superior para el más pequeño de $a$, en términos de $p$.

Gracias por la ayuda.

Answer 1

Aquí está la solución en dos pasos.

---

En primer lugar, vamos a comprobar que cuando no se $a$, 2 es un QR. Esto es un montón de trabajo, y no funciona para algunos pequeños números primos. (Específicamente para $p=2, 3, 5, 7, 11, 13$.) Podemos comprobar de ellos por separado, y encontrar los tres contraejemplos de esa manera.

Supongamos que 2 es un QNR. Por lo tanto 8 es un QNR, 32 es un QNR, 18 es un QNR.

40 debe ser un código QR o de lo contrario nos encontramos con la secuencia de 32, 36, 40. Por lo tanto, el 20 es un QNR.

12 debe ser un código QR o de lo contrario nos encontramos con la secuencia 12, 16, 20. Por lo tanto 24 es un QNR, 48 es un QR, 96 es un QNR.

104 debe ser un código QR o de lo contrario nos encontramos con la secuencia 96, 100, 104. Por lo tanto 52 es un QNR.

28 debe ser un QNR o de lo contrario nos encontramos con la secuencia de 24, 28, 32. Por lo tanto 14 es un QR.

22 debe ser un código QR o de lo contrario nos encontramos con la secuencia 14, 18, 22. Por lo tanto 44 es un QNR.

Ahora nos encontramos con la secuencia de 44, 48, 52.

---

Segundo, suponiendo que $2$ es un QR y no hay casos de $a$ tal que $a^2-4$, $a^2+4$ son QNR, llegamos a una contradicción.

Si cualquiera de las tres números enteros consecutivos $k, k+1, k+2$ siga el patrón de QNR, QR, QNR, entonces el mismo es cierto para $4k, 4k+4, 4k+8$ y hemos terminado. Así que junto a cualquier QR es otro de los QR.

Si esto es cierto, pero no hay dos números enteros consecutivos son siempre QNR, entonces también estamos en problemas, porque entonces, al menos aproximadamente, $\frac23$ de los residuos de mod $p$ son QR.

Supongamos que $k, k+1$ son tanto QNR para algunos $k$. A continuación, $8k, 8k+8$ son tanto QNR, por lo $8k+4$ debe ser QNR o de lo $8k, 8k+4, 8k+8$ es la secuencia que desea. (Tenga en cuenta que $8k+4 \not\equiv 0 \pmod p$ porque $8k+8$ podría no ser QNR.) Por lo tanto, $2k, 2k+1, 2k+2$ es una secuencia de tres consecutivos QNRs.

La aplicación de este argumento, una vez más, vemos que $4k, 4k+1, 4k+2, 4k+3, 4k+4$ es una secuencia de cinco consecutivos QNRs. Entonces tenemos cada vez más secuencias como esta por recorrer en el argumento. Pero una vez que obtenemos una secuencia de más de $p$, se obtiene una contradicción.

Answer 2

parece creíble

jagy@phobeusjunior:~$ ./mse
  p  3  fails    p  5  fails    p  7   a:   3  p  11   a:   5  p  13  fails  
  p  17   a:   1  p  19   a:   5  p  23   a:   1  p  29   a:   6  p  31   a:   5
  p  37   a:   3  p  41   a:   8  p  43   a:   4  p  47   a:   1  p  53   a:   1
  p  59   a:   6  p  61   a:   5  p  67   a:   3  p  71   a:   13  p  73   a:   3
  p  79   a:   8  p  83   a:   1  p  89   a:   10  p  97   a:   3  p  101   a:   6
  p  103   a:   4  p  107   a:   1  p  109   a:   6  p  113   a:   1  p  127   a:   4
  p  131   a:   6  p  137   a:   1  p  139   a:   6  p  149   a:   6  p  151   a:   10
  p  157   a:   5  p  163   a:   3  p  167   a:   1  p  173   a:   1  p  179   a:   6
  p  181   a:   6  p  191   a:   5  p  193   a:   3  p  197   a:   1  p  199   a:   8
  p  211   a:   6  p  223   a:   3  p  227   a:   1  p  229   a:   5  p  233   a:   1
  p  239   a:   12  p  241   a:   12  p  251   a:   6  p  257   a:   1  p  263   a:   1
  p  269   a:   6  p  271   a:   5  p  277   a:   7  p  281   a:   10  p  283   a:   4
  p  293   a:   1  p  307   a:   3  p  311   a:   9  p  313   a:   7  p  317   a:   1
  p  331   a:   6  p  337   a:   7  p  347   a:   1  p  349   a:   6  p  353   a:   1
  p  359   a:   5  p  367   a:   4  p  373   a:   7  p  379   a:   6  p  383   a:   1
  p  389   a:   5  p  397   a:   3  p  401   a:   8  p  409   a:   5  p  419   a:   6
  p  421   a:   6  p  431   a:   9  p  433   a:   5  p  439   a:   8  p  443   a:   1
  p  449   a:   5  p  457   a:   3  p  461   a:   6  p  463   a:   3  p  467   a:   1
  p  479   a:   24  p  487   a:   3  p  491   a:   5  p  499   a:   6  p  503   a:   1
  p  509   a:   6  p  521   a:   8  p  523   a:   4  p  541   a:   6  p  547   a:   4
  p  557   a:   1  p  563   a:   1  p  569   a:   5  p  571   a:   6  p  577   a:   3
  p  587   a:   1  p  593   a:   1  p  599   a:   5  p  601   a:   5  p  607   a:   4
  p  613   a:   3  p  617   a:   1  p  619   a:   5  p  631   a:   10  p  641   a:   5
  p  643   a:   3  p  647   a:   1  p  653   a:   1  p  659   a:   5  p  661   a:   6
  p  673   a:   8  p  677   a:   1  p  683   a:   1  p  691   a:   6  p  701   a:   6
  p  709   a:   6  p  719   a:   9  p  727   a:   4  p  733   a:   3  p  739   a:   6
  p  743   a:   1  p  751   a:   8  p  757   a:   10  p  761   a:   10  p  769   a:   5
  p  773   a:   1  p  787   a:   3  p  797   a:   1  p  809   a:   5  p  811   a:   6
  p  821   a:   6  p  823   a:   4  p  827   a:   1  p  829   a:   5  p  839   a:   9
  p  853   a:   3  p  857   a:   1  p  859   a:   5  p  863   a:   1  p  877   a:   3
  p  881   a:   8  p  883   a:   4  p  887   a:   1  p  907   a:   4  p  911   a:   5
  p  919   a:   12  p  929   a:   8  p  937   a:   16  p  941   a:   6  p  947   a:   1
  p  953   a:   1  p  967   a:   3  p  971   a:   6  p  977   a:   1  p  983   a:   1
  p  991   a:   8  p  997   a:   5  p  1009   a:   9  p  1013   a:   1  p  1019   a:   6
  p  1021   a:   6  p  1031   a:   9  p  1033   a:   3  p  1039   a:   19  p  1049   a:   8