matematikk.net

Hvordan går man frem på en slik oppgave? 24x % 15 = 3. Jeg forstår ikke helt hvordan man skal kunne løse denne når det er modulo og Euklids algoritme inn i bildet... denne komboen virker ikke særlig enkel ut. Hvor starter man, og hva skal man egentlig gjøre her? Oppgaven ber meg finne en heltallsløsning.

euklimod wrote:Hvordan går man frem på en slik oppgave? 24x % 15 = 3. Jeg forstår ikke helt hvordan man skal kunne løse denne når det er modulo og Euklids algoritme inn i bildet... denne komboen virker ikke særlig enkel ut. Hvor starter man, og hva skal man egentlig gjøre her? Oppgaven ber meg finne en heltallsløsning.

For det første vet vi at $\text{sfd}(24,15) = 3 | 3$, så kongruensen er løsbar. Vi dividerer alle tall med største felles divisor og får kongruensen $8x = 1\text{ }\text{ (mod }5).$ Fra Euklids fulle algoritme (eller inspeksjon) har vi at $2\cdot 8 - 3\cdot 5 = 1$, hvilket forteller oss at $8\cdot 2 = 1 \text{ }\text{ (mod }5).$ Dermed får vi løsningen $x = 2 \text{ }\text{ (mod }5).$ (eller med din notasjon: $x$%$5 = 2$.)

euklimod wrote:Hvordan går man frem på en slik oppgave? 24x % 15 = 3. Jeg forstår ikke helt hvordan man skal kunne løse denne når det er modulo og Euklids algoritme inn i bildet... denne komboen virker ikke særlig enkel ut. Hvor starter man, og hva skal man egentlig gjøre her? Oppgaven ber meg finne en heltallsløsning.

mener du:

[tex]24x\equiv 3\pmod{15}\\ \\ 8x\equiv 1\pmod{5}\\ \\ x\equiv 2\pmod{5}[/tex]

deler på 3 fra 1. til 2.

fra 2 til 3:

8x = 1 + 5*3 = 16
x = 2

Hmm.. så man kan bare ta å dele alle tallene med GCDen uansett hva? Visste ikke at man bare kunne flytte rundt på %15 (mod 15) helt uten videre. Slik dere har gjort det så har dere flyttet den over til høyre siden - hvordan er reglene rundt dette?

trådstartern wrote:Hmm.. så man kan bare ta å dele alle tallene med GCDen uansett hva? Visste ikke at man bare kunne flytte rundt på %15 (mod 15) helt uten videre. Slik dere har gjort det så har dere flyttet den over til høyre siden - hvordan er reglene rundt dette?

Teknisk sett spurte jo oppgaven din kun etter én heltallsløsning. Da er det forsåvidt ikke nødvendig å dividere med gcd. Du kunne brukt Euklids algoritme direkte:
$$\begin{align*} 24 & = 15 + 9 \\ 15 & = 9 + 6 \\ 9 & = 6 + \textbf{3} \\ 6 & = 2\cdot 3,\end{align*}$$
og videre:
$$\begin{align*} 3 & = 9 - 6 \\ & = 9 - (15 - 9) \\ & = 2\cdot 9 - 15 \\ & = 2(24 - 15) - 15 \\ & = 2\cdot 24 - 3\cdot 15.\end{align*}$$
Dette forteller oss at alle tall $x$ som tilfredsstiller $24\cdot 2 = 3\text{ }\text{ (mod }15)$ vil være løsninger, så vi kan velge eksempelvis $x=2, x=17, x=32,$ osv.

Hvis du derimot er ute etter å finne alle heltallige løsninger må du dividere gjennom med gcd, ja, slik det er gjort i de tidligere svarene.

Det virker som ditt siste spørsmål dreier seg om notasjonen som er brukt. Her er det ikke noe fasitsvar, og du kan helt fint konvertere utregningene jeg har gjort til notasjonen du bruker selv (med % fremfor "mod").

Sliter fortsatt med å forstå hvordan dere gjør det. Eneste jeg kan tenke som gir noe logisk mening for meg, er dette:


Men da får jeg negativ x, og jeg vet ikke om dette er "lovlig" i det hele tatt i den matematiske verdenen Siden når man har funnet resten, så kan man vel bare fjerne %5 slik jeg har gjort det? Flytter jeg da 3 tallet over for å få x alene, blir det negativt svar.. x = -2 | dere får 2, noe som er riktig i henhold til fasiten.

.. men når jeg tenker over det, så er det * mellom 3 og x, så det hadde isåfall blitt 1/3. Huff.. klarer virkelig ikke å forstå disse greiene.

trådstarteroj wrote:Sliter fortsatt med å forstå hvordan dere gjør det. Eneste jeg kan tenke som gir noe logisk mening for meg, er dette:

Men da får jeg negativ x, og jeg vet ikke om dette er "lovlig" i det hele tatt i den matematiske verdenen Siden når man har funnet resten, så kan man vel bare fjerne %5 slik jeg har gjort det? Flytter jeg da 3 tallet over for å få x alene, blir det negativt svar.. x = -2 | dere får 2, noe som er riktig i henhold til fasiten.

.. men når jeg tenker over det, så er det * mellom 3 og x, så det hadde isåfall blitt 1/3. Huff.. klarer virkelig ikke å forstå disse greiene.

Du må lese i læreboken din hvilke regneregler som er gyldige i modulær aritmetikk, og hvordan en går frem for å løse kongruenser og diofantiske likninger. Det virker som ditt største problem er å forstå hvordan matematikken faktisk henger sammen, hvilke definisjoner som er i bruk og hvordan de skal anvendes. Hvis boken din ikke forklarer materialet tilstrekkelig, kan jeg anbefale deg å plukke opp en bok til faget Matematikk X for videregående skole. Selv brukte jeg Sinus X. Hvis du er varsom på å få med deg stoffet tydelig fra starten, så vil det sannsynligvis øke forståelsen din av dette temaet ganske kraftig.

Nå, til bildet du la ved:
Alt er riktig frem til punkt 3. Vi har nå kongruensen $$3x = 1 \text{ (mod 5)}.$$
Du kan nå ikke fjerne mod $5$. Videre skjønner jeg ikke hva du har gjort. For å løse kongruensen må du (enten via Euklids fulle algoritme eller ved inspeksjon) se at $$3\cdot 2 - 1\cdot 5=1,$$ så vi ser at $$3\cdot 2 = 1\text{ (mod }5).$$ Dermed er $x=2$ én spesifikk løsning til kongruensen, og følgelig er den generelle løsningen gitt ved $$x=2\text{ (mod }5).$$