euler-Phi 2 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:40 So 31.10.2010 | | Autor: | wauwau |
| Aufgabe | Sei p eine Primzahl, $a,b [mm] \in \IN$ [/mm] mit $a,b [mm] \ge [/mm] 1$
Wenn $ [mm] n-\phi(n)=p^a$ [/mm] und [mm] $n+2=p^b$ [/mm] dann folgt
$p=2$ |
Wieder mal wo ich nicht weiter weiß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:51 So 31.10.2010 | | Autor: | abakus |
> Sei p eine Primzahl, [mm]a,b \in \IN[/mm] mit [mm]a,b \ge 1[/mm]
> Wenn
> [mm]n-\phi(n)=p^a[/mm] und [mm]n+2=p^b[/mm] dann folgt
> [mm]p=2[/mm]
> Wieder mal wo ich nicht weiter weiß
Hallo
[mm] n-\phi(n)=p^a [/mm] könnte man umstellen zu
[mm] n-p^a=\phi(n)
[/mm]
Die Anzahl [mm] \phi(n) [/mm] der zu n teilerfremden Zahlen erhält man doch, indem man von n die Anzahl ihrer Teiler subtrahiert.
Bedeutet das nicht, dass [mm] p^a [/mm] gerade die Anzahl der Teiler von n ist, dass also jeder Primfaktor (von denen es genau p Stück geben müsste) von n in der Anzahl (a-1) vorkommen muss?
Aber Moment mal, die 1 ist zwar ein Teiler von n, sie wird doch aber bei [mm] \phi(n) [/mm] mitgezählt, weil der ggt von 1 und n 1 ist?
Dann müsste die Anzahl aller Teiler von n also [mm] n-\phi(n)+1 [/mm] sein.
Da hilft der Ansatz wohl doch nichts, oder?
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:52 Mo 01.11.2010 | | Autor: | wauwau |
> [mm]n-\phi(n)=p^a[/mm] könnte man umstellen zu
> [mm]n-p^a=\phi(n)[/mm]
> Die Anzahl [mm]\phi(n)[/mm] der zu n teilerfremden Zahlen erhält
> man doch, indem man von n die Anzahl ihrer Teiler
> subtrahiert.
Leider nicht, denn [mm] $\phi(9)=9-|\{3,6,9\}|=6$ [/mm] und die Anzahl der Teiler von 9 wäre aber nur 1
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:01 Mo 01.11.2010 | | Autor: | felixf |
Moin!
> > [mm]n-\phi(n)=p^a[/mm] könnte man umstellen zu
> > [mm]n-p^a=\phi(n)[/mm]
> > Die Anzahl [mm]\phi(n)[/mm] der zu n teilerfremden Zahlen
> erhält
> > man doch, indem man von n die Anzahl ihrer Teiler
> > subtrahiert.
>
> Leider nicht, denn [mm]\phi(9)=9-|\{3,6,9\}|=6[/mm] und die Anzahl
> der Teiler von 9 wäre aber nur 1
Nun, die Zahl der Teiler von 9 ist schon 3: 1, 3 und 9 sind die Teiler von 9.
Allerdings stimmt es trotzdem nicht: z.B. fuer $n = 12$ gibt es 6 Teiler (1, 2, 3, 4, 6, 12), jedoch 8 Nicht-Einheiten modulo $n$ (0, 2, 3, 4, 6, 9, 8, 10). Damit ist [mm] $\phi(n) [/mm] = n - 8$ und nicht $n - 6$.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:53 Di 02.11.2010 | | Autor: | moudi |
Hallo wauwau
Ich nehme an, das folgende hast du auch herausgefunden.
1. Ist n gerade, sost ist p=2 (trivial).
2. n=prim erfuellt nicht die Voraussetzungen (fast trivial).
3. Ist n nicht quadratfrei, so ist p=2 (ziemlich einfach).
4. Fuer alle anderen n ist [mm] $p\equiv 3\mod [/mm] 4$. Hier muesste man zeigen, dass nicht gleichzeitig [mm] $n+2=p^b$ [/mm] und [mm] $n-\varphi(n)=p^a$ [/mm] sein kann.
Kannst du irgendwelche Hintergruende angeben, woher die Aufgaben kommen? Gehoeren sie zu einem speziellen Thema? For allem der Term [mm] $n-\varphi(n)$ [/mm] bekommt man nicht in den Griff.
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:10 Mi 03.11.2010 | | Autor: | wauwau |
ja auf das bin ich auch gekommen
darüberhinaus, wenn du n,p > 3 annimmst, kannst du auch noch schließen, dass $n [mm] \equiv [/mm] -1(6)$
ich beschäftige mit der Variaton von Produkten
Bei Summen ist alles ja einfach:
Verringert man jeden summanden um 1 verringert sich die Summe um die Anzahl der Summanden
Verringert man die Faktoren eines Produkts um eins, dann kommt man im Spezialfal von quadratfreien Zahlen eben auf [mm] $n-\varphi(n)$
[/mm]
|
|
|
| |
|
Hallo wauwau,
nach der ![[]](/images/popup.gif) allgemeinen Berechnungsformel der $ \varphi $-Funktion gilt doch:
[mm] \varphi(n)=n\produkt_{p|n}\left(1-\bruch{1}{p}\right)=n\produkt_{p|n}\bruch{p-1}{p}
[/mm]
Nun ist gegeben [mm] q^a=n-\varphi(n)=n\left(1-\produkt_{p|n}\bruch{p-1}{p}\right)
[/mm]
Ich habe mal die Variable p aus der Aufgabenstellung in q umbenannt, damit die Gleichung leserlich bleibt, auch wenn das hier nicht unbedingt nötig wäre. Natürlich müsste sie dann auch in der zweiten gegebenen Gleichung umbenannt werden.
Was heißt das für die Struktur von n?
Im Zusammenhang mit der anderen Gleichung, in der ja eine Aussage über $ [mm] n+\blue{2} [/mm] $ getroffen wird, kannst Du doch ermitteln, dass q ein Teiler von 2 sein muss. Und das erfüllt nur eine einzige Primzahl. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:21 Mi 03.11.2010 | | Autor: | wauwau |
Also diesen zusammenhang sehe ich nicht - bitte um nähere Erläuterung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:48 Mi 03.11.2010 | | Autor: | reverend |
Hallo wauwau,
ich steige gerade nicht durch meinen vorhin angelegten Zettel durch. :-(
...und bin jetzt auch erstmal bis zum Abend vorwiegend unterwegs. Dann mehr. Zwischendurch schaue ich aber mal kurz rein.
Ich bin von der Teilerstruktur von n ausgegangen. Die erste Gleichung gibt dazu ja ein paar Hinweise. Im Moment steige ich aber durch meine Fallunterscheidung nicht mehr durch. Sorry. Wie gesagt, später.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 11.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:21 Mi 03.11.2010 | | Autor: | felixf |
Moin!
> Nun ist gegeben
> [mm]q^a=n-\varphi(n)=n\left(1-\produkt_{p|n}\bruch{p-1}{p}\right)[/mm]
Und das kann man noch zu [mm] $q^a [/mm] = [mm] \frac{n \left( \prod_{p\mid n} p - \prod_{p\mid n} (p - 1) \right)}{\prod_{p\mid n} p}$ [/mm] umschreiben. Ist $n = [mm] \prod_{i=1}^t p_i^{e_i}$ [/mm] (mit paarweise verschiedenen Primzahlen [mm] $p_i$), [/mm] so erhaelt man [mm] $q^a [/mm] = [mm] \prod_{i=1}^t p_i^{e_i - 1} \left( \prod_{p\mid n} p - \prod_{p\mid n} (p - 1) \right)$.
[/mm]
Man sieht also: ist [mm] $e_i [/mm] > 1$, so ist [mm] $p_i$ [/mm] ein Teiler von [mm] $q^a$, [/mm] womit $q = [mm] p_i$ [/mm] ist. Der einzige Primfaktor, der also mehrfach in $n$ vorkommen kann, ist $q$.
Angenommen, $n$ ist nicht quadratfrei. Aus $n + 2 = [mm] q^b$ [/mm] folgt dann, dass $2$ durch $q$ teilbar ist, also $q = 2$.
Fuer $n$ quadratfrei komme ich jedoch nicht weiter...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:54 Fr 05.11.2010 | | Autor: | wauwau |
so gehts mir schon seit Tagen.....
|
|
|
|
