¿Por qué son todos los no-números primos divisible por un número primo?

Question

En Euclid infinito de números primos prueba, la lógica es la siguiente:

Asumir un conjunto $S$ de todos los números primos en la existencia es finita (hay una cantidad finita de números primos)

A continuación, debe haber una mayor prime $p$

$$n = (2 \cdot 3 \cdot 5\cdots p) + 1$$

$n > p$, y en virtud de la prueba de la asunción, $n$ no puede ser primo.*

Aquí es donde la lógica me confunde. ¿Por qué es que, dado que si un número no es primo, entonces es automáticamente divisible por un primo. No puedo pensar en un ejemplo a contradecir, pero eso no es una prueba de que no existe ningún número que no es primo y no divisible por los números primos.

Answer 1

Uno puede demostrar que esta para todos los enteros mayores que $1$ por inducción: sabemos que $2$ es un primo. Ahora ou paso inductivo suponga que para todo $i<n$, $i$ es el primer o divisible por un primo. Caso 1: $n$ es primo; hemos terminado. Caso 2: $n$ es compuesto, por lo $ab = n$$a, b < n$. Así que cada uno de ellos es divisible por un primo. Hemos terminado.

Esencialmente el mismo argumento muestra que todos los enteros mayores que $1$ se puede escribir como un producto de números primos.

Answer 2

Lema $\ $ El mínimo factor de $>1\,$ $\ n>1\,$ es primo.

Prueba $\ $$\,n>1$ tiene al menos un factor de $> 1,\,$ viz. $\,n.\,$ Deje $\,p\,$ ser por lo menos su factor de $>1.\,$ $\,p\,$ es el primer ($\,p\,$ tiene una adecuada divisor $\,1 < d < p\,$ $\,d\mid p\mid n\,\Rightarrow\,d\mid n,\,$ contra minimality de $\,p).$

Comentario $\ $ Más en general, se demuestra que prime el menor elemento de un conjunto a $\,S\,$ de los enteros $> 1$ que es cerrado bajo divisores $> 1,\,$ es decir $ $ si $\,S\,$ contiene $\,n\,$ $\,S\,$ contiene cada divisor $> 1$ $\,n.\,$ Sobre el $\,S\,$ es el conjunto de factores $>1$ $\,n.$

Podemos interpretar la prueba constructiva de la siguiente manera. Supongamos que tenemos un algoritmo $\,n\mapsto f(n)\,$ que se obtiene un adecuado factor de cada nonprime $\,n > 1.\,$ Luego de iterar el algoritmo debe, finalmente, terminar en un primer factor de $\,n,\,$ pues de lo contrario se produciría un infinito estrictamente descendente de la secuencia adecuada de los factores (ver más abajo), contra $\,\Bbb N\,$ es bien ordenado

$$ n > f(n) > f(f(n)) > f(f(f(n))) >\, \cdots$$

Answer 3

Usted está en buena compañía en su error. Algunos de los grandes matemáticos, incluyendo Dirichlet, han cometido el mismo error: informar falsamente que Euclides de la prueba por contradicción.

Euclides prueba dice que si usted toma cualquier conjunto finito de números primos (por ejemplo, $2$, $11$, y $19$) y los multiplicaré y, a continuación, agregue $1$, el número resultante no es divisible por ninguno de los números primos en el conjunto finito con el que comenzó (lo $(2\cdot11\cdot19)+1$ no es divisible por $2$, $11$, o $19$ debido a su resto en la división por cualquiera de esos números es $1$.

Por lo tanto, el conjunto finito comenzó con el puede ser extendido a un mayor conjunto finito: los factores primos de (en este ejemplo) $(2\cdot11\cdot19)+1$.)

La razón por la que el número de $(2\cdot11\cdot19)+1$ debe ser divisible por algún primo es que si no es divisible por ningún primer distinto de sí mismo, entonces es primo y por supuesto que es divisible por sí mismo.

PS: Algunas personas comentando a continuación están descontentos con mi último párrafo de arriba, así que voy a añadir esto: Vamos a hacer una prueba por contradicción en esto: Considerar el menor número $N$ que es no es divisible por ningún primo. No se puede divisble por algo más pequeño que sí con la excepción de $1$, ya que no-necesariamente-el primer factor, siendo más pequeño que el más pequeño de contraejemplo, sería divisible por algún primo, y, a continuación, $N$ sería divisible por que el primer. Así que no son divisibles por nada excepto a sí misma y $1$, $N$ sería la primera, y por lo tanto divisible por algún primo, es decir, a sí mismo.

Answer 4

Asumir su "no-el primer número de" no es divisible por un primo. Porque el único teorema de factorización, todos los números se pueden escribir como un producto de números primos. Esto significa que su "no-número primo" se puede escribir como un producto de números primos. Pero no puede ser escrito como un producto de números primos por definición, por lo que debe ser divisible por sí misma - de hacer su "no-el primer número de" un número primo.