Uppgift 6
(a)
Definiera begreppet största gemensamma delare.
(b)
Visa att om $\SGD(a,b)=1$ så kan $\SGD(6a,b)$ bara anta värdena $1,2,3$ eller $6$.
Satser från kursen får användas. Ledtråd: Börja med att förstå varför $\SGD(6a,b)$ inte kan vara 5.
Diskret matematik · 2024-03-07
Uppgift 6
Visa lösningDölj lösning
- Den största gemensamma delaren av två tal $a$ och $b$, är det största positiva heltal $d$ för vilket det gäller att $d \mid a$ och $d\mid b$.
- Låt $d = \SGD(6a,b).$ Antag att $p^k$ är en primtalspotens som delar $d$, för något $k\geq 1$. Då måste $p^k \mid 6a$ och $p^k \mid b$. Om $p \mid a$, skulle $p$ vara gemensam delare till $a$ och $b$. Alltså måste $p^k \mid 6$. Då måste $p^k$ antingen vara $2$ eller $3$. Detta innebär att $d$ som mest kan delas av $2$ och $3$ och vi får värdena ovan.
Alternativt, låt $a= p_1 p_2 \dotsc p_k$ och $b= q_1 q_2 \dotsc q_\ell$ vara primtalsfaktoriseringarna av $a$ och $b$ (samma primtal kan finnas med flera gånger i vardera lista). Eftersom $\SGD(a,b)=1$ så har de två produkterna ingen gemensam primtalsfaktor. Nu tittar vi på \[ \SGD(6a,b) = \SGD(2\cdot 3 \cdot p_1 p_2 \dotsc p_k, q_1 q_2 \dotsc q_\ell). \] Den enda skillnaden nu är om något/några av primtalsfaktorerna i $b$ är lika med $2$ eller $3$. I så fall blir största gemensamma delaren $2$, $3$ eller $6$.