Алгоритм Евклида состоит в том, чтобы делить числа с остатком.
39 739 165 = 13 804 131 * 2 + 12 130 903
13 804 131 = 12 130 903 * 1 + 1 673 228
12 130 903 = 1 673 228 * 7 + 418 307
1 673 228 = 418 307 *4 + 0
Общий множитель
418 307. После сокращения получится
39 739 165 / 13 804 131 = (418 307*95) / (418 307*33) = 95 / 33