matematikk.net

Hei, jeg holder på med et bevis i diskret matematikk, det går som følger:
Bevis at for alle posivtive integere a, b, at a|b hvis og bare hvis gcd(a,b) = a.
Kan noen hjelpe meg med dette?

På forhånd takk!

Vi har implikasjonene

[tex]a \, \mid \, b \;\;\; \Rightarrow \;\;\; [/tex] b = ac for et naturlig tall c [tex]\;\;\; \Rightarrow \;\;\; [/tex]gcd(a,b) = gcd(a,ac) = a [tex]\cdot [/tex]gcd(1,c) = a [tex]\cdot [/tex]1 = a

og

gcd(a,b) = a [tex]\;\;\; \Rightarrow \;\;\; a \, \mid \, b.[/tex]

M.a.o. er

[tex]a \, \mid \, b \;\;\; \Leftrightarrow \;\;\; [/tex] gcd(a,b) = a.

Takk for svar

Ettersom jeg har forstått av definisjonen til gcd, vil vi ha at a|b og a|a når gcd(a,b) = a? Håper definisjonen holder som bevis i denne omgang!

Det du skriver, er korrekt. Generelt er det slik at hvis a og b er to heltall forskjellig fra 0, så er d=gcd(a,b) definert som det største heltallet som gjør at d|a og d|b.