Kongruenzrechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:28 Di 07.04.2009 | | Autor: | Cannae |
| Aufgabe | | 28x - 38 [mm] \equiv [/mm] 193 mod 35 |
Hallo,
ich bin am letzten Thema der kommenden Algebraklausur angelangt und verstehe leider garnichts.
Wie berechne ich die angegebene Formel??? Mir ist nichtmal wirklich klar wozu man die Kongruenzrechnung benötigt?
Ich bin für jede Hilfe dankbar.
Viele Grüße
Stefan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:12 Di 07.04.2009 | | Autor: | leduart |
Hallo
Du weisst schon, dass du nur mit den Resten zu 35 rechnen musst.
1. 193=18mod35
damit
28x-38=18mod35
28x=56 mod35
28x=21 mod 35
Edit: die naechste Zeile ist falsch. es wurde mit [mm] 7^{-1} [/mm] multipliziert, aber 7 hat kein Inverses. richtige Loesung siehe die posts von schachuzipus .
4x =7 mod35
jetzt das Inverse von 4 wissen oder suchen also [mm] 4*4^{-1}=1
[/mm]
un eigentlich weiss man 4*9=36=1mod 35
also die gl mit 9 mult.
4*9*x=63 mod35
1*x= 28 mod 35
(Nicht immer findet man das Inverse so leicht)
andere Moeglichkeit waere gewesen direkt das Inverse von 28 zu suchen. Das war mir zu langwierig.
Wenn du mod einer Nicht primzahl rechnest gibt es nicht unbedingt ein mult. Inv.
Gruss leduart.
|
|
|
| |
|
Hi leduart,
> Hallo
> Du weisst schon, dass du nur mit den Resten zu 35 rechnen
> musst.
> 1. 193=18mod35
> damit
> 28x-38=18mod35
> 28x=56 mod35
> 28x=21 mod 35
> 4x =7 mod35 ![[notok]](/images/smileys/notok.gif "[notok]")
Hier musst du [mm] $\mod\left(\frac{35}{ggT(28,35)}=5\right)$ [/mm] nehmen!
> jetzt das Inverse von 4 wissen oder suchen also
> [mm]4*4^{-1}=1[/mm]
> un eigentlich weiss man 4*9=36=1mod 35
> also die gl mit 9 mult.
> 4*9*x=63 mod35
> 1*x= 28 mod 35
> (Nicht immer findet man das Inverse so leicht)
> andere Moeglichkeit waere gewesen direkt das Inverse von
> 28 zu suchen. Das war mir zu langwierig.
> Wenn du mod einer Nicht primzahl rechnest gibt es nicht
> unbedingt ein mult. Inv.
> Gruss leduart.
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:14 Di 07.04.2009 | | Autor: | felixf |
Hallo Stefan
> Mir ist nichtmal wirklich klar wozu man die Kongruenzrechnung benötigt?
Dazu eine Gegenfrage: hast du schonmal mit Uhrzeigen gerechnet (a la 23 Uhr plus 2 Stunden ist 1 Uhr)? Hast du schonmal etwas im Internet eingekauft? Hast du schonmal Onlinebanking gemacht? Hast du einen neuen biometrischen Reisepass?
Die vier Fragen haben alle eine Gemeinsamkeit: ohne Kongruenzrechnung muesstest du jeweils nein sagen, weil es das alles nicht geben wuerde.
LG Felix
|
|
|
| |
|
Hallo Stefan,
irgendetwas scheint mir an leduarts Lösung faul zu sein, x=28 ist keine Lösung der Kongruenz
> 28x - 38 [mm]\equiv[/mm] 193 mod 35
> Hallo,
>
> ich bin am letzten Thema der kommenden Algebraklausur
> angelangt und verstehe leider garnichts.
>
> Wie berechne ich die angegebene Formel???
Erstmal die -38 rüberschaffen:
[mm] $28x\equiv [/mm] 231 \ [mm] \mod [/mm] 35$
Dann ist [mm] $231=6\cdot{}35+21$, [/mm] also [mm] $231\equiv [/mm] 21 \ [mm] \mod [/mm] 35$
Also [mm] $28x\equiv [/mm] 21 \ [mm] \mod [/mm] 35$
Es ist $ggT(28,35)=7$ und [mm] $7\mid [/mm] 21$, also ist die Kongruenz lösbar und es gibt 7 modulo 35 inkongruente Lösungen der Kongruenz
Es ist [mm] 35=5\cdot{}7
[/mm]
Es ergeben sich also die Kongruenzen [mm] $28x\equiv [/mm] 21 \ [mm] \mod [/mm] 5$ und [mm] $28x\equiv [/mm] 21 \ [mm] \mod [/mm] 7$
Die wieder reduzieren jeweils mod5,7
gibt: [mm] $3x\equiv [/mm] 1 \ [mm] \mod [/mm] 5$ und [mm] $3x\equiv [/mm] 1 \ [mm] \mod [/mm] 7$
Die Inversen von $3$ modulo 5 bzw. 7 sind 2 bzw. 5 (wieso?)
Also ergibt sich
[mm] $x\equiv [/mm] 2 \ [mm] \mod [/mm] 5$
[mm] $x\equiv [/mm] 5 \ [mm] \mod [/mm] 7$
Mit dem chines. Restsatz kommst du auf [mm] $x\equiv [/mm] 12 \ mod 35$
Die Lösungen sind also [mm] $x=12+k\cdot{}5$, [/mm] $k=0,1,...,6$ (modulo 35)
Die 5 erklärt sich durch [mm] $\frac{35}{ggT(28,35)}=\frac{35}{7}=5$
[/mm]
(schaue dir mal den Beweis zur Lösbarkeit linearer Kongruenzen an, dort steht was zur Lösungsstruktur!)
> Mir ist nichtmal wirklich klar wozu man die Kongruenzrechnung benötigt?
Naja, damit kann man bequem rechnen, (fast) wie mit Gleichungen, viele Teilbarkeitsaussagen lassen sich schneller und eleganter beweisen ...
>
> Ich bin für jede Hilfe dankbar.
>
> Viele Grüße
>
> Stefan
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:02 Mi 08.04.2009 | | Autor: | Cannae |
Vielen Dank für die Antworten. Ich habe noch 1 1/2 Wochen Zeit das zu verstehen was ihr mir geschrieben habt. Mal schauen wie ich den morgigen Tag damit überstehe 
|
|
|
|
![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]"){kind=small}
.
![[pfeif]](/images/smileys/pfeif.gif "[pfeif]"){kind=small}
![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]"){kind=small}
