3.1 $$321=123\times 2+75\quad 123=321\times 0+123\times 1$$ $$123=75\times 1+48\quad 75=321\times 1-123\times 2$$ $$75=48\times 1+27\quad 48=-321\times 1+123\times 3$$ $$48=27\times 1+21\quad 27=321\times 2-123\times 5$$ $$27=21\times 1+6\quad 21=-321\times 3+123\times 8$$ $$21=6\times 3+3\quad 6= 321\times 5-123\times 13$$ $$6=3\times 2\quad 3=-321\times 18+123\times 47$$

3.2 Suppose their gcd is \(d>1\). (And \(d<p\).) Then \(d\) divides \(a+b=p\), a contradiction.

3.3 (a) \(\gcd(a_1,\ldots,a_n)=\gcd(\cdots\gcd(\gcd(a_1,a_2),a_3)\ldots,a_n)\). By definition, it exists. By induction, there exist \(b_1,\ldots,b_n\) such that \(\gcd(a_1,\ldots,a_n)=b_1a_1+\cdots+b_na_n\).

(b) All common prime factors have been taken out, so they are relatively prime, that is, their gcd is \(1\).