Valki be tudná bizonyítani nekem ezt b=aq+r (b, a) = (a, r) az egész számok halmazán?

b=aq + r

(a,r) | aq + r

tehat (a,r) | b

mivel (a,r) | a is

ezert (a,r) | (b,a)

b-aq = r

(b,a) | b-aq

ezert (b,a) | r

tehat

(b,a) | (a,r)

(a,r) | (b,a)

(b,a) | (a,r)

tehat

(b,a) = (a,r)

Latom mast nem erdekel ez a feladat, akkor leirom a masik megkozelitest:

Jelolje: t=(a,b)

valamilyen A,B egeszekre:

b=Bt,

a=At

es (A,B)=1

Bt = Atq + r

t(B-Aq) = r

vagyis t-vel oszthato r.

Mivel t-vel oszthato a is ezert t-vel oszthato (a,r) is.

jelolje k azt a szamot amire:

k*t = (a,r)

valamilyen, C,D egeszekre

a=Ckt

r=Dkt

b= Cktq+Dkt

b=kt(Cq + D)

vagyis kt - vel nem csak a oszthato, hanem b is.

viszont (a,b) =t tehat kt|t

tehat k = 1

(a,r) = t = (b,a)