Einfaches Kongruenzensystem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:33 So 11.07.2010 | | Autor: | kickerle |
Hallo zusammen,
ich zerbreche mir gerade über folgende Aufgabe den Kopf:
Gegeben ist das Kongruenzensystem
[mm] x^2\equiv a_1 \pod{p^n}
[/mm]
xy [mm] \equiv a_2 \pod{p^n}
[/mm]
[mm] y^2\equiv a_3 \pod{p^n}
[/mm]
wobei die [mm] a_i [/mm] ganze Zahlen mit [mm] ggT(a_1,a_2,a_3)=1 [/mm] sind und p eine ungerade Primzahl. Gezeigt werden soll nun, dass wenn [mm] x_1,y_1 [/mm] eine Lösung dieses System ist, dass es dann nur noch genau eine weitere Lösung gibt die von dieser verschieden (d.h. nicht äquivalent) ist und, dass diese gerade durch [mm] x_2=-x_1 [/mm] und [mm] y_2=-y_1 [/mm] gegeben ist. Klar ist mir, dass diese beiden Lösungen stets verschieden sind,d.h. dass es immer mindestens diese beiden Lösungen gibt. Warum gibt es aber keine anderen Zahlenpaare welche die Kongruenzen lösen???
Wäre nett wenn mir jemand einen Tipp geben könnte. Ich steh da gerade auf dem Schlauch. Vermute fast, dass die Lösung mehr oder weniger offensichtlich ist...aber im Moment seh ich es einfach nicht.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:27 Mo 12.07.2010 | | Autor: | PeterB |
Hallo kickerle,
Hier eine Skizze einer möglichen Lösung:
Zeige erst, dass mindestens eine der Zahlen [mm] $a_1$ [/mm] und [mm] $a_3$ [/mm] nicht durch p teilbar ist. Sagen wir o.B.d.A. [mm] $a_1$ [/mm] dann gibt es genau zwei Lösungen von [mm] $x^2\equiv a_1 \text{ mod } p^n$. [/mm] (Da der Fall, dass es gar keine gibt ausgeschlossen ist.) Diese zwei Lösungen für $x$ legen $y$ jeweils fest.
Gruß
Peter
|
|
|
| |
|
Alles klar, hab ich verstanden. Vielen Dank. Noch eine Anschlußfrage aus Interesse. Wenn ich statt dem Modul [mm] p^n [/mm] den modul 4 betrachte, dann gibt es ja auch nur diese beiden Lösungen. Warum soll soll es dann bei einem Modul [mm] 2^n [/mm] mit n>2 4 Lösungen geben? (steht so in einem Buch) Kann man die 4 Lösungen denn stest angeben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:39 Do 15.07.2010 | | Autor: | felixf |
Moin!
> Alles klar, hab ich verstanden. Vielen Dank. Noch eine
> Anschlußfrage aus Interesse. Wenn ich statt dem Modul [mm]p^n[/mm]
> den modul 4 betrachte, dann gibt es ja auch nur diese
> beiden Lösungen.
Es sind nicht umbedingt diese beiden Loesungen: die Geichung [mm] $x^2 \equiv [/mm] 0 [mm] \pmod{4}$ [/mm] hat z.B. die Loesungen 0 und 2, und es ist nicht $-2 = 0$.
Die Gleichung [mm] $x^2 \equiv [/mm] 1 [mm] \pmod{4}$ [/mm] dagegen hat die Loesungen 1 und 3, und es ist $-3 = 1$ (modulo 4).
Die Gleichungen [mm] $x^2 \equiv [/mm] 2 [mm] \pmod{4}$ [/mm] und [mm] $x^2 \pmod{3} \pmod{4}$ [/mm] haben keine Loesung.
> Warum soll soll es dann bei einem Modul
> [mm]2^n[/mm] mit n>2 4 Lösungen geben? (steht so in einem Buch)
> Kann man die 4 Lösungen denn stest angeben?
Nehmen wir mal $n = 3$. Dann hast du: [mm] $\begin{array}{c|cccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline x^2 \pmod{8} & 0 & 1 & 4 & 1 & 0 & 1 & 4 & 1 \end{array}$
[/mm]
Wie du siehst, hat die Gleichung [mm] $x^2 \equiv [/mm] 0 [mm] \pmod{8}$ [/mm] genau 2 Loesungen, die Gleichung $x [mm] \equiv [/mm] 1 [mm] \pmod{8}$ [/mm] genau 4 Loesungen, und die Gleichung $x [mm] \equiv [/mm] 4 [mm] \pmod{8}$ [/mm] genau 2 Loesungen.
Ist die Aussage eventuell auf Gleichungen [mm] $x^2 \equiv [/mm] a [mm] \pmod{2^n}$ [/mm] bezogen mit $a$ ungerade? In dem Fall koennte es tatsaechlich stimmen, dass jede solche Gleichung entweder 0 oder 4 Loesungen hat.
Interessant ist aber: wenn man eine Loesung modulo [mm] $2^{n+1}$ [/mm] hat, dann ist es auch modulo [mm] $2^n$ [/mm] eine. Umgekehrt: wenn $x$ modulo [mm] $2^n$ [/mm] eine Loesung ist, dann ist es entweder modulo [mm] $2^{n+1}$ [/mm] keine, oder modulo [mm] $2^{n+1}$ [/mm] sind sowohl $x$ wie auch $x + [mm] 2^n$ [/mm] eine Loesung!
Damit haben wir ein interessantes Phaenomen: macht man $n$ um eins groesser, werden aus zwei der vier Loesungen die vier neuen, und zwei der Loesungen kann man "wegwerfen".
(Beim Uebergang von $n = 1$ nach $n = 2$, und von $n = 2$ nach $n = 3$ hat man immer zwei neue pro Loesung bekommen und musste nichts "wegwerfen" -- man hat also erst eine (modulo 2), dann 2 (modulo 4) und schliesslich 4 (modulo 8) Loesungen. Nur ab $n > 3$ muss man dann "wegwerfen".)
Das ganze gibt uns aber schonmal eine Idee, wie die Loesungen aussehen (der Einfachheit halber erst fuer $a = 1$): wenn man modulo [mm] $2^n$ [/mm] die Loesungen $x, x + [mm] 2^{n-1}, [/mm] x', x' + [mm] 2^{n-1}$ [/mm] hat, dann kann man zwei davon nehmen, sagen wir [mm] $x_1$ [/mm] und [mm] $x_2$, [/mm] und bekommt die Loesungen [mm] $x_1, x_1 [/mm] + [mm] 2^n, x_2, x_2 [/mm] + [mm] 2^n$ [/mm] modulo [mm] $2^{n+1}$. [/mm] Ich wuerde vermuten, dass man [mm] $x_1 \in \{ x, x + 2^{n-1} \}$ [/mm] und [mm] $x_2 \in \{ x', x' + 2^{n-1} \}$ [/mm] waehlen kann. Du kannst das ja mal versuchen zu beweisen oder naeher zu untersuchen :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:56 Sa 17.07.2010 | | Autor: | kickerle |
Hallo Felix,
richtig, a muss als ungerade vorausgesetzt werden. Sorry, dass ich das nicht gleich bemerkt habe. Ich habe es mir jetzt mal genauer angeschaut und denke, dass eine vollständigen Induktion das Problem endgültig löst.
Es sei [mm] $a\equiv [/mm] 1 [mm] \pod{2^n}$ [/mm] (alle anderen Fälle zeigt man analog). Zu zeigen ist, dass diese Kongruenz genau 4 Lösungen hat. Ist $n=3$ und [mm] $x^2\equiv a\pod{2^3}$ [/mm] lösbar, dann ist [mm] $a\equiv1\pod{8}$ [/mm] (da [mm] $a\in 2\mathbb [/mm] Z+1$ ist) und die Lösungen sind [mm] $x_3^{(1)}\equiv [/mm] 1 [mm] \pod{2^3}$, $x_3^{(2)}\equiv [/mm] 3 [mm] \pod{2^3}$, $x_3^{(3)}\equiv5\pod{2^3}$, $x_3^{(4)}\equiv [/mm] 7 [mm] \pod{2^3}$. [/mm] Es gilt also [mm] $x_3^{(1)}\equiv [/mm] 1 [mm] \pod{2^3}$, $x_3^{(2)}\equiv 2^2-1 \pod{2^3}$, $x_3^{(3)}\equiv2^2+1\pod{2^3}$, $x_3^{(4)}\equiv [/mm] -1 [mm] \pod{2^3}$. [/mm] Angenommen die Kongruenz [mm] $x^2\equiv [/mm] 1 [mm] \pod{2^n}$ [/mm] hat die vier Lösungen [mm] $x_n^{(1)}\equiv [/mm] 1 [mm] \pod{2^n}$, $x_n^{(2)}\equiv 2^{n-1}-1 \pod{2^n}$, $x_n^{(3)}\equiv 2^{n-1}+1 \pod{2^n},$ $x_n^{(4)}\equiv [/mm] -1 [mm] \pod{2^n}$. [/mm] Wie aus der elementaren Zahlentheorie bekannt ist, erhält man dann die Lösungen von [mm] $x^2\equiv [/mm] 1 [mm] \pod{2^{n+1}}$ [/mm] aus denjenigen [mm] $x_n^{(i)}$ [/mm] für die [mm] $(x_n^{(i)})^2-1\equiv 0\pod{2^{n+1}}$ [/mm] gilt, in diesem Fall also aus [mm] $x_n^{(1)}$ [/mm] und [mm] $x_n^{(4)}$. [/mm] Die Lösungen von [mm] $x^2\equiv [/mm] 1 [mm] \pod {2^{n+1}}$ [/mm] sind dann [mm] $x_{n+1}^{(1)}=x_n^{(1)}+0\cdot 2^n$, $x_{n+1}^{(2)}=x_n^{(1)}+1\cdot2^n$ [/mm] und [mm] $x_{n+1}^{(3)}=x_n^{(4)}+0\cdot 2^n$, $x_{n+1}^{(4)}=x_n^{(4)}+1\cdot2^n$ [/mm] und für diese gilt [mm] $x_{n+1}^{(1)}\equiv [/mm] 1 [mm] \pod{2^{n+1}}$, $x_{n+1}^{(2)}\equiv 2^n+1\pod{2^{n+1}}$, $x_{n+1}^{(3)}\equiv 2^n-1\pod{2^{n+1}}$ [/mm] und [mm] $x_{n+1}^{(4)}\equiv -1\pod{2^{n+1}}$. [/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 16.07.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
