Divisionsrest < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:24 Fr 22.04.2005 | | Autor: | Tinje |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Aufgabe lautet: Man löse in [mm] \IZ[/mm] :
(a)33x[mm] \equiv[/mm] 398(691)
(b)572x[mm] \equiv[/mm] 51(1309)
Ich weiß dass ich x finden muss (oder ein vielfaches) was bei der Division durch die Klammer der Rest ist. Also : (33*x)/ 691 = ... rest 398
Bei kleineren Zahlen wie 7 und 3 rest 1 ist es ja noch einfach..aber wie mache ich es bei so großen Zahlen ohne lange probieren zu müssen?
Danke für die Hilfe,
Tina
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:44 Fr 22.04.2005 | | Autor: | Julius |
Hallo Tina!
> (a)33x[mm] \equiv[/mm] 398(691)
Da $33$ und $691$ teilerfremd sind, findest du mit Hilfe des erweiterten Euklidischen Algorithmus ganze Zahlen $a$ und $b$ mit
$33 [mm] \cdot [/mm] a + 691 [mm] \cdot [/mm] b = 1$.
Nun multipliziert du diese Gleichung mit $398$:
$33 [mm] \cdot [/mm] (a [mm] \cdot [/mm] 398) + 691 [mm] \cdot [/mm] (b [mm] \cdot [/mm] 398) = 398$.
Nimmst du nun die Gleichung modulo $691$, so erhältst du:
$33 [mm] \cdot [/mm] (a [mm] \cdot [/mm] 398) [mm] \equiv [/mm] 398 [mm] \pmod{691}$,
[/mm]
und $x=a [mm] \cdot [/mm] 398$ ist eine Lösung.
Viele Grüße
Julius
|
|
|
|
