Потому что у вас неэффективный алгоритм вычисления НОД, работающий на вычитании, а не на делении с остатком.
Естественно, НОД(1,6) = НОД(1, 6−1=5) = НОД(1, 5−1=4) = НОД(1, 4−1=3) = НОД(1, 3−1=2) = НОД(1, 2−1=1) = НОД(1, 1−1=0) = 1
НОД(2,6) = НОД(2, 6−2=4) = НОД(2, 4−2=2) = НОД(2, 2−2=0) = 2
С арифметическим переполнением никак не связано. Просто даже в результате переполнения получились немаленькие числа.
Как надо: НОД(1,6) = НОД(6, 1%6=1) = НОД(1, 6%1=0) = 1
Аналогично для НОД(6,2) — в общем, сходится довольно быстро.