Diofantiske likninger - euklidsalgoritme - kan du hjelpe? :)

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

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

Svar
mokki

Hei!
Jeg har problemer med å forstå diofantiske likninger, og euklids algoritme. Er det noen som kan hjelpe meg?

Eksempel:
3x + 4y = 17 (jeg forstår hvordan jeg setter den opp)

1. Kan den løses? Ja, sff er 1. Finner ut dette ved å primtallfaktorisere.

2. Euklids algoritme:

3x + 4y = 1 (her har jeg notert meg at denne alltid er 1, men kommer det an på hva som er sff?)

3 = 0 x 4 + 3
4 = 1 x 3 + 1 (1 er stoppsignal... hva om det går opp, slik at det blir 0?)

1 = 1 x 4 - 1 x 3

Y* er da: 1
X* er: -1

I akkurat dette eksempelet henger jeg med på dette.

3. Spesiell løsning:
Gange med 17: Yo = 1 x 17 = 17 og Xo = -1 x 17 = -17 (dette er også greit)

4. Generell løsning:
Xn = -17 + 4 x n
Yn = 17 - 3 x n
(henger fortsatt med).

5. krever positive tall:
-17 + 4n = 0
4n = 17:4
n = 4,25... runder alltid opp, så da blir det 5.

Da skjønner jeg at 5 er det tallet man starter på i tabellen, men tilsvarer det også origo i koordinatsystemet?)

6. Lage tabell:
n - 5 - 6
x - 3 - 7
y - 2 - -1

Dette er greit, forstår at man må se på den generelle løsningen og fylle inn n


MEN, hva hvis jeg har likningen: 24x + 10y = 4

Starter med å primtallfaktorisere, og finner ut at sff må være 2, skriver derfor likningen slik med euklids algoritme:
24x + 10y = 2 (???)

Fortsetter med:
24 = 2 x 10 + 4 (hvor mange ganger det minste tallet går opp i det første, 4 i rest)
10 = 2 x 4 + 2 (hvor mange ganger 4 (resten) går opp i 10)
4 = 2 x 2 + 0 (hvor mange ganger resten 2 går opp i 4)

Her ender jeg altså med 0. Men skal ikke denne alltid være 1? Og dessuten trodde jeg at dette tallet skulle være sff, men det er jo 2!)

Og nå som jeg har så mange tall og forholde meg til så skjønner jeg ikke hvordan jeg fortsetter... dette er hva jeg har prøvd:

En måte jeg har prøvd
0 = 4 - 2 x 2
2 = 10 - 2 x 4
4 = 24 - 2 x 10
(tatt utgangspunkt i restene og sokket om. Men aner ikke grunnen)

2 (sff) = 4 - 2 x (10 - 2 x 4) x (24 - 2 x 10)
2 = 4 - 2 x (10 - 8) x (24 - 20)
2 = 4 - 2 x 2 x 4
2 = ?????? Her skjønner jeg over hode ingen ting.

Eller blir det slik? en anne måte jeg har prøvd:
2 = 2(sff) x 10 - 2 (sff) x 24
og siden jeg vet at 10 er y og 24 er x, så blir det: Y* = 2 og X* = -2

For deretter å gå løs på spesiell løsning (gange med svaret på likninga som var 4):
Yo = 2 x 4 = 8
Xo = -2 x 4 = -8

Generell lösning blir da muligens:
Xn = - 8 + 10 (y`n) x n
Yn = 8 - 24 (x`n) x n

Og siden det krever positive tall:
-8 + 10n = 0
10n = 8
n = 8:10 ...... og det er da ikke positivt i alle fall, men kanskje tabellen starter på minus?

Hjeeeeeelp!! :? Eksamen om to uker, og jeg klarer virkelig ikke å forstå logikken i hvordan jeg skal gå frem og hvorfor jeg gjør som jeg gjør
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

24 = 2 x 10 + 4 (hvor mange ganger det minste tallet går opp i det første, 4 i rest)
10 = 2 x 4 + 2 (hvor mange ganger 4 (resten) går opp i 10)
4 = 2 x 2 + 0 (
gcd(24, 10) =2

siste linja di, etter likhetstegnet
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

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