lineare Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bestimme jeweils alle Lösungen der folgenden linearen Kongruenzen, z. B. mittels Euklidischem Algorithmus und Rückwärtseinsetzen:
24x [mm] \equiv [/mm] 9 mod 135 |
Hallo,
ich lerne gerade und bin bei den linearen Kongruenzen hängen geblieben...
Also, ich bin so weit:
ggT (135, 24)= 3 (rausgefunden durch den Euklid, Algorith.)
Durch die Vielfachsummendarstellung habe ich raus:
3= 17*24 -3*135
Dann habe ich durch 3 geteilt: 8x [mm] \equiv [/mm] 3 mod 45
Hier ist der ggT (8, 45)=1 =17*8 -3*45 (Vielfachsummendarstellung)
bis dahin habe ich alles ja verstanden, aber wie geht es jetzt weiter? Kann mir da jemand helfen...
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:51 Do 23.07.2009 | | Autor: | abakus |
> Bestimme jeweils alle Lösungen der folgenden linearen
> Kongruenzen, z. B. mittels Euklidischem Algorithmus und
> Rückwärtseinsetzen:
> 24x [mm]\equiv[/mm] 9 mod 135
> Hallo,
> ich lerne gerade und bin bei den linearen Kongruenzen
> hängen geblieben...
> Also, ich bin so weit:
> ggT (135, 24)= 3 (rausgefunden durch den Euklid,
> Algorith.)
> Durch die Vielfachsummendarstellung habe ich raus:
> 3= 17*24 -3*135
> Dann habe ich durch 3 geteilt: 8x [mm]\equiv[/mm] 3 mod 45
> Hier ist der ggT (8, 45)=1 =17*8 -3*45
> (Vielfachsummendarstellung)
Hallo,
welches Vielfache von 8 lässt denn bei Teilung durch 45 den Rest 3?
Du musst doch einfach nur Zahlen der Form 45k+3 durchgehen und schauen, welche durch 8 teilbar sind.
Spätenstens nach 8 Versuchen wirst du fündig, weil bei Teilung durch 8 nur 8 verschiedene Reste (darunter eben auch der Rest 0) möglich sind und diese Reste sich regelmäßig wiederholen.
Bereits bei k=1 klappt es, denn 45*1+3=48 ist durch 8 teilbar.
Wegen 48=8*6 ist also eine erste Lösung x=6.
Gruß Abakus
>
> bis dahin habe ich alles ja verstanden, aber wie geht es
> jetzt weiter? Kann mir da jemand helfen...
> Danke
|
|
|
| |
|
Also, ich habe das als Lösung gegeben:
Aus der Darstellung des ggT(8,45) ergibt sich:
8^-1 mod 45=17 und damit x [mm] \equiv [/mm] 17* 3 [mm] \equiv [/mm] 6 (mod 45).
3. Lösungen: [6]_45 [mm] \equiv [/mm] [6]_135 [ [51]_135 [ [96]_135.
Deine Erklärung leuchtet mir ein, aber das verstehe ich nicht. Klar, es müssen drei Lösungen sein, weil ich am Anfang ggT=3 habe, und dann kann es nur eine sein, weil ich ggT=1 habe.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:13 Do 23.07.2009 | | Autor: | abakus |
> Also, ich habe das als Lösung gegeben:
>
> Aus der Darstellung des ggT(8,45) ergibt sich:
> 8^-1 mod 45=17 und damit x [mm]\equiv[/mm] 17* 3 [mm]\equiv[/mm] 6 (mod
> 45).
>
> 3. Lösungen: [6]_45 [mm]\equiv[/mm] [6]_135 [ [51]_135 [ [96]_135.
Was soll das denn jetzt?
Lösungen sind alle Zahlen x, für die [mm] x\equiv [/mm] 6 mod 45 gilt. Fertig.
Beispiele: ..., -39, 6, 51, 96, 141, ...
Es ist zwar richtig, dass auch Zahlen der Form [mm] x\equiv [/mm] 6 mod 135 Lösungen sind (z.B. ..., 6, 141,...) , das ist aber nur eine Teilmenge der bereits angegebenen Zahlen.
Gruß Abakus
>
> Deine Erklärung leuchtet mir ein, aber das verstehe ich
> nicht. Klar, es müssen drei Lösungen sein, weil ich am
> Anfang ggT=3 habe, und dann kann es nur eine sein, weil ich
> ggT=1 habe.
|
|
|
| |
|
Ok, danke. Nur um zu testen, ob ich es verstanden habe: Ich habe gegeben
15x [mm] \equiv [/mm] 3 mod 72
Der ggT= 3 und die Vielfachsummendarstellung ergibt 3= 15-1*2
Dann teile ich das durch 3:
5x [mm] \equiv [/mm] 1 mod 24
Dann muss ich eine Zahl finden, für die gilt: 24k+1 muss durch 5 teilbar sein.
Also: 24*1+1= 25 und 25/5= 5
Also ist die Lösung: [mm] [5]_{24}
[/mm]
ist das so richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:26 Do 23.07.2009 | | Autor: | abakus |
> Ok, danke. Nur um zu testen, ob ich es verstanden habe: Ich
> habe gegeben
> 15x [mm]\equiv[/mm] 3 mod 72
> Der ggT= 3 und die Vielfachsummendarstellung ergibt 3=
> 15-1*2
> Dann teile ich das durch 3:
> 5x [mm]\equiv[/mm] 1 mod 24
> Dann muss ich eine Zahl finden, für die gilt: 24k+1 muss
> durch 5 teilbar sein.
> Also: 24*1+1= 25 und 25/5= 5
> Also ist die Lösung: [mm][5]_{24}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
>
> ist das so richtig?
|
|
|
|
