Las caracterizaciones de los números primos

Question

Deje $\mathbb{P}$ ser el conjunto de los números primos.

Sabemos, a partir del Teorema de Wilson que $$(p-1)!\equiv-1 \pmod p \iff p \in \mathbb{P}$$

¿Qué otra de las fórmulas que con un si y sólo si ($\iff$) instrucción para caracterizar los números primos, no equivalente o derivados de Wilson del Teorema?

(No estoy preguntando acerca de los algoritmos de primalidad pruebas, sino más bien expresiones que sostienen exactamente para los números primos usando álgebra, módulo, integrales y otra de las cosas).

O expresiones como: $p \in \mathbb{P} \iff$ Expresión de p

Answer 1

Existe un polinomio de grado $25$ $26$ variables con coeficientes enteros tales que el conjunto de números primos es idéntico con el conjunto de valores positivos asumido por el polinomio como las variables de alcance sobre los enteros no negativos. (El polinomio se puede encontrar aquí.)

En otras palabras, no es un polinomio $h(a,b,c,\ldots,z)\in \mathbb{Z}[a,b,c,\ldots,z]$ de manera tal que un número natural $p\in\mathbb{N}$ es primo si y sólo si hay $a_0,b_0,c_0,\ldots,z_0\geq 0$ tal que $p=h(a_0,b_0,c_0,\ldots,z_0)$.

Nota: esta declaración no puede ser utilizado como un determinista de la prueba de primalidad. Si $p>0$ es compuesto, entonces un algoritmo basado en esta declaración (que comprobar si $p=h(a_0,b_0,c_0,\ldots,z_0)$ algunos $a_0,b_0,c_0,\ldots,z_0\geq 0$), que nunca va a terminar, ya no es (conocida) de manera de acotar el tamaño de la posible $26$-tuplas que iba a dar a la deseada igualdad.

Answer 2

1. Muy simple, pero incluido en aras de la exhaustividad: ($n$ es primo) si y sólo si ([$n\gt1$] y el [{si $n$ divide $ab$} entonces {<$n$ divide $a$> o <$n$ divide $b$>}]).

2. Elevados a partir de un comentario, ya que el OP ha indicado es el tipo de cosa que quería: Giuga de la conjetura de los estados que $n$ es primo si y sólo si $1^{n-1}+2^{n-1}+\cdots+(n-1)^{n-1}\equiv-1\pmod n$.