Kongruenslikning

Hei. Jeg leser Matematikk 3mz. Jeg står bom fast på dette! I en oppgave skal vi gjøre om en kongruensligning til diofantisk ligning. $7x=10(\mathrm{mod}29)$.

Hvordan gjøres det? Finnes det en generell formel for å utføre det?. Kan man for eksempel omforme en diofantisk ligning til en kongruensligning? På forhånd takk!

$7x=10(\mathrm{mod}29)$ betyr at $7x-10=29k$ for en eller annen (heltallig) $k$, dvs. at $7x-10$ er delelig med 29. Den lineære diofantiske likningen får vi ved å sette $y=-k$, og den er $7x+29y=10$.

Men til ditt siste spørsmål: $x$ og $y$ kan bytte rolle: $29y=10(\mathrm{mod}7)$ er en annen kongruenslikning med samme diofantiske lineære likning. For å løse den må du observere at 7 og 29 er primtall, og derfor ikke har noen felles divisor større enn 1. $7x+29y=1$ kan vi derfor finne løsninger av ved Euklids algoritme (dele 29 på 7, om resten ikke er 1 fortsette å dele 7 på den, og så videre).

$29=4\cdot 7+1$, så vi trenger ikke fortsette! Altså er $1\cdot 29-4\cdot 7=1$, og om vi ganger med 10 på begge sider får vi:

$10\cdot 29-40\cdot 7=10$

Nå har vi løst likningen din, men vi vil pynte litt på den. Vi kan legge til og trekke fra $29\cdot 7\cdot k$:

$(10-7k)\cdot 29+(-40+29k)\cdot 7=10$

Løsningene er derfor $x=-40(\mathrm{mod}29)$, og $k=2$ gir den første positive løsningen for $x$: $-4\cdot 29+18\cdot 7=10$. Likningene av $7x=10(\mathrm{mod}29)$ er derfor $x=18(\mathrm{mod}29)$.