Kongruenz zerlegen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
wie zerlege ich eigentlich eine lineare Kongruenz folgender Form:
[mm] 7x\equiv [/mm] c mod 15
in seine Primfaktoren,also so, dass ich ein dazu äquivalentes System der Form:
[mm] x\equiv [/mm] ___ mod 3
[mm] x\equiv [/mm] ___ mod 5
erhalte.
Wie Forme ich [mm] 7x\equiv [/mm] c mod 15 überhaupt um, so dass x links alleine steht ? Ich weiß nur wie es geht, wenn c einen bestimmten Wert annimmt und da muss man ja auch bisschen rumprobieren (ein Vielfaches von 15 auf c addieren und durch 7 teilen).
vielen Dank und
Viele liebe Grüße
|
|
| |
|
Hallo imagemixer,
> Hallo,
> wie zerlege ich eigentlich eine lineare Kongruenz
> folgender Form:
> [mm]7x\equiv[/mm] c mod 15
> in seine Primfaktoren,also so, dass ich ein dazu
> äquivalentes System der Form:
>
> [mm]x\equiv[/mm] ___ mod 3
> [mm]x\equiv[/mm] ___ mod 5
> erhalte.
> Wie Forme ich [mm]7x\equiv[/mm] c mod 15 überhaupt um, so dass x
> links alleine steht ? Ich weiß nur wie es geht, wenn c
Berechne das multiplikativ Inverse von 7 modulo 15.
Das wird mit dem ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus gemacht.
Dann kannst Du die Kongruenz mit diesem Inversen duchmultiplizieren.
> einen bestimmten Wert annimmt und da muss man ja auch
> bisschen rumprobieren (ein Vielfaches von 15 auf c addieren
> und durch 7 teilen).
>
> vielen Dank und
> Viele liebe Grüße
Gruss
MathePower
|
|
|
| |
|
Danke, aber bin mir noch nicht sicher:
Ist das multiplikativ Inverse von 7 modulo 15 etwa
=-2mod15 sprich 13?
Folgt dann [mm] x\equiv13c [/mm] mod 15 ?
|
|
|
| |
|
Hallo imagemixer,
> Danke, aber bin mir noch nicht sicher:
> Ist das multiplikativ Inverse von 7 modulo 15 etwa
> =-2mod15 sprich 13?
So ist es.
> Folgt dann [mm]x\equiv13c[/mm] mod 15 ?
Auch das ist richtig.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:57 So 24.06.2012 | | Autor: | imagemixer |
Vielen Dank an beide Helfer.
Nur mal nebenbei:
gibt es in dem Fall:
[mm] 15x\equiv25mod35
[/mm]
kein inverses Element (die sind ja auch nicht teilerfremd)? Falls doch, habe ich es immer noch nicht verstanden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:14 So 24.06.2012 | | Autor: | abakus |
> Vielen Dank an beide Helfer.
>
> Nur mal nebenbei:
> gibt es in dem Fall:
> [mm]15x\equiv25mod35[/mm]
> kein inverses Element ? Falls doch, habe ich es immer noch
> nicht verstanden.
>
Hallo,
hier kannst du beide Seiten durch 5 teilen, wodurch sich eventuell ein anderes Modul ergibt.
Der ggT von 35 und 5 ist 5, wodurch sich
[mm]3x\equiv5mod\bruch{35}{5}[/mm]
ergibt, also [mm]3x\equiv5mod7[/mm].
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 So 24.06.2012 | | Autor: | imagemixer |
Durch ggT teilen lässt die Gleichung äquivalent zu der vorigen sein oder? Also sind die beiden Kongruenzen äquivalent, auch wenn das eine mod35 das andere mod7 ist.
|
|
|
| |
|
Vielen vielen Dank, ein Teil habe ich gut verstanden.
Wie das geht, ist mir aber noch unklar:
> wie zerlege ich eigentlich eine lineare Kongruenz
> folgender Form:
> $ [mm] x\equiv [/mm] $ 13c mod 15
> in seine Primfaktoren,also so, dass ich ein dazu
> äquivalentes System der Form:
>
> $ [mm] x\equiv [/mm] $ ___ mod 3
> $ [mm] x\equiv [/mm] $ ___ mod 5
> erhalte.
|
|
|
| |
|
Hallo imagemixer,
das ist einfach.
> Vielen vielen Dank, ein Teil habe ich gut verstanden.
> Wie das geht, ist mir aber noch unklar:
> > wie zerlege ich eigentlich eine lineare Kongruenz
> > folgender Form:
> > [mm]x\equiv[/mm] 13c mod 15
> > in seine Primfaktoren,also so, dass ich ein dazu
> > äquivalentes System der Form:
> >
> > [mm]x\equiv[/mm] ___ mod 3
> > [mm]x\equiv[/mm] ___ mod 5
> > erhalte.
[mm] x\equiv 13c\mod{15}\quad\Rightarrow\quad x\equiv 13c\mod{3}\quad\Rightarrow\quad x\equiv c\mod{3}
[/mm]
[mm] x\equiv 13c\mod{15}\quad\Rightarrow\quad x\equiv 13c\mod{5} \quad\Rightarrow\quad x\equiv 3c\mod{5}
[/mm]
Deutlicher ist das vielleicht sogar, bevor Du die 13 als Inverses zu 7 [mm] \mod{15} [/mm] gefunden hast:
[mm] 7x\equiv c\mod{15}\quad\Rightarrow\quad 7x\equiv c\mod{3} \quad\Rightarrow\quad x\equiv (1*)c\mod{3}
[/mm]
[mm] 7x\equiv c\mod{15}\quad\Rightarrow\quad 7x\equiv c\mod{5} \quad\Rightarrow\quad 2x\equiv c\mod{5} \quad\Rightarrow\quad x\equiv 3c\mod{5}
[/mm]
Hieraus folgt mit chin.Restsatz leicht [mm] x\equiv 13c\mod{15}
[/mm]
Grüße
reverend
|
|
|
|
