eulersche Phi-funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:48 Mi 03.02.2010 | | Autor: | wauwau |
Sei n eine natürliche Zahl, p eine Primzahl und 0<a < p
n sei quadratfrei, hat also keinen Primfaktor, der zweimal vorkommt.
Zeige:
Gilt: [mm] $n\equiv [/mm] a [mm] \mod(p^3)$ [/mm] dann [mm] $\phi(n) \not \equiv a\mod(p^2)$
[/mm]
Hab schon alle Variante von Euler-Fermat angewendet und komme auf keinen grünen Zweig.
Vielleicht stimmts ja auch nicht...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:08 Mi 03.02.2010 | | Autor: | felixf |
Moin!
> Sei n eine natürliche Zahl, p eine Primzahl und 0<a < p
> n sei quadratfrei, hat also keinen Primfaktor, der zweimal
> vorkommt.
>
> Zeige:
>
> Gilt: [mm]n\equiv a \mod(p^3)[/mm] dann [mm]\phi(n) \not \equiv a\mod(p^2)[/mm]
Sei $p$ eine ungerade Primzahl, und seien [mm] $p_1, \dots, p_t$ [/mm] paarweise verschiedene Primzahlen mit [mm] $p_i \equiv [/mm] 2 [mm] \pmod{p^3}$ [/mm] (ueber $t$ sage ich erst spaeter was). Sei $n = [mm] \prod_{i=1}^t p_i$; [/mm] dann ist [mm] $\phi(n) [/mm] = [mm] \prod_{i=1}^n (p_i [/mm] - 1)$, womit [mm] $\phi(n) \equiv [/mm] 1 [mm] \pmod{p^3}$ [/mm] und somit auch modulo [mm] $p^2$ [/mm] ist.
Weiterhin ist $n [mm] \equiv 2^t \pmod{p^3}$, [/mm] und da $p$ ungerade ist, ist $2$ modulo [mm] $p^3$ [/mm] invertierbar. Man kann also $t$ gross genug waelhen (etwa $t = [mm] p^2 [/mm] (p - 1)$ nach Euler-Fermat) und erhaelt $n [mm] \equiv [/mm] 1 [mm] \pmod{p^3}$. [/mm] Damit hat man ein Gegenbeispiel mit $a = 1$.
Ich kann mir auch vorstellen, dass man mit anderen Werten von $a$ ein Gegenbeispiel bekommt, da muss man aber wohl etwas mehr Muehe investieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:36 Do 04.02.2010 | | Autor: | wauwau |
| Aufgabe | | könntest du für a=2 auch ein Gegenbeispiel konstruieren? |
Danke vorerst für deine Antwort
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:12 Fr 05.02.2010 | | Autor: | felixf |
Hallo!
> könntest du für a=2 auch ein Gegenbeispiel konstruieren?
> Danke vorerst für deine Antwort
Waehle $p = 5$, [mm] $p_1 [/mm] = 3$ und die Primzahlen [mm] $p_2, \dots, p_{95}$ [/mm] (wie immer paarweise verschieden) mit [mm] $p_i \equiv [/mm] 2 [mm] \pmod{5^3}$. [/mm] Sei wieder $n = [mm] \prod_{i=1}^{95} p_i$. [/mm] Dann gilt [mm] $\phi(n) [/mm] = [mm] \prod_{i=1}^{95} (p_i [/mm] - 1) [mm] \equiv [/mm] 2 [mm] \cdot 1^{94} \equiv [/mm] 2 [mm] \pmod{5^3}$ [/mm] und $n [mm] \equiv [/mm] 3 [mm] \cdot 2^{94} \equiv [/mm] 2 [mm] \pmod{5^3}$.
[/mm]
Allgemein kann man fuer ein $a$ einfach $p > a + 1$ genug gross waehlen (eventuell muss man mehr als ein $p$ probieren), und dann [mm] $p_1 \equiv [/mm] a + 1 [mm] \pmod{p^3}$ [/mm] und [mm] $p_i \equiv [/mm] 2 [mm] \pmod{p^3}$ [/mm] waehlen; dann sucht man noch ein $t$ mit $(a + 1) [mm] 2^t \equiv [/mm] a [mm] \pmod{p^3}$ [/mm] (sowas muss es nicht immer geben, deswegen mehrere $p$ probieren) und voila, man muss nur $n = [mm] p_1 \cdot \prod_{i=1}^t p_{i+1}$ [/mm] setzen mit [mm] $p_{i+1} \equiv [/mm] 2 [mm] \pmod{p^3}$, [/mm] $1 [mm] \le [/mm] i [mm] \le [/mm] t$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:44 Sa 06.02.2010 | | Autor: | wauwau |
super - allgemein verneinbar....
|
|
|
|
