Divisibilidad y Primos

En un problema de divisibilidad, las mejores herramientas suelen ser:
si a / b y a / c => a / (b-c) , a / (b+c) , a / (bx + cy) con x e y también enteros.
si a / b y b =/=0 entonces el módulo de b es mayor o igual que el módulo de a.

http://www.ehu.es/olimpiadamat/Curso%202005-06/Material/Aritmetica/Aritmetica.pdf

Dados dos números enteros a y b (con a distinto de 0), se dice que a divide a b, y lo escribimos como a/b,si existe un c∈Z tal que b= ac.
También se dice que a es un factor o divisor de b, y que b es un múltiplo de a.
Algunas propiedades derivadas de la definición anterior:

1/a
a/0
a/b y a/c ⇒ a/b+c , ab+c o mas generalmente:
a/b y a/c ⇔ a/bx+cy para cualesquiera x, y∈ Z
a/b y b/a ⇒ a = b o bien a = -b

Algoritmo de Euclides

Este método se basa en la siguiente propiedad:
si A y B son enteros entonces DCM(A,B) = DCM(A-B,B)
Pueden encontrar la demostración aquí.

Buscando Primos
Una forma de ver si un número es primo es probar dividirlo por todos los números menores que él y si ninguno lo divide, ¡ganamos!, el número es primo
Sin embargo, el divisor (distinto de n) más grande posible es n/2, así que podríamos probar sólo hasta n/2 en vez de n-1. Pero si n/2 es un número entero que es divisor de n, entonces 2 también es divisor (¡porque n dividido 2 es entero!), pero ya probamos antes si el 2 dividía a n. Así que no hace falta probar con el n/2. Entonces el siguiente divisor más grande posible es n/3, pero por un razonamiento análogo, tampoco hace falta probarlo ya que antes habíamos probado con 3.
¿Hasta cuando podemos repetir esto? Bueno hasta que n/i = i, o sea hasta que n = i^2, o sea hasta que i=sqrt(n). Una forma más formal de ver esto es que si d es un divisor de n, entonces n/d es un divisor de n. Así que en vez de probar con estos dos números hace falta probar sólo con el más chico. Pero si uno es mayor que sqrt(n) entonces el otro es menor que n/sqrt(n) =sqrt(n). Por ello el más chico seguro que es menor que n y entonces sólo hace falta probar hasta sqrt(n)
Vamos a probar si 7247 es primo
Sqrt(7247)=85.129 debemos probar hasta con el número primo menor o igual que 85.129 que
en este caso es el 83

Como lectura esta muy bien el Teorema de los números primos:
http://thales.cica.es/rd/Recursos/rd97/UnidadesDidacticas/16-2-o-primos.html

León-Sotelo