2 lineare kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:08 So 10.06.2012 | | Autor: | kalifat |
| Aufgabe | a) [mm] 8x\equiv{12} [/mm] (mod 19)
b) [mm] 8x\equiv{12} [/mm] (mod 28) |
Bei a) ggT(8,19)=1=3*19-7*8=1 (mit eukl. Algorithmus). Nun müsste doch -7 eine Lösung sein oder? 56 und 12 haben aber nicht denselben Rest bei Division durch 19.
Es sind doch [mm] x_0+k*\bruch{m}{d} [/mm] alle modulo m paarweise inkongruente Lösungen von [mm] ax\equiv{b} [/mm] (mod m)
[mm] x_0 [/mm] wäre bei a) nach dem Algor. gleich -7, funktioniert jedoch nicht.
Bei b) würde ich es zuerst reduzieren: [mm] 2x\equiv{3} [/mm] (mod 7) [mm] \equiv{2*5} [/mm] (mod 7)
=> x=5 (mod 7)
|
|
| |
|
Hallo kalifat,
> a) [mm]8x\equiv{12}[/mm] (mod 19)
> b) [mm]8x\equiv{12}[/mm] (mod 28)
> Bei a) ggT(8,19)=1=3*19-7*8=1 (mit eukl. Algorithmus). Nun
> müsste doch -7 eine Lösung sein oder? 56 und 12 haben
> aber nicht denselben Rest bei Division durch 19.
>
Um auf die Lösung zu kommen,
mußt Du die Kongruenz in a) mit -7 durchmultiplizeren:
[mm]8x\equiv{12} \ (mod 19)[/mm]
[mm]\gdw \left(-7)*8x\equiv{\left(-7\right)*12} \ (mod 19)[/mm]
> Es sind doch [mm]x_0+k*\bruch{m}{d}[/mm] alle modulo m paarweise
> inkongruente Lösungen von [mm]ax\equiv{b}[/mm] (mod m)
>
> [mm]x_0[/mm] wäre bei a) nach dem Algor. gleich -7, funktioniert
> jedoch nicht.
>
> Bei b) würde ich es zuerst reduzieren: [mm]2x\equiv{3}[/mm] (mod 7)
> [mm]\equiv{2*5}[/mm] (mod 7)
>
> => x=5 (mod 7)
Das stimmt. ![[ok]](/images/smileys/ok.gif "[ok]")
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:26 So 10.06.2012 | | Autor: | kalifat |
Danke für deine Antwort, ich sehe aber immer noch nicht die Lösung.
Ich kenne die Regel, dass wenn
[mm] ka\equiv{kb} [/mm] (m) und [mm] k\not=0 [/mm] => [mm] a\equiv{b} (\bruch{m}{ggT(k,m)})
[/mm]
aber sie hilft mir hier nichts, da ich immer zur Ausgangsgleichung gelange.
|
|
|
| |
|
Hallo kalifat,
> Danke für deine Antwort, ich sehe aber immer noch nicht
> die Lösung.
>
> Ich kenne die Regel, dass wenn
>
> [mm]ka\equiv{kb}[/mm] (m) und [mm]k\not=0[/mm] => [mm]a\equiv{b} (\bruch{m}{ggT(k,m)})[/mm]
>
> aber sie hilft mir hier nichts, da ich immer zur
> Ausgangsgleichung gelange.
Ziel ist doch, daß da steht: [mm]x \equiv \ ...[/mm].
Dies erreichst Du durch die Multiplikation dieser Kongruenz mit -7.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:50 So 10.06.2012 | | Autor: | kalifat |
[mm] (-7)\cdot{}8x\equiv{\left(-7\right)\cdot{}12} [/mm] (mod 19)
=> 19|(-7*8x+7*12)
-7*8x+7*12=7*(12-8x)
12-8x muss Vielfaches von 19 sein, also 12-8x=19k mit [mm] k\in\IZ
[/mm]
Nur erhalte ich für x dann wieder nichts Schönes.
|
|
|
| |
|
Hallo kalifat,
> [mm](-7)\cdot{}8x\equiv{\left(-7\right)\cdot{}12}[/mm] (mod 19)
>
Es steht doch da:
[mm](-56)x\equiv -84 [/mm] (mod 19)
Es ist doch [mm](-56) \equiv 1[/mm] (mod 19)
Berechne [mm](-84)\equiv x_{0} [/mm] (mod 19) so, daß [mm]x_{0} \ge 0[/mm] ist.
> => 19|(-7*8x+7*12)
>
> -7*8x+7*12=7*(12-8x)
>
> 12-8x muss Vielfaches von 19 sein, also 12-8x=19k mit
> [mm]k\in\IZ[/mm]
>
> Nur erhalte ich für x dann wieder nichts Schönes.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:12 So 10.06.2012 | | Autor: | kalifat |
[mm] (-84)\equiv x_{0} [/mm] (mod 19) für [mm] x_0=8
[/mm]
|
|
|
| |
|
Hallo kalifat,
> [mm](-84)\equiv x_{0}[/mm] (mod 19) für [mm]x_0=8[/mm]
Das stimmt nicht.
Richtig ist [mm]x_{0}=11[/mm]
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:22 So 10.06.2012 | | Autor: | kalifat |
Danke für deine Hilfe, und da der ggT=1 ist 11 auch die einzige Lösung, richtig?
|
|
|
| |
|
Hallo kalifat,
> Danke für deine Hilfe, und da der ggT=1 ist 11 auch die
> einzige Lösung, richtig?
11 ist nicht die einzige Lösung.
Lösungen sind alle x, für die gilt:
[mm]x \equiv 11 \ \operatorname{mod} \ \left(19\right)[/mm]
Demnach auch x=30, x=49, x=68 usw.
Gruss
MathePower
|
|
|
|
