Kongruens räkning, euklides algoritm

Hej!

Har problem med att få till följande ekvation

84x *= 2(mod 5)
(*= symboliserar kongruenstecknet som jag inte kan få till på den här datorn)

Man ska tydligen kunna lösa den med euklides algoritm, då man får en diofantisk ekvation som jag antar ser ut så här:

84x - 5y = 2, så det jag egentligen undrar är hur jag löser den? Får inte till det på något sätt.. Help me out plzzz!!

Du behöver inte tolka den som en diofantisk ekvation direkt, men du kan om du vill.

Ekvationen:

84x ≡ 2 (mod 5)

Först måste vi klargöra vad vi vill göra med en ekvation. Syftet med en ekvation är att ta reda på vad ett enda x är lika med, eller i detta fallet då kongruent med. Vi vill alltså inte veta vad 84x är utan vad ett enda x är, då måste vi hitta en metod för att få bort 84.

Om vi hade haft ett vanligt likhetstecken så hade vi löst denna genom att dividera med 84 på båda sidor, dvs finna den multiplikativa inversen till 84, för att koefficienten framför x skall bli 1 (det är det division är, omvänd multiplikation så att säga). Vi gör på samma sätt med denna ekvationen, först måste vi bara ta reda på vad den multiplikativa inversen till 84 modulo 5 är, och det är hela historien egentligen. För en vanlig ekvation med ett vanligt likhetstecken vet vi att 1/84 är den multiplikativa inversen till 84, eftersom (1/84)*84 = 1. Men i världen om modulo 5 så vet vi inte än vad den multiplikativa inversen till 84 är. Ett riktigt bra sätt att ta reda på den multiplikativa inversen till 84 modulo 5 är då att använda euklides algoritm (EA) för att räkna med den största gemensamma delaren.

Beräkna SGD(84,5):

84 = 5*16+4
5 = 4*1+1

Detta visar då att den största gemensamma delaren är 1, då vet vi definitivt att en multiplikativ invers finns. Å andra sidan så vet vi redan direkt att en multiplikativ invers finns eftersom 5 är ett primtal och 84 är inte delbart med 5.

Nu skall vi räkna EA "baklänges", dvs att vi kan uttrycka 84 och 5 som en linjärkombination i likhet med 1.

Titta på nedersta raden av SGD, dvs 5 = 4*1+1, vi kan skriva om detta

5 = 4*1+1
5-4*1 = 1

Och kolla på den allra första raden, där återfinner vi en fyra.

84 = 5*16+4
84-5*16 = 4

Då kan vi skriva allt som:

5-4*1 = 1
5-(84-5*16) = 1
5-84+5*16 = 1
-84+5*17 = 1 [eftersom vi hade 17 stycken femmor]

Ur detta vet vi att vi att den multiplikativa inversen till 84 modulo 5 är -1, eftersom koefficienten framför 84 är lika med -1. Om vi då multiplicerar med -1 på båda sidor i vår kongruensekvation så är koefficienten framför x lika med 1.

Illustrerar exemplet:

84x ≡ 2 (mod 5) ⇔
-1*84x ≡ -1*2 (mod 5) ⇔
-84x ≡ -2 (mod 5) ⇔

Vi vet att -84 är kongruent med 1 modulo 5, så då är vi klara!

x ≡ -2 (mod 5) ⇔
x ≡ 3 (mod 5)

Mvh

Du kan använda ~ i stället. Det används ofta för ekvivalensrelationer.


Vi börjar med att lösa 84 x0 - 5 y0 = 1 genom Euklides algoritm (resterna fetmarkerade):
84 = 16 * 5 + 4
5 = 1 * 4 + 1

Alltså: 1 = 5 - 1 * 4 = 5 - 1 * (84 - 16 * 5)
= 17 * 5 - 1 * 84.

Med x0 = -1 och y0 = 17 får vi alltså en lösning till 84 x0 - 5 y0 = 1.

Den generella lösningen får vi genom att sätta x0 = -1 + 5 n och y0 = 17 + 84 n.

Sätt nu x = 2 x0 = 10 n - 2 och y = 2 y0 = 168 n + 34. Vi får då
84 x - 5 y = 84 (10 n - 2) - 5 (168 n + 34) = (840 n - 168) - (840 n + 170) = 2,
dvs dessa x och y ger lösningar till ekvationen.

