matematyka dyskretna NWD

macnadzieja · Post autor: **macnadzieja** » 27 lut 2005, o 11:20

Mam problem z pewnym zadaniem, należy udowodnic, że :

NWD(m*a,m*b)=m*NWD(a,b)

Arek · Post autor: **Arek** » 27 lut 2005, o 11:44

Właściwie to chyba jest jasne, no ale... hmmm... można skorzystać z definicji NWD wprost, czyli każdą z liczb: m, a, b rozłożyć na czynniki pierwsze i wtedy cała zabawa staje się znacznie przejrzystsza. Nie no, bo nie chciałbym po prostu dowodu podawać, ta podpowiedź powinna wystarczyć

macnadzieja · Post autor: **macnadzieja** » 27 lut 2005, o 12:47

tak, to jest jasne, ale musze to formalnie udowodnic

Lilav · Post autor: **Lilav** » 2 maja 2005, o 17:55

Mamy do udowodnienia, że NWD(am, bm) = m × NWD(a,b)

a wiec założmy ze:

k=NWD(a,b) k ε N

wtedy:

k | a i k | b

czyli:

k × x = a i k × y = b gdzie x,y ε N NWD(x, y) = 1

mnozymy obie strony rownania przez "m" i mamy:

kmx = a × m i kmy = b × m

wówczas:

NWD (am, bm) = k × m = NWD(a, b) × m
c.b.d.o

Chyba dobrze no nie ?