a,bの最大公約数をrとすると、a,bがともにｒの倍数3a+7b,4a+9bはrの倍数
3a+7b=p=kr
4a+9b=q=lrとおく。
a=7q-9p=(7l-9k)r
b=4p-3q=(4k-3q)r
となるのでｋとｌが1でない公約数をもつとすると7l-9kと4k-3qも1でない公約数をもつことになり
aとｂの最大公約数がrであることに矛盾する。よってｋとｌは互いに素。→pとqの最大公約数はr