Bestäm alla lösningar 7x konguent med 1(mod 2019)

Hej,

När du gör Euklides algoritm vill du göra faktorn så stor som möjligt så att resten blir mindre än $7$ här. Så i detta fall skulle det bli

$2019=7 \cdot 288+3$, sedan

$7 = 3 \cdot 2 + 1$, så $SGD(2019,7) = 1$.

Sedan Euklides algoritm baklänges för att hitta en lösning till den diofantiska ekvationen.

jan Maku skrev:

Hej,

När du gör Euklides algoritm vill du göra faktorn så stor som möjligt så att resten blir mindre än $7$ här. Så i detta fall skulle det bli

$2019=7 \cdot 288+3$, sedan

$7 = 3 \cdot 2 + 1$, så $SGD(2019,7) = 1$.

Sedan Euklides algoritm baklänges för att hitta en lösning till den diofantiska ekvationen.

Ah okej då är jag med. Men vad menar du med lösning till den diofantiska ekvationen baklänges?

Vi vill lösa diofantiska ekvationen $7x + 2019y = 1$.

Från sista raden i algoritmen har vi att

$1 = 7 - 2 \cdot 3$.

Och från andra raden har vi att $3 = 2019 - 288 \cdot 7.$ Om vi använder det får vi

$1 = 7 - 2 (2019 - 288 \cdot 7) = 7 + 576 \cdot 7 - 2 \cdot 2019 = 7 \cdot 577 + 2019 \cdot (-2).$

Så $x = 577$ och $y = -2$ är en lösning. Vi får den generella lösningen $x = 577 + 2019n$ och $y=-2 - 7n$. Nu är vi ju dock bara intresserade av $x$.

Detta är vad jag får. Dock har jag SGD(2019,7)=18

Euklides algoritm ser ut så här:

För att hitta $SGD(a,b)$,

$a = q_0 b + r_0$,

$b = q_1 r_0 + r_1$

$r_0 = q_2 r_2 + r_3$, osv.

Så i det här fallet ska det vara $7$ som hänger med till västerledet på rad 2 i stället för $288$.

jan Maku skrev:

Euklides algoritm ser ut så här:

För att hitta $SGD(a,b)$,

$a = q_0 b + r_0$,

$b = q_1 r_0 + r_1$

$r_0 = q_2 r_2 + r_3$, osv.

Så i det här fallet ska det vara $7$ som hänger med till västerledet på rad 2 i stället för $288$.

Så vad ska jag ha med ? 7 på alla eller ?

jan Maku skrev:

$2019=7 \cdot 288+3$, sedan

$7 = 3 \cdot 2 + 1$, så $SGD(2019,7) = 1$.

Så här som jag skrev tidigare. Skulle vi fortsätta en rad till så följer 3:an med till vänsterledet och det blir

$3 = 1 \cdot  3+ 0$. Så vi får redan på andra raden den sista nollskilda resten vilket är $1$. Alltså är $SGD(7,2019) = 1$.

jan Maku skrev:

jan Maku skrev:

$2019=7 \cdot 288+3$, sedan

$7 = 3 \cdot 2 + 1$, så $SGD(2019,7) = 1$.

Så här som jag skrev tidigare. Skulle vi fortsätta en rad till så följer 3:an med till vänsterledet och det blir

$3 = 1 \cdot  3+ 0$. Så vi får redan på andra raden den sista nollskilda resten vilket är $1$. Alltså är $SGD(7,2019) = 1$.

Okej jag förstår! Nu ska vi bestämma lösningar x och y.