Aussagen zeigen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:16 Fr 14.01.2011 | | Autor: | SolRakt |
| Aufgabe | Für n [mm] \in \IN [/mm] ist j(n) = |{0 [mm] \le [/mm] m < n | ggT(m;n) = 1}. Seien p [mm] \not= [/mm] q Primzahlen. Zeigen Sie:
a) [mm] j(p^{2}) [/mm] = (p-1)p
b) j(pq) = (p-1)(q-1) |
Hallo. Kann mir vllt jemand helfen.
Bei der a) würde ja gelten:
0 [mm] \le [/mm] m < [mm] p^{2}
[/mm]
Aber was soll mir das sagen?
Oder fange ich falsch an?
Danke.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:53 Fr 14.01.2011 | | Autor: | Lippel |
Hallo,
> a) [mm]j(p^{2})[/mm] = (p-1)p
>
> b) j(pq) = (p-1)(q-1)
> Hallo. Kann mir vllt jemand helfen.
>
> Bei der a) würde ja gelten:
>
> 0 [mm]\le[/mm] m < [mm]p^{2}[/mm]
Stimmt.
> Aber was soll mir das sagen?
Überlege dir das ganze doch erstmal anhand von einem Beispiel. Nehmen wir $p [mm] =5\:$
[/mm]
Dann ist [mm] $j(p^2)$ [/mm] die Anzahl der Zahlen zwischen 0 und 24, deren ggT mit 25 gerade 1 ist. Das sind alle außer 0, 5, 10, 15 und 20. Also ist [mm] $j(p^2) [/mm] = 25 - 5 =20$. Und das ist gerade das gleiche wie: $(p-1)p=4*5=20$.
Hilft dir das schon weiter? Du musst es jetzt allgemeiner formulieren.
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:01 Fr 14.01.2011 | | Autor: | SolRakt |
Hmm..ich bin mir nicht sicher.
Setze man p:=a
Dann bezeichne j(n) die Anzahl der Zahlen zwischen 0 [mm] \le [/mm] a < [mm] a^{2}, [/mm] deren ggT(a, [mm] p^{2}) [/mm] gerade 1 ist.
Nur wie schreibt man das jetzt allgemein mit dem ggT?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:15 Fr 14.01.2011 | | Autor: | Lippel |
Hallo,
> Setze man p:=a
>
> Dann bezeichne j(n) die Anzahl der Zahlen zwischen 0 [mm]\le[/mm] a
> < [mm]a^{2},[/mm] deren ggT(a, [mm]p^{2})[/mm] gerade 1 ist.
Das macht mal keinen Sinn, damit wäre a ja fest, aber du sollst ja alle Zahlen zwischen 0 und [mm] $p^2$ [/mm] betrachten.
Du suchst alle $m [mm] \in \IZ: [/mm] 0 [mm] \leq [/mm] m < [mm] p^2$ [/mm] und [mm] $ggT(m,p^2)=1$
[/mm]
Die Teiler von [mm] p^2 [/mm] sind [mm] $\{1,p,p^2\}$
[/mm]
Was muss m also erfüllen, damit m einen gemeinsamen Teiler mit [mm] $p^2$ [/mm] hat, der im oben genannten Bereich liegt?
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:18 Fr 14.01.2011 | | Autor: | SolRakt |
Danke.
m dürfte dann nicht gleich [mm] p^{2} [/mm] oder p sein, sonst wäre der ggT nicht 1, oder? Aber wie kommt man damit jetzt auf die zu zeigende Gleichung?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:23 Fr 14.01.2011 | | Autor: | Lippel |
> Danke.
>
> m dürfte dann nicht gleich [mm]p^{2}[/mm] oder p sein, sonst wäre
> der ggT nicht 1, oder? Aber wie kommt man damit jetzt auf
> die zu zeigende Gleichung?
Wir hatten doch $0 [mm] \leq [/mm] m < [mm] p^2$, [/mm] also darf m sowieso nicht [mm] $p^2$ [/mm] sein. Dass es nicht p sein darf ist richtig, es gibt aber noch mehr Zahlen. Denke mal an das Beispiel mit p=5 zurück. Es war richtig, dass m nicht 5 sein darf, aber auch nicht 0, 10, 15, 20, d.h. Vielfache von 5 , die im Bereich zwischen 0 und [mm] $p^2$ [/mm] liegen kommen auch nicht infrage.
Das musst du jetzt nur noch formal aufschreiben.
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:29 Fr 14.01.2011 | | Autor: | SolRakt |
Hmm..sry, bin nur grad was verwirrt. xD Wie schreibt man sowas den formal auf?
m darf kein Vielfaches von p sein, denn sonst wäre ggT(np, [mm] p^{2}) [/mm] = p
Ausnahme: p=1, muss man zusätzlich behandeln, oder?
m darf nicht [mm] p^{2} [/mm] sein, denn sonst wäre [mm] ggT(p^{2}, p^{2}) [/mm] = [mm] p^{2}
[/mm]
Aber kann ich jetzt einfach behaupten, dass alle anderen Zahlen ok sind? Und ist das überhaupt richtig bisher? Wie käme ich dann aber auf die Gleichung?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:46 Fr 14.01.2011 | | Autor: | Lippel |
> Hmm..sry, bin nur grad was verwirrt. xD Wie schreibt man
> sowas den formal auf?
Also die Anzahl der Zahlen m mit $0 [mm] \leq [/mm] m < [mm] p^2$ [/mm] ist gerade [mm] $p^2$, [/mm] da m auf jeden Fall in [mm] $\{0, 1, \ldots, p^2-1\}$ [/mm] liegt. Suchen wir nun die Elemente $n [mm] \in \{0, 1, \ldots, p^2-1\}$, [/mm] für die gilt: [mm] $ggT(n,p^2)\not=1$. [/mm] Da die Menge der Teiler von [mm] $p^2$ [/mm] gegeben ist durch [mm] $\{1,p,p^2\}$ [/mm] muss [mm] $ggT(n,p^2)=p$ [/mm] gelten, da n nach Vor. kleiner als [mm] $p^2$ [/mm] und der ggT nicht 1 sein soll. Damit liegt n in der Menge [mm] $\{0, p, 2p, (p-1)p\}$. [/mm] Diese hat genau p Elemente.
Die Anzahl der gesuchten Elemente ist also nun [mm] $p^2-p [/mm] = (p-1)p$, nämlich alle Elemente aus [mm] $\{0, 1, \ldots, p^2-1\}$ [/mm] minus die, für die [mm] $ggT(n,p^2)\not=1$ [/mm] gilt.
>
> m darf kein Vielfaches von p sein, denn sonst wäre ggT(np,
> [mm]p^{2})[/mm] = p
>
> Ausnahme: p=1, muss man zusätzlich behandeln, oder?
1 ist keine Primzahl.
>
> m darf nicht [mm]p^{2}[/mm] sein, denn sonst wäre [mm]ggT(p^{2}, p^{2})[/mm]
> = [mm]p^{2}[/mm]
m ist per Definition kleiner als [mm] $p^2$
[/mm]
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:52 Fr 14.01.2011 | | Autor: | SolRakt |
Sry, aber so ganz versteh ich das immer noch nicht.
> Damit liegt n in der Menge $ [mm] \{0, p, 2p, (p-1)p\} [/mm] $. Diese hat genau p
> Elemente.
Ab diesem Satz komme ich nicht mehr weiter. Wie kommst du darauf? Tut mir leid, wenn ich wieder nachfragen muss. Danke aber für deine Hilfe.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:06 Fr 14.01.2011 | | Autor: | Lippel |
> Sry, aber so ganz versteh ich das immer noch nicht.
>
> > Damit liegt n in der Menge [mm]\{0, p, 2p, (p-1)p\} [/mm]. Diese hat
> genau p
> > Elemente.
Das liegt daran, dass n ja ein Vilefaches von p sein muss, aber eben auch nicht größer als [mm] $p^2$ [/mm] sein darf. Du suchst einfach die Vielfachen von p aus der Menge [mm] $\{0,1,\ldots,p^2-1\}$ [/mm] heraus, das sind genau die, die ich oben hingeschrieben habe, und es sind offenbar p stück.
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:07 Sa 15.01.2011 | | Autor: | SolRakt |
Geht die b) dann so (?) (salopp aufgeschrieben):
0 [mm] \le [/mm] m < pq
m [mm] \in [/mm] {0,1,...,pq-1}
Suche n [mm] \in [/mm] {0,1,...,pq-1} mit ggT(n,pq) [mm] \not= [/mm] 1
Menge der Teiler von pq durch {1,p,q} ... 1 geht nach Vor. nicht
es muss ggT(n,pq) = p oder ggT(n,pq) = q gelten
also folgt n [mm] \in [/mm] {0,p,2p,(p-1)p,q, 2q, (q-1)q}
Dies hat genau p+q Elemente
Also folgt die Behauptung
So ungefähr ok. Dein text bei der a war ja schon perfekt. Kann man dann ja ähnlich formulieren. Stimmts denn?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:04 So 16.01.2011 | | Autor: | Lippel |
Nabend,
> Geht die b) dann so (?) (salopp aufgeschrieben):
>
> 0 [mm]\le[/mm] m < pq
>
> m [mm]\in[/mm] {0,1,...,pq-1}
>
> Suche n [mm]\in[/mm] {0,1,...,pq-1} mit ggT(n,pq) [mm]\not=[/mm] 1
>
> Menge der Teiler von pq durch {1,p,q} ... 1 geht nach Vor.
> nicht
>
> es muss ggT(n,pq) = p oder ggT(n,pq) = q gelten
>
> also folgt n [mm]\in[/mm] {0,p,2p,(p-1)p,q, 2q, (q-1)q}
Hier ist ein Fehler, die obere Schranke der Menge ist pq, also muss gelten:
$n [mm] \in \{0,p,2p,\ldots,(\red{q}-1)p,q, 2q,\ldots,(\red{p}-1)q\}$
[/mm]
> Dies hat genau p+q Elemente
Nein, es sind p+q-1, nämlich q-1 echte Vielfache von p und p-1 echte Vielfache von q und dann eben die 0, also [mm] $(p-1)+(q-1)+1=p+q-1\:$
[/mm]
Damit folgt für die Gesamtzahl: [mm] n(pq)=pq-(p+q-1)=pq-p-q+1=(p-1)(q-1)\:$
[/mm]
>
> Also folgt die Behauptung
Nach deiner Rechnung ja eigentlich nicht. Dass dir das nicht auffällt...
LG Lippel
|
|
|
|
