Discusión:División por tentativa

Contraejemplo

Hay un contraejemplo: 43 = 2 * 23, y 23 es mayor que la raiz de 23.

Esa cota es para la construccion de una criba de eratostenes donde no puede aparecer un numero compuesto mayor que la raiz de n, tal que no es multiplo de algun numero menor que la raiz de n.

Para hallar esto la cota si no me equivoco es n/2. — El comentario anterior es obra de 83.57.37.62 (disc. · contr. · bloq.), quien olvidó u omitió firmarlo. $k_{n}\,$ ■ 18:44 3 ago 2008 (UTC)

Respuesta

Esa cota es correcta. De hecho, tu contraejemplo no es un contraejemplo, porque $2\leq {\sqrt {43}}$. Aunque, si nos ponemos estrictos, $43\neq 2\times 23$ Así que más bien es $46=2\times 23$. Más bien Lo que debes de tomar en cuenta es que si $n$ es un número compuesto, entonces al menos un factor tiene que ser menor o igual que su raíz cuadrada. Y si no me crees, aquí tienes la demostración matemática que puedes encontrar en cualquier libro de teoría de números:

Teorema Si $n>1$ es un número entero que no es divisible por ningún número entero menor o igual que ${\sqrt {n}}$, entonces $n$ debe ser un número primo.

Demostración: La demostración es por reducción al absurdo. Supongamos que el teorema es falso, es decir, que $n$ no es divisible por ningún entero menor o igual que ${\sqrt {n}}$ pero que $n$ no es un número primo.

Como $n$ no es primo, entonces lo podemos factorizar como $n=pq$. Además, como $n$ no tiene factores primos menores o iguales que ${\sqrt {n}}$, entonces tampoco los tienen $p$ y $q$ y además ellos mismos son mayores que ${\sqrt {n}}$. Pero como $n=pq$, entonces estaríamos diciendo que $n>{\sqrt {n}}{\sqrt {n}}$, es decir, que $n>n$, lo cual es absurdo.

Por lo tanto el teorema no puede ser falso (es decir, es verdadero).

$k_{n}\,$ ■ 18:44 3 ago 2008 (UTC)

Malentendido

Disculpa, error mio entonces. Entendi que deberia dividirse entre todo numero primo menor que la raiz de n. Es cierto que al menos un primo ha de ser menor que la raiz cuadrada. Pero en ese caso supongo que tienes que despues de dividir has de repetir el proceso con n/(p1*p2*...*pn), donde pn son los primos por los que has dividido. puede ser? Siguiendo con el ejemplo 46 = 2 * 23, para hallar el 23.

No estoy seguro de si el articulo lo explica, pero si fuese asi, seria conveniente poner un ejemplo de la iteracion, para no dejar lugar a dudas.

Un saludo y gracias por tu trabajo. — El comentario anterior es obra de 83.57.37.62 (disc. · contr. · bloq.), quien olvidó u omitió firmarlo. $k_{n}\,$ ■ 13:36 6 ago 2008 (UTC)

Propuesta

Mejoraré el artículo cuando tenga tiempo. Pero no será pronto. $k_{n}\,$ ■ 13:36 6 ago 2008 (UTC)

Algoritmo

Dejo aquí una parte que estaba en número primo pero que igual queda mejor aquí:

A la hora de construir un algoritmo informático, no es necesario calcular explícitamente la raíz cuadrada, sino que se puede parar en cuando uno vea que el cociente es menor que el divisor. Concretamente, la última posibilidad de que N sea compuesto es dividirlo por un m primo tal que m+1 al cuadrado es mayor que N.

A lo mejor lo acabo aprovechando, a lo mejor no. Sabbut (めーる) 07:48 16 abr 2009 (UTC)