Kongruenzen von Produkten < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:12 So 05.09.2010 | | Autor: | wauwau |
| Aufgabe | Seien p eine Primzahl und a,b positive natürliche Zahlen:
Zeige:
$ab [mm] \equiv 1\mod{(p+1)} \gdw [/mm] a [mm] \equiv b\mod{(p+1)}$ [/mm] und $ggT(a,p+1)=1 $ |
Ist das ein bekannter Satz?
Wenn ja, in welchem Buch kann ich ihn finden?
Wenn nein, wie kann man ihn beweisen?
Oder stimmt er gar nicht?
Habe ein wenig probiert - und in der Kürze kein Gegenbeispiel gefunden gefunden...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:33 So 05.09.2010 | | Autor: | abakus |
> Seien p eine Primzahl und a,b positive natürliche Zahlen:
> Zeige:
> [mm]ab \equiv 1\mod{(p+1)} \gdw a \equiv b\mod{(p+1)}[/mm] und
> [mm]ggT(a,p+1)=1[/mm]
> Ist das ein bekannter Satz?
Hallo,
der Satz klingt interessant - und ich kenne ihn nicht.
Spontan habe ich für eine Richtung folgende Idee:
Aus a [mm] \equiv [/mm] b mod(p+1) folgt, dass [mm] ab\equiv a^2 [/mm] mod(p+1).
Diese Kongruenz lässt sich durch beidseitige Division durch a vereinfachen.
(Bei einer solchen Division erfolgt manchmal auch eine Änderung des Moduls, manchmal nicht... Du kennst diese Regel?)
Gruß Abakus
> Wenn ja, in welchem Buch kann ich ihn finden?
> Wenn nein, wie kann man ihn beweisen?
> Oder stimmt er gar nicht?
> Habe ein wenig probiert - und in der Kürze kein
> Gegenbeispiel gefunden gefunden...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:23 So 05.09.2010 | | Autor: | abakus |
> > Seien p eine Primzahl und a,b positive natürliche Zahlen:
> > Zeige:
> > [mm]ab \equiv 1\mod{(p+1)} \gdw a \equiv b\mod{(p+1)}[/mm] und
> > [mm]ggT(a,p+1)=1[/mm]
> > Ist das ein bekannter Satz?
> Hallo,
> der Satz klingt interessant - und ich kenne ihn nicht.
> Spontan habe ich für eine Richtung folgende Idee:
> Aus a [mm]\equiv[/mm] b mod(p+1) folgt, dass [mm]ab\equiv a^2[/mm]
> mod(p+1).
> Diese Kongruenz lässt sich durch beidseitige Division
> durch a vereinfachen.
> (Bei einer solchen Division erfolgt manchmal auch eine
> Änderung des Moduls, manchmal nicht... Du kennst diese
> Regel?)
> Gruß Abakus
Hallo,
ich sehe gerade, dass ich mich etwas im Kreis drehte.
Aus [mm]ab\equiv a^2[/mm] mod(p+1) und ab [mm] \equiv 1\mod{(p+1)} [/mm] folgt [mm] a^2 \equiv [/mm] 1 mod(p+1) und somit [mm] a^2-1 \equiv [/mm] 0 mod(p+1),
also ist (a-1)(a+1) durch (p+1) teilbar.
Gruß Abakus
>
> > Wenn ja, in welchem Buch kann ich ihn finden?
> > Wenn nein, wie kann man ihn beweisen?
> > Oder stimmt er gar nicht?
> > Habe ein wenig probiert - und in der Kürze kein
> > Gegenbeispiel gefunden gefunden...
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:10 So 05.09.2010 | | Autor: | felixf |
Moin!
> Seien p eine Primzahl und a,b positive natürliche Zahlen:
> Zeige:
> [mm]ab \equiv 1\mod{(p+1)} \gdw a \equiv b\mod{(p+1)}[/mm] und
> [mm]ggT(a,p+1)=1[/mm]
Die Rueckrichtung behauptet: ist $a$ eine Einheit in [mm] $\IZ/n\IZ$ [/mm] mit $n = p + 1$, so hat $a$ Ordnung 2. Das ist schlichtweg falsch: z.B. fuer $a = 3$ und $p = 13$ ist [mm] $a^2 \equiv [/mm] 9 [mm] \not\equiv [/mm] 1 [mm] \pmod{14}$, [/mm] obwohl $ggT(a, p + 1) = ggT(3, 14) = 1$ ist.
Fuer die andere Richtung gibt's auch Gegenbeispiele, etwa fuer $p = 13$. Es ist [mm] $\IZ/14\IZ \cong \IZ/2\IZ \times \IZ/7\IZ$, [/mm] womit man im Ring auf der rechten Seite $a = (1, 2)$ und $b = (1, 4)$ nehmen kann; dann ist $a b = (1, 1)$, jedoch $a [mm] \neq [/mm] b$. Mit dem Chinesischen Restsatz bekommt man $a = 9$, $b = 11$; dann gilt $a b = 99 [mm] \equiv [/mm] 1 [mm] \pmod{13+1}$, [/mm] jedoch $a [mm] \not\equiv [/mm] b [mm] \pmod{13+1}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:51 So 05.09.2010 | | Autor: | felixf |
Moin!
Ein Zusatz: man kann sich damit auch leicht ueberlegen, fuer welche Primzahlen $p$ die Aussage korrekt ist.
Dazu muss jedes Element in $G = [mm] (\IZ/(p+1)\IZ)^\ast$ [/mm] hoechstens Ordnung 2 haben: das ist aequivaent dazu, dass in der Gruppe $G$ die Aequivalenz $a b = 1 [mm] \Leftrightarrow [/mm] a = b$ gilt.
Das ist aber dann der Fall, wenn fuer jede Primzahlpotenz [mm] $\ell^n$, [/mm] die $p + 1$ teilt, gilt, dass [mm] $(\IZ/(\ell^n)\IZ)^\ast$ [/mm] eine solche Gruppe ist. Ist [mm] $\ell [/mm] > 3$, so gilt es schonmal nicht (es gibt ein Element der Ordnung [mm] $\ell [/mm] - 1$). Fuer [mm] $\ell [/mm] = 3$ gilt es nur fuer $n = 1$, andernfalls gibt es ein Element der Ordnung 3. Fuer [mm] $\ell [/mm] = 2$ gilt dies fuer $n [mm] \le [/mm] 3$ (ab $n = 4$ hat z.B. das Element 3 nicht Ordnung 2).
Damit also die Bedingung erfuellt ist, muss $p + 1 = [mm] 2^a 3^b$ [/mm] sein mit $a [mm] \in \{ 0, 1, 2, 3 \}$ [/mm] und $b [mm] \in \{ 0, 1 \}$. [/mm] Es bleiben also die Moeglichkeiten $p + 1 [mm] \in \{ 1, 2, 3, 4, 6, 8, 12, 24 \}$, [/mm] also $p [mm] \in \{ 0, 1, 2, 3, 5, 7, 11, 23 \}$ [/mm] (wovon einiges keine Primzahlen sind). Die kleinste Primzahl, fuer die die Aussage also nicht funktioniert, ist $p = 13$, und sie funktioniert ueberhaupt nur falls $p [mm] \in \{ 2, 3, 5, 7, 11, 23 \}$ [/mm] ist.
LG Felix
|
|
|
|
