Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos»
Contenido eliminado Contenido añadido
Convierto las notas en verdaderas notas al pie (faltaría pasar las formulas a sintaxis de LaTeX)) |
|||
Línea 22:
</pre>
Otro, similar pero que consiste en iterar hasta la raíz cuadrada de N<ref>Un número compuesto (
</br>
Dem: Supongamos que sí puede haber más de uno. Llamemos A y B a esos dos números primos. Llamemos P1, P2,.. Pn al resto de los números primos factores de C.</br>▼
Sea dA = A - raizcuad (C)</br>▼
Sea dB = B - raizcuad (C)</br>▼
Si A y B son mayores que la raíz cuadrada de C, entonces dA y dB serán positivos</br>▼
Entonces C = A*B*P1*P2... = (raizcuad (C)+dA)*(raizcuad (C)+dB)*P1*P2... = (raizcuad (C)*raizcuad (C) + dA*raizcuad (C) + dB*raizcuad (C) + dA*dB)*P1*P2... = (C + (dA+dB)*raizcuad (C) + dA*dB)*P1*P2...</br>▼
C*P1*P2.. + (dA+dB)*raizcuad (C)*P1*P2... + dA*dB*P1*P2...</br>▼
Obviamente, toda esa suma es mayor a C. Como partimos diciendo que C era igual a esa suma llegamos a una contradicción</br>▼
Por lo tanto, a lo sumo un factor puede ser mayor que la raíz cuadrada de C.</br>▼
</ref>
<pre>
Línea 40 ⟶ 50:
</pre>
Otro, que combina ambos, consiste en, además, ir incrementando i de a 2, 4, 2, 4..<ref>Los números primos (
</br>
Dem: Todo número natural puede expresarse como 6n±r, para algún n. R variara solo entre 0 y 5.</br>▼
6n+0 es divisible por 6 SIEMPRE</br>▼
6n+2 es divisible por 2 SIEMPRE</br>▼
6n+3 es divisible por 3 SIEMPRE</br>▼
6n+4 es divisible por 2 SIEMPRE</br>▼
6n+1 y 6n-1 (o lo que es lo mismo a efectos del análisis, 6n+5), no proporcionan ninguna garantía de divisibilidad, por lo tanto los números primos solo pueden encontrarse entre ellos).</br>▼
</ref>
<pre>
Línea 63 ⟶ 81:
== Notas ==
{{Listaref}}
▲Dem: Supongamos que sí puede haber más de uno. Llamemos A y B a esos dos números primos. Llamemos P1, P2,.. Pn al resto de los números primos factores de C.
▲Sea dA = A - raizcuad (C)
▲Sea dB = B - raizcuad (C)
▲Si A y B son mayores que la raíz cuadrada de C, entonces dA y dB serán positivos
▲Entonces C = A*B*P1*P2... = (raizcuad (C)+dA)*(raizcuad (C)+dB)*P1*P2... = (raizcuad (C)*raizcuad (C) + dA*raizcuad (C) + dB*raizcuad (C) + dA*dB)*P1*P2... = (C + (dA+dB)*raizcuad (C) + dA*dB)*P1*P2...
▲C*P1*P2.. + (dA+dB)*raizcuad (C)*P1*P2... + dA*dB*P1*P2...
▲Obviamente, toda esa suma es mayor a C. Como partimos diciendo que C era igual a esa suma llegamos a una contradicción
▲Por lo tanto, a lo sumo un factor puede ser mayor que la raíz cuadrada de C.
▲Dem: Todo número natural puede expresarse como 6n±r, para algún n. R variara solo entre 0 y 5.
▲6n+0 es divisible por 6 SIEMPRE
▲6n+2 es divisible por 2 SIEMPRE
▲6n+3 es divisible por 3 SIEMPRE
▲6n+4 es divisible por 2 SIEMPRE
▲6n+1 y 6n-1 (o lo que es lo mismo a efectos del análisis, 6n+5), no proporcionan ninguna garantía de divisibilidad, por lo tanto los números primos solo pueden encontrarse entre ellos).
|