Demostración por contradicción en relación a los números primos. ¿Dónde está la contradicción?

Question

Declaración a demostrar:

Demuestra que si $n > 1$ no es divisible por ningún número primo $p$ donde $p \le \sqrt{n}$ entonces $n$ es un número primo.

Supongamos que asumimos que $n$ es compuesto. Entonces demostramos que $n$ es divisible por un número primo $\le \sqrt{n}.

Hemos demostrado que un número compuesto es divisible por un número primo $\le \sqrt{n}.$. ¿Podemos deducir justamente que un número primo no es divisible por un número $\le \sqrt{n}$? Dudo de esto. En lo que respecta a esta demostración, por lo que sabemos, tanto los números compuestos como los números primos podrían ser divisibles por un número primo $\le \sqrt{n}$. ¿Dónde está la contradicción?

Answer 1

Su pregunta realmente concierne la lógica de las contrapositivas. Está demostrando que una condición suficiente para que $n$ sea primo es que ningún número primo menor o igual a $\sqrt n$ divide a $n$. Una forma de hacerlo es mostrar que una condición necesaria para que $n$ sea compuesto (negación de $n>1$ primo) es la negación de la condición dada anteriormente.

Entonces, la lógica funciona de la siguiente manera. Quiere demostrar que $P$ implica $Q$ (así que $P$ es la condición suficiente). El método es probar la contrapositiva de la implicación, que $\neg Q$ implica $\neg P$ (es decir, demostrar que $\neg P$ es una condición necesaria para $\neg Q$). Dado que se ha probado la contrapositiva, se puede estar seguro de que $P$ implica $Q también. Una forma de ver eso es comparar las tablas de verdad. Pero, uno puede estar convencido del siguiente argumento: $P\implies Q$ sigue de $\neg Q\implies \neg P$ ya que $P$ y $\neg Q$ implicarían $\neg P$, una contradicción.

Answer 2

No estoy seguro si entiendo tu pregunta. Pero si quieres probar que si $n$ es compuesto, debe haber al menos un primo $p\leq\sqrt{n}$ que lo divide:

1. Cada número compuesto tiene al menos dos factores primos.
2. Suponga que el primo más pequeño que divide a $n$ es $p$, y el siguiente más pequeño es $q

Ahora, si $p \gt \sqrt{n}$, eso significa que $q \gt \sqrt{n}$, ya que si no lo fuera, entonces no sería más grande que $p$.

Dos números multiplicados juntos que ambos son mayores que $\sqrt{n}$ no pueden ser iguales a $n$, porque la función raíz cuadrada es estrictamente creciente. Por lo tanto, el primo más pequeño que divide a $n$ debe ser $\leq \sqrt{n}$.

Answer 3

"¿Podemos deducir justamente de esto que un número primo no es divisible por un número <= sqrt(n)?"

Bueno, obviamente[#], pero eso no es en absoluto el punto. Nunca nos preguntaron probar algo así y no necesitamos hacerlo.

Se nos pidió demostrar "Si $n >1$ no es divisible por ningún número, $k$ $1 < k \le \sqrt{n}$ entonces $n$ es primo".

Hicimos una demostración por contradicción "Si $n$ es compuesto, entonces $k|n$ para algún $k$"

POR LO TANTO "Si $n$ es no divisible $\implies$ $n$ no es compuesto $\implies$ $n$ es primo."

¿Probamos que $n$ primo $\implies$ $n$ no es divisible por ningún número menor que $\sqrt{n}$? No, no lo hicimos. ¿Por qué deberíamos haberlo hecho? Eso no era lo que estábamos tratando de demostrar.

\=====

[#] Bueno, obvio. Si $n$ es primo no es divisible por nada más que él mismo y 1. ¡Obvio!

Answer 4

Sabemos que cualquier número entero positivo siempre es mayor que su raíz cuadrada de sí mismo como $25>\sqrt{25}$ entonces $n>\sqrt{n}$. ahora dado $p\le \sqrt{n}$ por lo tanto $n > \sqrt{n}\ge p$. entonces $n>p$ y $p>1$. por lo tanto $p$ no es igual a $n$ ni a $1$.

deje que $p$ divida a $n$. ahora $p$ no es ni $n$ ni $1$ pero divide a $n.

ahora si $n$ es primo entonces solo sería divisible por $n$ y $1$. pero $p$ divide a $n$ aunque no es ni $n$ ni $1$.

por lo tanto $n$ no es primo, es decir, $n$ será primo si no es divisible por $p$ tal que $p\le\sqrt{n}$. (probado)