Utilizando gauss ' lema s encontrar $(\frac{n}{p})$ (símbolo de Legendre)

Question

Lo siento si esto termina siendo largo.

Así que, básicamente, estoy tratando de entender las pruebas de Gauss lema para las cosas tales como $(\frac{2}{p})$ $(\frac{3}{p})$ etc

Para $(\frac{2}{p})$ me da esta prueba

Sabemos que $(\frac{a}{p}) = (-1)^n$

Así que encontrar a $n$ es importante aquí, obviamente.

$n$ es representativo del número de elementos en el conjunto $\{{a,2a,3a,...,\frac{(p-1)}{2}}\}$ $\frac{p}{2}$ $p$ para $a=2$ este va a ser $\{2,4,5,...,(p-1)\}$

Aproximadamente la mitad tienen menos de p/2 y la otra mitad se encuentran entre p/2 y p, por lo que es importante, precisamente, encontrar el punto medio.

Así que si $p = 1+4k$ $2,4,6...,2k < p/2$ $p/2 < 2k+2, 2k+4,...,4k$
Por lo tanto, $n=k=(p-1)/4$
Si $p \equiv 1$ mod $8$ $n = (p-1)/4$ es incluso
Si $p \equiv 5$ mod $8$ $n = (p-1)/4$ es impar

por lo $(\frac{2}{p}) = +1$ Si $p \equiv 1$ mod $8$
y
por lo $(\frac{2}{p}) = -1$ Si $p \equiv 5$ mod $8$

A continuación, la prueba va y hace lo mismo para $p = 3+4k$, lo que permite resolver la $(2/p)$ 3 mod 8 y 5 mod 8

Estoy teniendo problemas para entender esto completamente. Sobre todo, me pregunto donde la $p = 1+4k$ proviene. Entiendo que se trata de $p \equiv 1$ mod $4$ Pero estoy confundido en cuanto a por qué se eligió mod 4. Tal vez mi malentendidos será más evidente cuando trato de crear este tipo de prueba para $(\frac{3}{p})$

Así que para empezar, $a = 3$ por lo que puede crear el conjunto $\{3,6,9,..,\frac{3(p-1)}{a}\}$

Así, con la suposición de que aproximadamente la mitad serán de menos de $p/2$ y la mitad será mayor que $p/2$ voy a intentar encontrar el punto medio.

Si $p = 1 + 4k$, (aquí es donde creo que me lío, tal vez un número distinto de 4k debe ser utilizado. Tal vez 6k?)

$3,6,9,..,3k<p/2$ $p/2 < 3k+3,3k+6,...,6k<p$
Por lo tanto, $n = k=(p-1)/6$.
Así que supongo que aquí, necesito determinar cuando $(p-1)/6$ es aún y cuando se $(p-1)/6$ es impar.

Así, a partir de la observación de la ecuación puedo ver que $(p-1) \equiv 0$ mod $12$ me va a dar y hasta número. En donde tengo el mod 12 por simplemente multiplicar 6 por 2. Tan sólo el uso de la aritmética básica para obtener $p \equiv 1$ mod $12$. Así, extendiéndose sobre el que, $p \equiv 7$ mod $12$ me va a dar un número impar correcta?

A partir de esto puedo concluir que $(3/p) = 1$ al $p\equiv 1$ mod $12$ y $(3/p) = -1$ al $p\equiv 7$ mod $12$.
Luego para el otro congruencias, puedo hacer la misma cosa, excepto decir que quizás deje $p = 5+6k$?

Supongo que esto se puede extender a trabajar para otros $(a/p)$ como $(\frac{5}{p})$ correcto?

Answer 1

Gauss lema nos dice que nos fijamos en el número de negativos menos residuos en la lista de números

a, 2a, 3a, ..., $\frac{p-1}{2}a$

Cuando ese número es par, entonces $(\frac{a}{p})=1$, cuando impar, entonces $(\frac{a}{p})=-1$