Tjohej, använder min gamla tråd för håller på att repetera samma ämne.

Jag ska lösa följande system av kongruenser:

x ~ 2 (mod6)
x ~ 5 (mod7)
x ~ 7 (mod15)

med hjälp av Kinesiska restsatsen. Utgångsstrategin är då, om jag fattat saker och ting rätt, att multiplicera enligt följande mönster:

7*15*x ~ 2 (mod6)
6*15*x ~ 5 (mod7)
6*7*x ~ 7 (mod15)

Sen börjar man lösa var kongruens för sig och gör en slutkläm för att få en specifik lösning till hela systemet(är det den enda lösning btw?)

Hur som helst, i just det här systemet så är SGD(7*15, 6) =/= 1 därför saknar den lösningar. Så bör man redan där dra slutsatsen att systemet är olösbart, eller kan man ändra sin utgångsstrategi på något sätt för att lösa det? Tack på förhand!

Om du redan vet att systemet saknar lösningar så kan man förstås dra slutsatsen att systemet är olösbart, och då är det ju ganska meningslöst att hitta en annan strategi att lösa det.

Däremot så vet jag inte vart du får det fetmarkerade från. T.ex. gäller för systemet

x ≡ 0 (mod 2)
x ≡ 0 (mod 4)

att SGD(2, 4) ≠ 1. Ändå har systemet uppenbart lösningar.

Så du behöver nog komma på ett bättre resonemang än så för varför systemet saknar lösningar. (Hint: Vad är x (mod 3)?)

Woops, det gällde tydligen bara kongruenser på formen a*x ≡ 1(mod b)

Alright, för att kunna använda Kinesiska restsatsen på ett system

x ≡ a(mod n_1)
x ≡ b(mod n_2)
x ≡ c(mod n_3)

Så måste ju iofs n_1, n_2, n_3 var parvis relativt prima vilket dom inte är i det här fallet. Fast att dra slutsatsen att systemet är olösbart bara för att jag inte kan använda min algoritm känns lite vågat, eller är det?

Annars kanske jag kan använda 7*15*x ~ 2 (mod6) som ger den diofantiska ekvationen
105x - 6y = 2
och utnyttja satsen "Om SGD(a, b) inte delar c i ekvationen ax + by = c så har ekvationen inga lösningar" då SGD(105, -6) = 3. Låter det bra?

Fast hur tusan fick du detta?

Haha det fick jag i och för sig från kinesiska restsatsen, där man ansätter
x = b_1*m_2*m_3*...*m_r + b_2*m_1*m_3*...*m_r + ... + m_1*m_2*m_3*...*b_r

där m:ena kommer ifrån systemets mod(m_i), som bygger på att m_i och m_j är parvis relativt prima för alla i:n och j:n vilket dom inte är(15 och 6), så det kanske bara var felfelfel..

Så räcker det med att säga att ett system,

x ≡ a_1 (mod m_1)
x ≡ a_2 (mod m_2)
...
x≡ a_k (mod m_k)

där m_1, m_2, ... , m_k inte är parvis relativt prima, saknar lösning?

Ja, det där känns lite fel, ja.


Nej, det räcker inte, eftersom det som du då säger inte är sant (och jag har redan presenterat ett motexempel.)

Titta istället på hinten jag skrev i inlägg #5.

Aaaasch va idiotiskt... Jag har faktiskt ingen aning om hur jag ska använda mig av din hint
x(mod 3), vad menas med det egentligen?

Alltså, antag att x löser kongruenssystemet. Vad måste då resten av x vid division med 3 vara?

Det borde väl bli något jag kan få fram utifrån dom här kongruenserna
x ~ 2 (mod6)
------------
x ~ 7 (mod15)

då 6=3*2 och 15 = 5*3.

Så när jag delar x med 6 får jag samma rest som när jag delar 2 med 6
Och när jag delar x med 15 så får jag samma rest som när jag delar 7 med 15.
På rätt spår? Sedan komma fram till någon motsägelse att ett sådant x inte existerar(förutsatt att systemet nu inte är lösbart, oh boy om det visar sig vara fel)