Kongruensregning

Det er god trening å prate matematikk. Her er det fritt fram for alle. Obs: Ikke spør om hjelp til oppgaver i dette underforumet.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Bente75
Fibonacci
Fibonacci
Innlegg: 1
Registrert: 13/05-2018 22:25

Hei!
Eg held på med vidarerutdanning i matematikk og strevar med kongruensrekninga.
Det er greit når eg kan forkorte x til 1x, men når eg ikkje kan det så lurer eg på korleis eg skal gjere det.

to eksempel: 65x ~4 (mod 14) bruker dette ~som kongruenstegn
og
17x ~30 (mod 49)

helsing Bente (litt desperat)
Mattebruker

Oppgave 1: 65x kongruensteikn 4 (mod 14 ) ( dette betyr at ( 65x - 4) er eit multiplum av 14 )

Da kan vi skrive

65x - 4 = 14y

ekvivalensteikn

65x - 14y = 4 (diofantisk likning )

For å løyse denne likninga , må vi kunne skrive talet ( 1 ) som ein lineær kombinasjon
av koeffisientane 65 og 14. Da brukar vi Euklids algoritme:

65 = 4 * 14 + 9 som gir 9 = 65 - 4 * 14 , m element i Z

14 = 9 + 5 som gir 5 = 14 - 9

9 = 5 + 4 som gir 4 = 9 - 5

5 = 1 * 4 + 1 som gir 1 = 5 - 4

No kan vi " nøste oss tilbake" og får :

1 = 5 - 4 = 5 - (9 -5 ) = 2 * 5 - 9 = 2 * (14 - 9 ) - 9 = 2 * 14 - 3 * 9 = 2 * 14 - 3 (65 - 4 *1 4 ) = 14 * 14 - 3 * 65

Gå tilbake til " moderlikninga " , og får

65x - 14 y = 4 = 4 * ( 14 * 14 - 3 * 65 ) = 65 * ( -12 ) -14 * ( -56 )

Samanliknar V.S./H.S. og får x = -12 og y = -56

Allmenn løysing: x = -12 + 14m og y= -56 + 65m
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

evt

skriver kongruenslikninga som diofantisk likning:

[tex]17x\equiv 30 \pmod{49}\\ \\ 17x-30=49y\\ \\ ved \,\,inspeksjon\,\,sees\\ \\ 17*45=30+49*15\\ dvs\\ x\equiv 45 \pmod{49}\\ x=45+49y[/tex]
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Mattebruker

Janhaa skreiv: x = 45 + 49 y

Dette er ein heller tvilsam påstand.

Kongruenslikninga 17x trippelstrek30 ( mod 49 ) er ekvivalent med den diofantiske likninga

17x - 49y = 30 ( så langt er eg samd med Janhaa )

Når eg brukar Euklids algoritme på koeffisientane 17 og 49 , får eg at eininga

1 = 8 * 49 - 23 * 17

Da kan vi skrive

17x -49y = 30 = 30 * 1 = 30(8 * 49 - 23 * 17 ) = (-690)* 17 - 49 *( -240 ) , som gir

x = -690 og y = -240

Allmenn løysing: x = -690 + 49m pog y = -240 + 17m , m element i Z

Ut frå desse uttrykka kan eg vanskeleg sjå at vi får ein enkel samanheng mellom x og y ( x = 45 + 49y )
Mattebruker

Alternativt svar:

Vel m = 15 og får

x = -690 + 15 * 49 = 45 og y = -240 + 17 * 15 = 15

Innfører ny variabel s. Da kan vi skrive

x = 45 + 49s og y = 15 + 17s , s element i Z
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

Mattegjest skrev:Janhaa skreiv: x = 45 + 49 y

Dette er ein heller tvilsam påstand.

Kongruenslikninga 17x trippelstrek30 ( mod 49 ) er ekvivalent med den diofantiske likninga

17x - 49y = 30 ( så langt er eg samd med Janhaa )

Når eg brukar Euklids algoritme på koeffisientane 17 og 49 , får eg at eininga

1 = 8 * 49 - 23 * 17

Da kan vi skrive

17x -49y = 30 = 30 * 1 = 30(8 * 49 - 23 * 17 ) = (-690)* 17 - 49 *( -240 ) , som gir

x = -690 og y = -240

Allmenn løysing: x = -690 + 49m pog y = -240 + 17m , m element i Z

Ut frå desse uttrykka kan eg vanskeleg sjå at vi får ein enkel samanheng mellom x og y ( x = 45 + 49y )
Du kan nå bruke uttrykket for $x$ i svaret på den diofantiske likningen til å skrive $$x \equiv -690 \, \text{ mod }49$$ $$x \equiv 45 \, \text{ mod }49$$
Mattebruker

Her presenterer du korrekt svar(notasjon) i forhold til det opphavelege problemet(kongruenslikninga).

Det er vel gjerne slik Janhaa også har tenkt ( Svaret hans blir rett gitt at han brukar y som parameter, y element i Z)
Takk for tilbakemelding.
Mattebruker

Adg. oppgave 1:

x = -12 + 14m ekvivalensteikn x trippelstrek ( -12 ) ( mod 14 ) ekvivalensteikn

x trippelstrek(-12 + 14) (mod 14) ekvivalensteikn x trippelstrek 2 (mod 14 )
Svar