Vamos a echar un vistazo a la lista para a=2. Tenemos la siguiente lista de números:

2, 4, ..., p-1

Inicio de esta lista contiene los valores en el intervalo de $(0, \frac{p}{2})$, lo que equivale a su (positivo) menos residuos; el resto de los valores están en el intervalo de $(\frac{p}{2}, p)$. Sólo estamos interesados en el número de números que están en el último intervalo, obviamente, estos han negativo menos residuos en el intervalo de $(-\frac{p}{2}, 0)$.

El número de números en el intervalo de $(\frac{p}{2}, p)$ claramente es igual al número de enteros en el intervalo de $(\frac{p}{4}, \frac{p}{2})$.

Aquí es donde mod 8 viene en: la determinación de que el número de enteros en el intervalo mencionado es par o impar es más fácil de hacer si sabemos que el inicio entero (el primero uno de los más grandes de $\frac{p}{4}$) y el final entero (último menor que $\frac{p}{2}$) en la lista: por ejemplo, cuando la lista se inicia con un número par y termina con un número par, sabemos que el número total en la lista es impar.

Así podemos distinguir 4 casos: $p \equiv 1, 3, -3, -1$ mod8.

$p \equiv 1$ mod8: $p=1+8k$; inicio entero es el mínimo mayor que $2k+\frac{1}{4}$, por lo tanto 2k+1; final entero es el máximo de un menor que $4k+\frac{1}{2}$, por lo tanto 4k; el número de enteros en [2k+1, 4k] es, incluso, lo $(\frac{2}{p})=1$

$p \equiv -1$ mod8: $p=-1+8k$; el intervalo de ahora se convierte en $[2k, 4k-1]$, que contiene un número par de números enteros, por lo $(\frac{2}{p})=1$

$p \equiv 3$ mod8: $p=3+8k$; el intervalo se convierte en $[2k+1, 4k+1]$, que contiene un número impar de números enteros, por lo $(\frac{2}{p})=-1$

$p \equiv -3$ mod8: $p=-3+8k$; el intervalo se convierte en $[2k, 4k-2]$, lo $(\frac{2}{p})=-1$

Lo mismo se puede hacer para$a=3$, pero ahora tenemos que considerar al menos los residuos de la siguiente lista de números:

3, 6, ..., $\frac{p-1}{2}3$

que se divide en tres subconjuntos de los múltiplos de 3:

si $0<3x<\frac{p}{2}$ menos de residuos es positiva

si $\frac{p}{2}<3x<p$ menos de residuos es negativa

si $p<3x<3\frac{p}{2}$, el menor residuo es positivo de nuevo

Por eso, deseamos conocer si el número de múltiplos de 3 en el intervalo de $(\frac{p}{2},p)$ es par o impar. Del mismo modo que el anterior para $a=2$, esto equivale a mirar el número de enteros en el intervalo de $(\frac{p}{6},\frac{p}{3})$. Así que aquí es donde mod 12. Nos fijamos en $p \equiv 1, 5, -5, -1$ mod12 (tenga en cuenta que 3 y -3 mod 12 no son primos).

$$ \begin{array}{r|r|l|l|c|c} \text{p mod12} & \text{p} & \text{lower} & \text{upper} & \text{count} & (\frac{3}{p}) \\ \hline 1 & 1+12k & 2k+1 & 4k & even & 1 \\ -1 & -1+12k & 2k & 4k-1 & even & 1\\ 5 & 5+12k & 2k+1 & 4k+1 & odd & -1 \\ -5 & -5+12k & 2k & 4k-2 & odd & -1 \end{array} $$

Para $a=5$ de la tierra en una situación un poco diferente, como el conjunto de los múltiplos de 5 está dividido en 5 partes, dos de los cuales son relevantes (es decir, tienen menos negativo de los residuos). Resumen:

$$ \begin{array}{r|r|l|l|c|l|l|c|c|c} \text{p mod20} & \text{p} & \text{lower > %#%#%} & \text{upper < %#%#%} & \text{count 1} & \text{lower > %#%#%} & \text{upper < %#%#%} & \text{count 2} & \text{total} & (\frac{5}{p}) \\ \hline 1 & 1+20k & 2k+1 & 4k & even & 6k+1 & 8k & even & even & 1 \\ 3 & 3+20k & 2k+1 & 4k & even & 6k+1 & 8k+1 & odd & odd & -1 \\ 7 & 7+20k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+2 & even & odd & -1 \\ 9 & 9+20k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & even & 1 \\ -9 & -9+20k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & even & 1 \\ -7 & -7+20k & 2k & 4k-2 & odd & 6k-2 & 8k-3 & even & odd & -1 \\ -3 & -3+20k & 2k & 4k-1 & even & 6k & 8k-2 & odd & odd & -1 \\ -1 & -1+20k & 2k & 4k-1 & even & 6k & 8k-1 & even & even & 1 \end{array} $$

Por lo $\frac{p}{10}$ si y sólo si $\frac{p}{5}$. En este caso en particular, esto puede ser reformulado a $3\frac{p}{10}$ si y sólo si $2\frac{p}{5}$.

Para $(\frac{5}{p}) = 1$ hay 7 segmentos a considerar, 3 de los cuales tienen efectos negativos residuos: $p \equiv \pm 1, 9 mod 20$, $(\frac{5}{p}) = 1$ y $p \equiv \pm 1 mod 5$. Resumen:

$$ \begin{array}{r|r|l|l|c|l|l|c|l|l|c|c|c} \text{p mod28} & \text{p} & \text{lower %#%#%} & \text{upper %#%#%} & \text{count 1} & \text{lower %#%#%} & \text{upper %#%#%} & \text{count 2} & \text{lower %#%#%} & \text{upper %#%#%} & \text{count 3} & \text{total} & (\frac{7}{p}) \\ \hline 1 & 1+28k & 2k+1 & 4k & even & 6k+1 & 8k & even & 10k+1 & 12k & even & even & 1 \\ 3 & 3+28k & 2k+1 & 4k & even & 6k+1 & 8k & even & 10k+2 & 12k+1 & even & even & 1 \\ 5 & 5+28k & 2k+1 & 4k & even & 6k+2 & 8k+1 & even & 10k+2 & 12k+2 & odd & odd & -1 \\ 9 & 9+28k & 2k+1 & 4k+1 & odd & 6k+2 & 8k+2 & odd & 10k+4 & 12k+3 & even & even & 1 \\ 11 & 11+28k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & 10k+4 & 12k+4 & odd & odd & -1 \\ 13 & 13+28k & 2k+1 & 4k+1 & odd & 6k+3 & 8k+3 & odd & 10k+5 & 12k+5 & odd & odd & -1 \\. -13 & -13+28k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & 10k-4 & 12k-6 & odd & odd & -1 \\ -11 & -11+28k & 2k & 4k-2 & odd & 6k-2 & 8k-4 & odd & 10k-3 & 12k-5 & odd & odd & -1 \\ -9 & -9+28k & 2k & 4k-2 & odd & 6k-1 & 8k-3 & odd & 10k-3 & 12k-4 & even & even & 1 \\ -5 & -5+28k & 2k & 4k-1 & even & 6k-1 & 8k-2 & even & 10k-1 & 12k-3 & odd & odd & -1 \\ -3 & -3+28k & 2k & 4k-1 & even & 6k & 8k-1 & even & 10k-1 & 12k-2 & even & even & 1 \\ -1 & -1+28k & 2k & 4k-1 & even & 6k & 8k-1 & even & 10k & 12k-1 & even & even & 1 \end{array} $$

Por lo $a=7$ si y sólo si $I_1 = (\frac{p}{14}, \frac{p}{7})$.