Hela algebra · 2021-12-06
Bestäm alla lösningar till den diofantiska ekvationen $15x+71y=7$.
Bestäm den minsta positiva heltalslösningen $x$ till $15x\equiv7\pmod{71}$.
Avgör, med noggrann motivering, för vilka heltal $a$ som kongruensen $15x\equiv a\pmod{71}$ har heltalslösningar $x$.
(a) Vi börjar med Euklides algoritm:
$$71=4\cdot14+11,\quad15=1\cdot11+4,\quad11=3\cdot4+3,\quad4=1\cdot3+1,\quad3=3\cdot1.$$
Så $\operatorname{SGD}(71,15)=1$ och vi kan lösa hjälpekvationen $71x+15y=1$ genom att köra Euklides algoritm baklänges:
$$1=4-3=4-(11-3\cdot4)=3\cdot4-11=3(15-11)-11=3\cdot15-4\cdot11=3\cdot15-4(71-4\cdot15)=19\cdot15-4\cdot71.$$
Vi får att $(x,y)=(19,-4)$ är en partikulärlösning till hjälpekvationen. Multipliceras denna med $7$ fås en partikulärlösning till vår ekvation, så den allmänna lösningen ges därmed av
$$x=133-71k,\qquad y=-28+15k,\qquad k\in\mathbb Z.$$
(b) Lösningarna $x$ till kongruensen är precis de som vi bestämt i (a), och vi får minsta möjliga positiva $x$ för $k=1$, vilket ger $x=62$.
(c) Att lösa kongruensen motsvarar att lösa den diofantiska ekvationen $15x+71y=a$, vilken är lösbar om och endast om $\operatorname{SGD}(15,71)=1$ delar $a$, dvs. för alla heltal $a$.