Einzige Lösung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:30 So 07.07.2013 | | Autor: | wauwau |
| Aufgabe | Zeige, dass $n=4$ die einzige Lösung der Gleichung
[mm] $3\varphi(n)=2(n-1)$ [/mm] wobei [mm] $\varphi$ [/mm] die Eulersche [mm] $\varphi$-Funktion [/mm] ist.
ist |
Ich kenne zwar die Lehmer Vermutung nachdem kein [mm] $\varphi(n)$ [/mm] $n-1$ teilt, aber diese Aufgabe ist ja doch etwas anders. (oder ist folgt sie aus dieser oder umgekehrt)?
|
|
| |
|
Hey wauwau,
edit: ok, etwas zu vorschnell. Aber wenn $n$ prim ist behaupte ich dennoch, dass diese komische Vermutung nicht stimmt, denn dann ist [mm] $\phi(n)=n-1$, [/mm] insbesondere ein Teiler davon.^^
Spaßeshalber können wir erstmal $n$ prim ausschließen, denn dann gilt [mm] $\phi(n)=n-1$.
[/mm]
Betrachtung modulo 3 gibt uns sofort: $n [mm] \equiv [/mm] 1$ (mod 3).
Weitere Einschränkungen an $n$ liefert wieder die Aussage, dass [mm] $\phi(n)$ [/mm] gerade ist für ausreichend großes $n$. Es habe jetzt $n$ genau $k$ verschiedene Primfaktoren [mm] $\geq [/mm] 3$, also $n = [mm] 2^a\cdot \prod_{i=1}^k p_i^{a_i}$.
[/mm]
Dann ist [mm] $\phi(n) [/mm] = [mm] \phi(2^a)\cdot \ldots [/mm] = [mm] 2^{a-1}\cdot \ldots$ [/mm] und jeder der hinteren Faktoren ist gerade. Also ist [mm] $\phi(n)$ [/mm] durch [mm] $2^{a+k-1}$ [/mm] teilbar und wir erhalten $n [mm] \equiv [/mm] 1$ (mod [mm] $2^{a+k-2}$).
[/mm]
Insbesondere ist $n$ ungerade, sobald $k [mm] \geq [/mm] 3$ ist und für $a [mm] \geq [/mm] 3$ erhalten wir einen Widerspruch, haben damit also auch alle Zweierpotenzen ausgeschlossen.
Das heißt es bleiben jetzt nur noch die Zahlen $n$ der Form
[mm] $n=2^a\cdot p^b \cdot q^c$ [/mm] für $p,q$ prim und $a,b,c [mm] \in \IN_0$ [/mm] auszuschließen.
Zuerst einmal den Fall
$n = [mm] 2^a\cdot p^b$:
[/mm]
Dann ist [mm] $\phi(n) [/mm] = [mm] 2^{a-1}\cdot(p^b-p^{b-1})= 2^{a-1}\cdot p^{b-1}\cdot [/mm] (p-1)$.
Auch dies ist wieder durch [mm] $2^a$ [/mm] teilbar (da $p$ ungerade) und damit erhalten wir wieder zwingend $n [mm] \equiv [/mm] 1$ (mod [mm] $2^{a-1}$).
[/mm]
Gucken wir uns unser $n$ nochmal an so ist dieses entweder $0$ (mod [mm] $2^{a-1}$) [/mm] oder $a=0$.
Als nächstes
[mm] $n=2^a\cdot p^b \cdot q^c$:
[/mm]
Hier haben wir [mm] $\phi(n) [/mm] = [mm] 2^{a-1}\cdot p^{b-1}(p-1)\cdot q^{c-1}(q-1)$ [/mm] und wir erhalten wieder als Forderung $n [mm] \equiv [/mm] 1$ (mod [mm] $2^a$), [/mm] was uns wie oben zwingend $a=0$ liefert.
Bleibt also
[mm] $n=p^k$ [/mm] für eine ungerade Primzahl $p$:
Hier ist [mm] $\phi(n) [/mm] = [mm] p^{k-1}(p-1)$ [/mm] und da $n$ ungerade ist, erhalten wir $p [mm] \equiv [/mm] 1$ (mod 4).
Was also noch ausgeschlossen werden muss (und wo ich jetzt gerade hänge) sind folgende $n$ (die alle 1 mod 3 sein müssen):
[mm] $n=p^k$ [/mm] für $p$ prim, $k [mm] \geq [/mm] 2$ und $p [mm] \equiv [/mm] 1$ (mod 4).
[mm] $n=p^a\cdot q^b$ [/mm] mit $p [mm] \neq [/mm] q$ prim und beide ungerade.
Vielleicht fällt dir für diese beiden Fälle ja noch was ein...
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:30 So 07.07.2013 | | Autor: | wauwau |
> Hey wauwau,
>
> edit: ok, etwas zu vorschnell. Aber wenn [mm]n[/mm] prim ist
> behaupte ich dennoch, dass diese komische Vermutung nicht
> stimmt, denn dann ist [mm]\phi(n)=n-1[/mm], insbesondere ein Teiler
> davon.^^
Lehmersche Vermutung besagt, es gibt keine zusammengesetzte Zahl wo [mm] $\varphi(n)$ [/mm] $n-1$ teilt
>
>
> Spaßeshalber können wir erstmal [mm]n[/mm] prim ausschließen,
> denn dann gilt [mm]\phi(n)=n-1[/mm].
> Betrachtung modulo 3 gibt uns sofort: [mm]n \equiv 1[/mm] (mod 3).
> Weitere Einschränkungen an [mm]n[/mm] liefert wieder die Aussage,
> dass [mm]\phi(n)[/mm] gerade ist für ausreichend großes [mm]n[/mm].
[mm] $\phi(n)$ [/mm] ist immer gerade nicht nur für ausreichend große n!
> Es habe
> jetzt [mm]n[/mm] genau [mm]k[/mm] verschiedene Primfaktoren [mm]\geq 3[/mm], also [mm]n = 2^a\cdot \prod_{i=1}^k p_i^{a_i}[/mm].
>
> Dann ist [mm]\phi(n) = \phi(2^a)\cdot \ldots = 2^{a-1}\cdot \ldots[/mm]
> und jeder der hinteren Faktoren ist gerade. Also ist
> [mm]\phi(n)[/mm] durch [mm]2^{a+k-1}[/mm] teilbar und wir erhalten [mm]n \equiv 1[/mm]
> (mod [mm]2^{a+k-2}[/mm]).
> Insbesondere ist [mm]n[/mm] ungerade, sobald [mm]k \geq 3[/mm] ist und für
> [mm]a \geq 3[/mm] erhalten wir einen Widerspruch, haben damit also
> auch alle Zweierpotenzen ausgeschlossen.
bis auf a=2,k=0
>
> Das heißt es bleiben jetzt nur noch die Zahlen [mm]n[/mm] der Form
> [mm]n=2^a\cdot p^b \cdot q^c[/mm] für [mm]p,q[/mm] prim und [mm]a,b,c \in \IN_0[/mm]
> auszuschließen.
> Zuerst einmal den Fall
> [mm]n = 2^a\cdot p^b[/mm]:
> Dann ist [mm]\phi(n) = 2^{a-1}\cdot(p^b-p^{b-1})= 2^{a-1}\cdot p^{b-1}\cdot (p-1)[/mm].
>
> Auch dies ist wieder durch [mm]2^a[/mm] teilbar (da [mm]p[/mm] ungerade) und
> damit erhalten wir wieder zwingend [mm]n \equiv 1[/mm] (mod
> [mm]2^{a-1}[/mm]).
> Gucken wir uns unser [mm]n[/mm] nochmal an so ist dieses entweder [mm]0[/mm]
> (mod [mm]2^{a-1}[/mm]) oder [mm]a=0[/mm].
>
> Als nächstes
> [mm]n=2^a\cdot p^b \cdot q^c[/mm]:
> Hier haben wir [mm]\phi(n) = 2^{a-1}\cdot p^{b-1}(p-1)\cdot q^{c-1}(q-1)[/mm]
> und wir erhalten wieder als Forderung [mm]n \equiv 1[/mm] (mod [mm]2^a[/mm]),
> was uns wie oben zwingend [mm]a=0[/mm] liefert.
>
> Bleibt also
> [mm]n=p^k[/mm] für eine ungerade Primzahl [mm]p[/mm]:
> Hier ist [mm]\phi(n) = p^{k-1}(p-1)[/mm] und da [mm]n[/mm] ungerade ist,
> erhalten wir [mm]p \equiv 1[/mm] (mod 4).
>
>
> Was also noch ausgeschlossen werden muss (und wo ich jetzt
> gerade hänge) sind folgende [mm]n[/mm] (die alle 1 mod 3 sein
> müssen):
> [mm]n=p^k[/mm] für [mm]p[/mm] prim, [mm]k \geq 2[/mm] und [mm]p \equiv 1[/mm] (mod 4).
> [mm]n=p^a\cdot q^b[/mm] mit [mm]p \neq q[/mm] prim und beide ungerade.
>
>
> Vielleicht fällt dir für diese beiden Fälle ja noch was
> ein...
warum schließt du [mm] $n=\prod_{i=1}^{m}p_i^{k_i}$ [/mm] mit ungeraden primen [mm] $p_i$ [/mm] und $m >2$ aus??? woraus man aber auf [mm] $k_i=1$ [/mm] also $n$ quadratfrei schließen kann
[mm] $n=p^k$
[/mm]
[mm] $3\varphi(p^k) [/mm] = [mm] 3(p-1)p^{k-1}=2(p^k-1)$
[/mm]
[mm] $p^{k-1}(p-3)=-2$ [/mm] was ein Widerspruch ist außer p=2,k=2, was wiederum zur Lösung n=4 führt.
>
>
> lg
>
> Schadow
|
|
|
| |
|
> warum schließt du [mm]n=\prod_{i=1}^{m}p_i^{k_i}[/mm] mit ungeraden
> primen [mm]p_i[/mm] und [mm]m >2[/mm] aus??? woraus man aber auf [mm]k_i=1[/mm] also [mm]n[/mm]
> quadratfrei schließen kann
Ach Mist, hast ja Recht...
Zumindest sollte die Argumentation gerade $n$ ausschließen können (hoffe ich mal^^) und $n$ quadratfrei hast du auch Recht mit.
Also haben wir [mm] $n=\prod_{i=1}^k p_i$ [/mm] mit [mm] $p_i$ [/mm] ungerade und paarweise verschieden.
$n [mm] \equiv [/mm] 1$ (mod 3) gibt uns, dass die Anzahl der [mm] $p_i$, [/mm] die -1 (mod 3) sind, gerade sein muss.
Weiterhin muss $n [mm] \equiv [/mm] 1(mod [mm] 2^{k-1})$ [/mm] gelten - damit haben wir wenigstens noch ein paar Einschränkungen, wenn auch bei weitem nicht so schöne wie ich gehofft hatte...
Wir haben jetzt [mm] $\phi(n) [/mm] = [mm] \prod p_i-1$.
[/mm]
Angenommen [mm] $3\prod( p_i-1) [/mm] = [mm] 2(\prod p_i)-2$
[/mm]
Kann man hier ggf. ein "wenn die [mm] $p_i$ [/mm] zu groß sind, rettet uns auch die 3 nicht mehr, dann ist die rechte Seite viel größer als die linke" bauen und es damit auf endlich viele [mm] $p_i$ [/mm] (und dann durch Quadratfreiheit) auf endlich viele $n$ reduzieren?
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 14:55 So 07.07.2013 | | Autor: | wauwau |
> > warum schließt du [mm]n=\prod_{i=1}^{m}p_i^{k_i}[/mm] mit
> ungeraden
> > primen [mm]p_i[/mm] und [mm]m >2[/mm] aus??? woraus man aber auf [mm]k_i=1[/mm]
> also [mm]n[/mm]
> > quadratfrei schließen kann
>
> Ach Mist, hast ja Recht...
> Zumindest sollte die Argumentation gerade [mm]n[/mm] ausschließen
> können (hoffe ich mal^^) und [mm]n[/mm] quadratfrei hast du auch
> Recht mit.
> Also haben wir [mm]n=\prod_{i=1}^k p_i[/mm] mit [mm]p_i[/mm] ungerade und
> paarweise verschieden.
> [mm]n \equiv 1[/mm] (mod 3) gibt uns, dass die Anzahl der [mm]p_i[/mm], die
> -1 (mod 3) sind, gerade sein muss.
> Weiterhin muss [mm]n \equiv 1(mod 2^{k-1})[/mm] gelten - damit
> haben wir wenigstens noch ein paar Einschränkungen, wenn
> auch bei weitem nicht so schöne wie ich gehofft hatte...
>
> Wir haben jetzt [mm]\phi(n) = \prod p_i-1[/mm].
> Angenommen [mm]3\prod( p_i-1) = 2(\prod p_i)-2[/mm]
Oder aber:
[mm] $\prod(1-\frac{1}{p_i}) [/mm] < [mm] \frac{2}{3}$ [/mm] was, da [mm] $\prod(1-\frac{1}{p})=0$ [/mm] über alle Primzahlen prinzipiell nicht unmöglich erscheint...
>
> Kann man hier ggf. ein "wenn die [mm]p_i[/mm] zu groß sind, rettet
> uns auch die 3 nicht mehr, dann ist die rechte Seite viel
> größer als die linke" bauen und es damit auf endlich
> viele [mm]p_i[/mm] (und dann durch Quadratfreiheit) auf endlich
> viele [mm]n[/mm] reduzieren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 07.08.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mi 07.08.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
