chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:21 Di 25.03.2008 | | Autor: | D-C |
| Aufgabe | | Welche natürlichen Zahlen lassen beim Teilen durch 7,11,13 die Reste 2,4,3 ? |
Hallo, habe folgenden Ansatz:
x [mm] \equiv [/mm] 2 mod 7 , x [mm] \equiv [/mm] 4 mod 11 , x [mm] \equiv [/mm] 3 mod 13
M1 = 11*13= 143 [mm] \equiv [/mm] 3 mod 7
M2 = 7*13= 91 [mm] \equiv [/mm] 3 mod 11
M3 = 7*11= 77 [mm] \equiv [/mm] 12 mod 13
3N1 [mm] \equiv [/mm] 1 mod 7 => N1 = 5
3N2 [mm] \equiv [/mm] 1 mod 11 => N2= 4
12N3 [mm] \equiv [/mm] 1 mod 13 => N3 = 12
x = 2*143*5+4*91*4+3*77*12=5658
Abändern um Vielfache von 7*11*13=1001
=> x [mm] \equiv [/mm] 653 (1001)
Wie kommt man auf die rot markierten Ergebnisse?
Gruß
D-C
|
|
| |
|
Hallo D-C,
> Welche natürlichen Zahlen lassen beim Teilen durch 7,11,13
> die Reste 2,4,3 ?
> Hallo, habe folgenden Ansatz:
>
>
> x [mm]\equiv[/mm] 2 mod 7 , x [mm]\equiv[/mm] 4 mod 11 , x [mm]\equiv[/mm] 3 mod 13
>
> M1 = 11*13= 143 [mm]\equiv[/mm] 3 mod 7
> M2 = 7*13= 91 [mm]\equiv[/mm] 3 mod 11
> M3 = 7*11= 77 [mm]\equiv[/mm] 12 mod 13
>
> 3N1 [mm]\equiv[/mm] 1 mod 7 => N1 = 5
> 3N2 [mm]\equiv[/mm] 1 mod 11 => N2= 4
> 12N3 [mm]\equiv[/mm] 1 mod 13 => N3 = 12
Da 7 eine Primzahlen und teilerfremd zu 3 ist, gilt:
[mm]3^{p-1}\ \equiv \ 1 \ mod \ 7[/mm]
Übertragen auf die Gleichung
[mm]3 N_{1} \ \equiv \ 1 \ mod \ 7[/mm]
heißt das
[mm]3^{p-1} = 3^{6} = 3*3^{5} \ \equiv \ 1 \ mod \ 7[/mm]
Um jetzt [mm]3^{5}[/mm] modulo 7 zu berechnen gehe wie folgt vor:
[mm]3^{1} = 3 \ \equiv \ 3 \ mod \ 7[/mm]
[mm]3^{2} = 3*3 \ \equiv \ 2 \ mod \ 7[/mm]
[mm]3^{4}=3^{2}*3^{2}=2*2 = 4 \ mod \ 7 [/mm]
Da [mm]5=4+1[/mm] gilt [mm]3^{5}=3^{4}*3^{1}=3*4=12 \ \equiv \ 5 \ mod \ 7[/mm]
So geht das Spielchen auch mit den anderen Gleichungen.
>
> x = 2*143*5+4*91*4+3*77*12=5658
>
> Abändern um Vielfache von 7*11*13=1001
>
> => x [mm]\equiv[/mm] 653 (1001)
>
Nun, ich mach das immer so:
[mm] z \ \equiv \ 2 \ \left(7\right) \Rightarrow z=\alpha7+2[/mm]
Nächste Gleichung:
[mm] z \ \equiv \ 4 \ \left(11\right) \gdw \alpha 7 + 2 \ \equiv \ 4 \ \left(11\right) \ \gdw \alpha 7 \ \equiv \ 2 \ \left(11\right)[/mm]
Die Lösung dieser Gleichung ist
[mm] \alpha \ \equiv \ 2*7^{9} \ \left(11\right)[/mm]
,da [mm] \alpha*7=2*7^{9}*7=2*7^{10}=2 (11)[/mm]
Es muss also [mm]7^{9} \ mod \ 11 [/mm] berechnet werden.
[mm]7^{1} = 7 \ \equiv \ 7 \ \left(11\right)[/mm]
[mm]7^{2} = 7*7 \ \equiv \ 4 \ \left(11\right)[/mm]
[mm]7^{4}=7^{2}*7^{2}=4*4 = 3 \ \left(11\right) [/mm]
[mm]7^{8}=7^{4}*7^{4}=5*5 = 9 \ \left(11\right) [/mm]
Demnach ergibt sich [mm]\alpha \ \equiv \ 2*7^{9}=2*7^{8}*7^{1}=2*9*7=126=5 \ \left(11\right)[/mm]
Daher lautet die Lösung [mm]z=\alpha*7+2=\left(5+\beta*11\right)*7+2=\beta*77+37[/mm]
Nun die letzte Gleichung:
[mm]z \ \equiv \ 3 \ \left(13\right) \gdw \beta*77+37 \ \equiv \ 3 \left(13) \gdw \beta*12+11 \equiv \ 3 \ \left(13\right) \gdw \beta*12 \ \equiv 5 \ \left(13\right)[/mm]
Die Lösung ergibt sich hier zu [mm]\beta \ \equiv 5*12^{11} \ \left(13\right)[/mm]
[mm]12^{1} = 12 \ \equiv \ 12 \ \left(13\right)[/mm]
[mm]12^{2} = 12*12=144 \ \equiv \ 1 \ \left(13\right)[/mm]
[mm]12^{4}=12^{2}*12^{2}=1*1 = 1 \ \left(13\right) [/mm]
[mm]12^{8}=12^{4}*12^{4}=1*1 = 1 \ \left(13\right) [/mm]
Demnach ergibt sich [mm]\beta \ \equiv \ 5*12^{11}=2*12^{8}*12^{2}*12^{1}=5*1*1*12=60=8 \
\left(13\right)[/mm]
Daher lautet die Lösung [mm]z=\beta*77+37=\left(8+\gamma*13\right)*77+37=\gamma*1001+8*77+37=\gamma*1001+653[/mm]
Lösungen sind also [mm]z \ \equiv 653 \ \left(1001\right)[/mm]
>
> Wie kommt man auf die rot markierten Ergebnisse?
>
>
> Gruß
>
> D-C
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:21 Mi 26.03.2008 | | Autor: | D-C |
Ok danke, ich denke jetzt hab ichs verstanden.
Hab nun auch N2 und N3 berechnen können.
Gruß
D-C
|
|
|
|
