Muestran que entre números naturales consecutivos $16$ uno es coprimo de todos los demás

Question

Muestran que entre números naturales consecutivos $16$ uno es coprimo de todos los demás.
¿Es útil usar el algoritmo de división en $16$?
$16k,16k+1,16k+2,...16k+15$

Answer 1

Primero apagado, usted debe observar que, desde cualquiera de los dos números en la secuencia diferentes a la mayoría de los 15, cualquier factor común es en la mayoría de los 15. Por lo tanto, cualquier número que no coprime a los demás es divisible por uno de los primos de 2,3,5,7,11,13.

Ahora bien, si un número $x$ en la secuencia es divisible por $p = 2, 3, $ o $7$, entonces no se puede coprime a los demás, ya que en ese caso cualquiera de las $x-p$ o $x+p$ también se encuentran en la secuencia. (Si $x-p$ no está en la secuencia, el primer elemento es, al menos,$x-p+1$, por lo que el último elemento es, al menos,$x-p+16 > x+p$.)

Por lo tanto, $x$ es un deseada coprime elemento si y sólo si las siguientes condiciones se cumple:

• $x$ no es divisible por 2, 3, 5, o 7.
• Si $x$ es divisible por 11, a continuación, $x-11$ $x+11$ no están en la secuencia.
• Si $x$ 13, a continuación, $x-13$ $x+13$ no están en la secuencia.

Consideramos que las clases de congruencia modulo 30. De estos, el conjunto $S = \{1, 7, 11, 13, 17, 19, 23, 29\}$ representan elementos divisible ni por 2 ni 3 ni 5. Ahora debemos considerar cada posible conjunto de dieciséis años consecutivos de residuos y argumentan que hay suficientes elementos de $S$ que al menos uno de ellos satisface nuestras condiciones para ser coprime.

En particular, nos damos cuenta de que es suficiente (aunque no necesario) para buscar un elemento en la secuencia de $S$ que es coprime 7, 11, 13.

Tenga en cuenta que en dicha secuencia no puede ser sólo un elemento de una clase residual en $S$ divisible por 11, y del mismo modo, sólo un elemento de una clase residual en $S$ divisible por 13. Podría haber dos divisible por 7, ya que sólo se requiere una diferencia de 14, lo que sucede en tres casos:

1. Cuando la secuencia de los elementos de la forma $30k+17$ $30(k+1) +1$
2. Cuando la secuencia de los elementos de la forma $30k+23$ $30(k+1) +7$
3. Cuando la secuencia de los elementos de la forma $30k+29$ $30(k+1) +13$

Consideramos que el residuo aparece primero en la secuencia. (Yo sería feliz para evitar que los casos explícitamente como este, pero por lo que parece necesario para el argumento, y los dos últimos casos son quisquillosos.)

• Si el primer elemento de $S$ es de la forma $30k+1$, entonces el primer elemento en general es $30k$ o mayor. Esto significa que $30k+1, 30k+7, 30k+11, 30k+13$ están todos en la secuencia. En la mayoría de uno de estos cuatro elementos es divisible por 11, en la mayoría de los que uno es divisible por 13, y por encima en la mayoría de los que uno es divisible por 7. Por lo tanto, uno de ellos es coprime a todos los elementos en la secuencia, como se desee.
• Si el primer elemento de $S$ es de la forma $30k+7$, entonces el primer elemento es, al menos, $30k+2$ y por lo tanto la secuencia contiene $30k+7, 30k+11, 30k+13, 30k+17$. De nuevo uno de estos es de nuevo divisible por ninguno de 7, 11 ni 13.
• Si el primer elemento de $S$ es de la forma $30k+11$ o $30k+13$, entonces el primer elemento es, al menos, $30k+8$ y por lo tanto la secuencia contiene $30k+13, 30k+17, 30k+19,30k+23$. De nuevo uno de estos es de nuevo divisible por ninguno de 7, 11 ni 13.
• Si el primer elemento de $S$ es de la forma $30k+17$, luego por el mismo razonamiento, la secuencia contiene los elementos $30k+17, 30k+19,30k+23, 30k+29$, de los cuales al menos uno es coprime como se desee.
• Si el primer elemento de $S$ es de la forma $30k+19$, entonces la secuencia contiene los elementos $30k+19,30k+23, 30k+29, 30(k+1) + 1$ y el argumento es el mismo.
• Si el primer elemento de $S$ es de la forma $30k+23$, entonces la secuencia contiene los elementos $30k+23, 30k+29, 30(k+1) + 1$. En este punto tenemos que ser más cuidadosos, ya que cada uno de estos tres podría muy bien ser divisible por 7,11,13. Sin embargo, en este caso, tenga en cuenta que $30k+29 \pm 11$ $30k+29 \pm 13$ se encuentran fuera de los límites de la secuencia (el primer elemento se encuentra en el rango $[30k+20, 30k+23]$ y el último elemento que se encuentra en el rango $[30(k+1)+5,30(k+1)+8]$). Por lo tanto para este elemento no coprime que debe ser divisible por 7. Si se intenta forzar $x = 30(k+1) + 1$, a no ser coprime, se examinan los elementos $x \pm 11, x \pm 13$. De estos, sólo $x-11 = 30k+20$ es posiblemente en la secuencia, que por lo tanto sería el rango de $[30k+20,30(k+1)+5]$. En ese caso, podemos ver que $(30k+23)$ podría ser divisible por 13, pero, a continuación, $(30k+23)\pm 13$ se encuentran fuera de la secuencia, de manera que $30k+23$ debe ser coprime después de todo.
• Si el primer elemento de $S$ es de la forma $30k+29$, entonces la secuencia contiene los elementos $30k+29, 30(k+1) + 1, 30(k+1)+7$. Si $30(k+1)+11$ se encuentra en la secuencia de cuatro elementos de$S$, con al menos uno de ellos coprime a 7,11,13, como se desee. Por lo tanto, nos limitamos a cuando el primer elemento es $30k+24$ o $30k+25$ y el último elemento es $30(k+1)+9$ o $30(k+1)+10$. De nuevo, vemos que los tres elementos $30k+29, 30(k+1) + 1, 30(k+1)+7$ pueden ser divisible por uno de 7,11,13. Desde $30(k+1) + 1 \pm 11$ $30(k+1) + 1 \pm 13$ se encuentran fuera de la secuencia de la gama, $30(k+1) + 1$ es coprime a menos que sea el uno divisible por 7. Entonces, si examinamos $x = 30k+29$, de los valores de $x\pm 11, x \pm 13$ $x+11$ es posiblemente en la secuencia, la cual debe ser $[30k+25, 30(k+1)+10]$. Pero, a continuación, $30(k+1)+7\pm 13$ ambos se encuentran fuera de la secuencia. Se realiza por el mismo razonamiento que en el caso anterior.