Tu peux te servir du pgcd = Plus Grand Diviseur Commun
En posant p=pgcd(a,b)
a/b = (a/p)/(b/p) en fraction réduite
Pour calculer le PGCD, le plus simple est de le faire récursivement, sachant que pour tout couple d'entiers naturels (a,b), pgcd(a,b) = pgcd(b,a), pgcd(a,b) = pgcd(a-b,b) si a>=b et pgcd(0,b)=b (condition d'arrêt). Algo:
fonction pgcd(a, b : entier) : entier
debut
si a <= 0
retourne b
fsi
si a < b
echanger a et b
fsi
retourne pgcd(a-b, b)
fin pgcd
exemple pgcd(63,42) = pgcd(21,42) = pgcd(42,21) = pgcd(21,21) = pgcd(0,21) = 21