# Divisions euclidiennes successives
# Thomas George 2007

puts 'Divisions euclidiennes successives de deux nombres:'

puts 'Premier: '
n1 = gets.to_i
puts 'Second: '
n2 = gets.to_i
# Copie, pour la fin
m1 = n1; m2 = n2

# On les classe dans l'ordre
if n1 < n2
	n3 = n1; n1 = n2; n2 = n3
end

# Algorithme d'Euclide
while n2 != 0
	ancien_reste = n2
	reste = n1 % n2
	div = (n1 - reste) / n2
	puts "#{n1} = #{n2} x #{div} + #{reste}"
	n1 = n2
	n2 = reste
end

puts "Le PGCD de " + m1.to_s + " et " + m2.to_s + " est " + ancien_reste.to_s + "."
if ancien_reste != 1
	puts "Ces nombres ne sont donc pas premiers entre eux."
else
	puts "Ces nombres sont donc premiers entre eux."
end