(a,b)=1 ⇔ ∃s,t(sa+tb=1)

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

Comments: 0