Matematik

KINESISKE RESTKLASSESÆTNING

04. december 2018 af diskretMat (Slettet) - Niveau: Universitet/Videregående

Hej alle sammen.

Jeg sidder med en opgave, og er egentlig på bar bund.

Jeg håber at der er nogle kloge hoveder som kan hjælpe med følgende opgave 4.6 (a og b), som er vedhæftet.

Det omhandler den kinisiske restklassesætning.

På forhånd tak.

Vedhæftet fil: afl4.pdf

Brugbart svar (1)

Svar #1
04. december 2018 af peter lind

Du må have ern anden version af den kinetiske restsætning end jeg har fordi metoden ikke kan bruges på b)

a) Sæt den inverse til 17 mod 101 til y1 og den inverse til 101 mod 17 til y2. Så er x = 2*101*y1 + 1*17*y2 mod 17*101 en løsning

b) metoden fra a) kan ikke bruges fordi de inverse ikke eksisterer

Svar #2
04. december 2018 af diskretMat (Slettet)

Hej igen.

jeg føler virkelig det er ret sort for mig, så når du siger den inverste til 17 og 101, hvad menes der så?

Og med hensyn til opgave b, så er det eneste jeg ved, det som står i "vink" nederst på siden :S
Tusinde tak for svar!

Brugbart svar (0)

Svar #3
04. december 2018 af peter lind

Det betyder at y1*17 ≡ 1 mod 101

Du må da have haft noget om den kinesiske restsætning for at du skulle løse sådan en opgave

Brugbart svar (0)

Svar #4
04. december 2018 af SådanDa

I b) kan du vel bruge at $x\equiv 7\mod 15$ er den entydige løsning (mod 15) til

$\left\{\begin{matrix} x\equiv 1\mod 3\\ x\equiv 2\mod 5 \end{matrix}\right.$ . per den kinesiske restklassesætning.

ligeledes er $x\equiv 14\mod 33$ den entydige løsning til

$\left\{\begin{matrix} x\equiv 2\mod 3\\ \ x\equiv 3\mod 11 \end{matrix}\right.$ .

Så din eventuelle løsning til ligningsystemet skal løse alle disse 4 ligninger, kan den det?

Brugbart svar (0)

Svar #5
04. december 2018 af peter lind

#4 Du har åbenbart også en anden beskrivelse af den kinesiske restsætning end jeg har, Hvad siger den ?

Brugbart svar (0)

Svar #6
04. december 2018 af SådanDa

#5 Jeg brugte denne her: http://people.math.aau.dk/~olav/dmge04/slilek5.pdf (side 2).

Men det er det samme som du beskriver i #1, man skal bruge den på systemet

$\left\{\begin{matrix} x\equiv 1\mod 3\\ x\equiv 2 \mod 5 \end{matrix}\right.$ , her kan du godt finde inverse, så du kan vise at x≡7 mod 15 løser ligningen. Jeg tror det er det hintet mener med at bruge sætningen "omvendt".

Brugbart svar (0)

Svar #7
04. december 2018 af Bibo53

a) Da $6\cdot 17+1=1\cdot 101+2=103$ , er $x=103$ en løsning til ligningssystemet. Da $\operatorname{sfd}(101,17)=1$ og $101\cdot 17=1717$ , er den fuldstændige løsning

$x=103+1717n,\quad n\in\Bbb{Z}$ .

b) Se https://www.studieportalen.dk/forums/thread.aspx?id=1865810

Svar #8
04. december 2018 af diskretMat (Slettet)

Hej igen alle sammen.

Tusinde tak fordi i gider bruge tid på at hjælpe mig!

Jeg har siddet og prøvet at løse det, men det er som om jeg går i stå når jeg prøver at finde y1. Jeg har benyttet Euklids algoritme.
Kan i se på billedet om jeg er på rette spor, eller om jeg er hel gal på den?

PS: Den aller øverste del af billedet, som viser opgavebeskrivelsen for opgave 4.6 b er en fejl, da det er opgave 4.6 a jeg er igang med lige nu.

Vedhæftet fil:Euklids algoritme.PNG

Brugbart svar (0)

Svar #9
04. december 2018 af Bibo53

Jeg tror ikke, du er på rette spor. Den inverse modulo 101 til 17 er 6, da

$6\cdot 17=102\equiv 1\pmod{101}$

Den inverse til 101 modulo 17 er 16, da

$16\cdot 101=1616\equiv 1\pmod{17}$

Svar #10
04. december 2018 af diskretMat (Slettet)

Hej igen.
Av, jeg er håbløs...
Ville det være muligt for dig at vise hvordan du kommer frem til de inverse, altså y1 og y2?
Jeg gør det åbenbart helt forkert..

Brugbart svar (0)

Svar #11
04. december 2018 af Bibo53

Noget er erfaring, men man kan komme langt med at prøve sig frem:

$1\cdot 101\equiv 16\pmod{17}$ , da $101=5\cdot 17+16$

$2\cdot 101\equiv 15\pmod{17}$

$3\cdot 101\equiv 14\pmod{17}$

osv. Har du læst #7?

Brugbart svar (0)

Svar #12
05. december 2018 af peter lind

Brugbart svar (0)

Svar #13
05. december 2018 af peter lind

#8 og #10

Du har bare lavet en fortegnsfejl fra næstsidste linje til sidste linje

17+101*(-1) +17*5 = 1 <=> 17(+6) -101 = 1

At skrive y1 =1/17 mod 101 og y1 =17^-1 mod 101 er noget vrøvl. Der må kun stå hele tal

Skriv et svar til: KINESISKE RESTKLASSESÆTNING

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.