Proof
(i) (a,b)=1 ⇒ ∃s,t(sa+tb=1)
The contraposition of (i) :
∀s,t(sa+tb=d≠1) ⇒(a,b)≠1 (i')
By ∀s,t(sa+tb=d≠1), we get a=b=d=0.
Therefore
(a,b)=0≠1.
Therefore (i') is true, so that (i) is also true.
(ii) ∃s,t(sa+tb=1) ⇒ (a,b)=1
The contraposition of (ii) :
(a,b)=d≠1 ⇒ ∀s,t(sa+tb≠1) (ii')
(a,b)=d≠1 ⇒ ∃a',b' in Z, a=da', b=db' and (a',b')=1.
Therefore
sa+tb=s(da')+t(db')=d(sa'+tb')≠1.
Therefore (ii') holds, so that (ii) is also true.
Q.E.D.
Write a comment