Hice algo de esto pero no se si tiene que ver.

num = int(raw_input('Agrega un número: '))
num_2 = int(raw_input('Agrega otro número: '))
 
creo_que_es_primo = True
divisor = 2
while divisor < num and creo_que_es_primo:
    if num % divisor == 0:
        creo_que_es_primo = False
    divisor += 1
 
    if creo_que_es_primo:
        print 'El número', num, 'es primo'
    else:
        print 'El número', num, 'no es primo'
 
creo_que_es_primo_2 = True
divisor_2 = 1
while divisor_2 < num_2 and creo_que_es_primo_2:
    if num_2 % divisor_2 == 0:
        creo_que_es_primo_2 = False
    divisor_2 += 1
 
    if creo_que_es_primo_2:
        print 'El número', num_2, 'es primo'
    else:
        print 'El número', num_2, 'no es primo'
 
# Como dice que los divida, me imagino que se refiere a esto.
n = num / num_2
print n

Estamos tratando del ejercicio sólo por ahora el 129.

Aquí hay algo que no se si realmente viene al cuento.
http://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor

Saludo.

Buenas campeón:

Ahora toca usar los for-in.

Num1 = int(raw_input('Agrega un número: '))
Num2 = int(raw_input('Agrega otro número: '))
 
#Num1 = 20
#Num2 = 10
Aux1 = Num1
Aux2 = Num2
Rest = 1
mcd = 1
mcm = 1
 
while Aux2 != 0
    Rest = Aux1 % Aux2
    Aux1 = Aux2
    Aux2 = Rest
 
 mcd = Aux1
 mcm = Num1 * Num2 / mcd

De todas maneras hay que usar el for-in si es posible.

Saludo.

En teoría es así y no se deja. Mejor usar un for in ya que es el que se usa en estos ejercicios. Bueno, si quieres hacerlo funcionar con While, lo haremos, pero a mi no me sale y me  da error. Por algo será. Seguiré investigando porqué da ese error.

from fractions import gcd
a = int(raw_input("Numero 1: "))
b = int(raw_input("Numero 2: "))
print gcd(a, b)
 

http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Implementaci.C3.B3n_en_pseudoc.C3.B3digo

Si. En este caso es para los visitantes, no para mi. Guardo los ejercicios porque debo leer otra vez el PDF y así espero tener más soltura.