Arithmetik

Neue Frage »

Billi Auf diesen Beitrag antworten »
Arithmetik
n aus N
n > 1,
S: = E d, d aus N, d<n, ggt(d,n)=1
> S = n * phi (n) / 2

Betrachten Sie einige Beispiele. Die zu n teilerfremden Zahlen treten immer "paarweise" auf.
AD Auf diesen Beitrag antworten »
RE: Arithmetik
Du drückst dich etwas unverständlich aus! d und n sind natürliche Zahlen mit ggT(d,n)=1 und phi(n) ist wahrscheinlich die Eulersche phi-Funktion.

Aber was soll "S: = E d" bedeuten und was schließlich "> S = n * phi (n) / 2" ???
Billi Auf diesen Beitrag antworten »

also dieses E ist so'n Summenzeichen, dat gibts hier aber nicht,
und wat S genau sein soll, weiß ich auch nicht.

jedenfalls folgt daraus, dass S= n * phi (n) / 2
AD Auf diesen Beitrag antworten »

Meinst du vielleicht

?
Billi Auf diesen Beitrag antworten »

also da stand zwar S, aber so sieht dat ganz gut aus! smile
AD Auf diesen Beitrag antworten »

OK, ich meinte ja auch und dann die Aufgabenstellung: Beweisen Sie .

Zum Beweis ist folgende Aussage hilfreich:

d ist genau dann teilerfremd zu n, wenn auch (n-d) teilerfremd zu n ist.

Dann musst du "nur" noch über beide Ausdrücke so wie oben summieren.
 
 
Billi Auf diesen Beitrag antworten »

also irgendwie versteh ich die Aufgabe gar nicht!
Also S ist d oder wie? oder was heißt dieses komische Zeichen?
AD Auf diesen Beitrag antworten »

Wenn du mit "komischen Zeichen" das Summensymbol meinst, dann frage ich mich, wie du zu so einer anspruchsvollen Aufgabe vordringen konntest, ohne dieses durchaus übliche Symbol jemals gesehen zu haben. Aber vielleicht kennst du es bisher nur in der Form

Billi Auf diesen Beitrag antworten »

ja, das zeichen kenn ich schon, aber weiß net, was es in diesem Zusammenhang genau bedeuten soll und was man genau beweisen soll
AD Auf diesen Beitrag antworten »

Das hast du doch ganz oben beschrieben! Ich habe es doch nur in Formelsprache übersetzt.

Wenn es dir gesprochen besser gefällt:
S ist die Summe aller natürlichen Zahlen d kleiner als n, die zur Zahl n teilerfremd sind.

Zu beweisen ist jetzt einfach die Formel



wobei die Eulersche -Funktion die Anzahl der zu n teilerfremden natürlichen Zahlen kleiner gleich n bezeichnet.

Was ist an der Aufgabenstellung unverständlich?
Billi Auf diesen Beitrag antworten »

Ah, jetzt hab ichs verstanden! Hatte das nicht kapiert, dat S die Summe aller natürlichen Zahlen d kleiner n ist, die zu n teilerfremd sind.
Dankeschön! smile
AD Auf diesen Beitrag antworten »

OK. Und zu meiner Beweisskizze oben führe ich mal das Beispiel n=20 an:

Die Primfaktorzerlegung ist 20=2²*5, also ist phi(20)=(2-1)*2*(5-1)=8.
Die 8 zu 20 teilerfremden Zahlen kleiner oder gleich 20 sind:

1, 3, 7, 9, 11, 13, 17, 19 <-- das sind die "d", über die summiert wird

Und wie ich oben angemerkt habe, jetzt zu jedem d der Wert (n-d):

19, 17, 13, 11, 9, 7, 3, 1 <-- das sind jetzt die "n-d"

Fällt dir was auf beim Vergleich beider Folgen?
Billi Auf diesen Beitrag antworten »

ja, wenn man weiß, dass die zu n teilerfremden Zahlen immer paarweise auftreten, also d zu n-d, dann ist das ja nicht mehr schwer.
Aber muss man auch noch wissen, warum die teilerfemden zahlen immer paarweise auftreten, oder kann man das einfach aus Beipielen begründen?
AD Auf diesen Beitrag antworten »

Naja - es gibt ja Rechenregeln für den größten gemeinsamen Teiler (nicht nur für natürliche, sondern ganze Zahlen):

Klar ist die Vertauschung ggT(a,b)=ggT(b,a) und auch der Vorzeichenwechsel ggT(a,b)=ggT(a,-b). Wichtig ist aber vor allem die Gültigkeit von

ggT(a,b)=ggT(a,b+k*a)

für beliebige ganze Zahlen k (wird beim Euklidischen Algorithmus genutzt).

Und nun benutze ich diese Eigenschaft, indem ich a = n, b = n-d und k=-1 setze:

ggT(n,n-d)=ggT(n,n-d+(-1)*n)=ggT(n,-d)=ggT(n,d)

Das heißt, es gilt:

ggT(n,d)=1 genau dann wenn ggT(n,n-d)=1

Und das ist der Beweis, den du suchst.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »