Uppgift 6
(a)
För $a,b\in\mathbb{Z}\setminus\{0\}$, ange definitionen av $\operatorname{SGD}(a,b)$.
(b)
Låt $a,b\in\mathbb{Z}\setminus\{0\}$, och låt $d=\operatorname{SGD}(a,b)$. Bevisa att $\operatorname{SGD}(a/d,b/d)=1$.
Diskret matematik · 2023-11-22
Uppgift 6
Visa lösningDölj lösning
(a) För $(a,b)\ne(0,0)$ definierar vi $\operatorname{SGD}(a,b)$ som det största heltal $d$ som delar både $a$ och $b$. Vi definierar också $\operatorname{SGD}(0,0)=0$.
(b) Låt $c=\operatorname{SGD}(a/d,b/d)$. Per definition gäller då att $c\mid a/d$ och $c\mid b/d$. Alltså finns heltal $m,n$ sådana att
$$
mc=\frac ad,\qquad nc=\frac bd.
$$
Detta är ekvivalent med
$$
mcd=a,\qquad ncd=b.
$$
Alltså är $cd$ en delare till både $a$ och $b$. Men $d$ är den största gemensamma delaren, och därför måste $c\le1$. Eftersom $c$ är positivt följer $c=1$, vilket var det som skulle visas.