Primitivwurzeln

11.12.2006, 14:48

piloan

Auf diesen Beitrag antworten »

Primitivwurzeln

hi
ich soll nun alle Primitivwurzeln mod 31 rausfinden.

nun da ich 31 eine Primzahl ist,weiss ich das ueberhaupt Primitivwurzeln existieren.

dann weiss ich auch ,dass

$\begin{eqnarray*} \varphi(\varphi( 31))=6 \end{eqnarray*}$ es somit 6 Primitvwurzeln gibt.

nun habe bleiben 30 zahlen zum ueberpruefen.
jetzt habe ich a=3 ueberprueft und es ist eine Primitivwurzel
nun haben wir den satz gehabt, falls

$\begin{eqnarray*} g \end{eqnarray*}$ primitvwurzel ist dann ist auch $\begin{eqnarray*} g^r \end{eqnarray*}$ Primitivwurzel falls

$\begin{eqnarray*} ggT(r,\varphi(31))=1 \end{eqnarray*}$ das trifft ja zb fuer r=7 zu ....dann waere

$\begin{eqnarray*} 3^7=2187 mod(31) =17 mod(31) \end{eqnarray*}$ ...ist das richtig und bekomme ich so meine 6 zusammen ....sonst waer das ja echt ober viel arbeit ..

gruß Wink

Wink

11.12.2006, 14:58

AD

Auf diesen Beitrag antworten »

RE: Primitivwurzeln
$\begin{eqnarray*} \varphi(\varphi(31)) = \varphi(30) = \varphi(2\cdot 3\cdot 5) = 1\cdot 2\cdot 4 = 8 \end{eqnarray*}$

11.12.2006, 15:03

piloan

Auf diesen Beitrag antworten »

ja meine ich auch...und der rest ist ok ?

dann waeren naemlich

$\begin{eqnarray*} 3^7,3^{11},3^{13},3^{17},3^{19},3^{23},3^{29} \end{eqnarray*}$ Primitivwurzeln...

gibt es eigentlich ein Programm oder aehnliches der mir schnell sagen kann ,was
$\begin{eqnarray*} 3^{11} mod 31 \end{eqnarray*}$ ist?

11.12.2006, 15:05

AD

Auf diesen Beitrag antworten »

Ja.

11.12.2006, 15:06

piloan

Auf diesen Beitrag antworten »

hatte noch edit gemacht =)

11.12.2006, 16:07

therisen

Auf diesen Beitrag antworten »

Hallo,

deine Frage ist so schlecht gestellt, dass Arthurs Beitrag, der diesen schon davor geschrieben hat, deine Frage trotzdem beantwortet. Das ist genauso wie viele Leute fagen: "Wissen Sie, wie viel Uhr es ist?". Man antwortet einfach "Ja" und fertig Augenzwinkern

Augenzwinkern

Vermutlich willst du wissen, welches Programm das z.B. kann. Ich empfehle das kostenlose GAP (ein sehr mächtiges Algebra-Programm).

Gruß, therisen

Anzeige

11.12.2006, 16:12

piloan

Auf diesen Beitrag antworten »

ne mein jung ....ich hatte die Frage nach dem Programm in meine Antwort editiert und somit konnte arthur nicht sehen, dass ich noch etwas zugefuegt hatte (deswegen mein post : hatte was editiert). Die Antwort "ja" bezieht sich auf den anderen Teil....ich glaube,dass ich gerade noch in der Lage bin meine Fragen richtig zu stellen .
Gruß

11.12.2006, 16:18

therisen

Auf diesen Beitrag antworten »

Selbst wenn Arthur deinen neuen Beitrag gelesen hat, warum hätte er seinen Beitrag ändern sollen? Du hast zwei Ja/Nein Fragen gestellt und beide kann man mit Ja beantworten. Ich bereue fast schon, dass ich mehr getan habe als nötig (und dir ein Programm genannt habe)...

EDIT: Hier ein Link, damit du siehst, was ich meine: Latex ins eigene Forum integrieren

11.12.2006, 17:00

AD

Auf diesen Beitrag antworten »

Amüsant, was aus so einer kleinen "Ja"-Antwort so alles werden kann. Big Laugh

Big Laugh

Bezog sich natürlich nur auf die erste Zeile von piloan, mehr stand auch nicht da, als ich diese Antwort gab.

11.12.2006, 17:08

piloan

Auf diesen Beitrag antworten »

aha ....
hi arthur
also habe das hinbekommen ....und konnte die $\begin{eqnarray*} 3^r \end{eqnarray*}$ bequem ausrechnen ...hatte ja schon bewiesen,das 3 Primitivwurzel ist.

nun soll ich andersrum zeigen,dass es genau 6 n gibt,s.d. mod n 8 Primitivwurzeln besitzt.

heisst quasi

$\begin{eqnarray*} \varphi(\varphi(n))=8 \end{eqnarray*}$

das waer nach def

$\begin{eqnarray*} \varphi(n) \prod_{p|\varphi(n)}~(1-\frac{1}{p})=8 \end{eqnarray*}$

(genau das wollte ich damit sagen ,was arthur meint ...meinte nix boese Augenzwinkern

Augenzwinkern

)

11.12.2006, 18:20

AD

Auf diesen Beitrag antworten »

Keine leichte Sache, solche "inversen" $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Betrachtungen. Irgendwelche Ideen?

11.12.2006, 18:34

Menelaos

Auf diesen Beitrag antworten »

Hmm.

Big Laugh

Zitat:

Original von therisen
Selbst wenn Arthur deinen neuen Beitrag gelesen hat, warum hätte er seinen Beitrag ändern sollen? Du hast zwei Ja/Nein Fragen gestellt und beide kann man mit Ja beantworten. Ich bereue fast schon, dass ich mehr getan habe als nötig (und dir ein Programm genannt habe)...

EDIT: Hier ein Link, damit du siehst, was ich meine: Latex ins eigene Forum integrieren

Von derartigen Reaktionen halte ich persönlich wenig. Es gab in der Vergangenheit einige Menschen, welche die Ansicht vertraten, dass sich viele philosophische Probleme lediglich auf sprachliche Missverständnisse zurückführen lassen - und dem kann man durchaus etwas entgegenwirken. Denn letztendlich ist der Mensch keine Maschine, die sprachlich vollkommen in sich schlüssige Sätze auf logischem Fundament generiert, sondern ein durch und durch fehlbares Wesen. Und gerade das macht uns doch zum Menschen (auch wenn der Mathematiker es sicherlich anders lieber hätte). Von daher halte ich deratige Antworten in Anbetracht der Tatsache, dass der Antwortende das Streben des Fragenden durchschaut hat, für absolut sinnfrei.

11.12.2006, 18:37

piloan

Auf diesen Beitrag antworten »

ich weiss,dass

$\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ die Anzahl der Einheiten im Restklassenring Z/nZ angibt. und dann muss fuer eine Einheit a zb gelten es gibt ein b mit ab=1

$\begin{eqnarray*} a*b\equiv1 (mod n) \end{eqnarray*}$

aber mir fehlt der zusammenhang...da mir klar ist,das ich 8 Einheiten habe aber auf kein n stoße ausser durch probieren

11.12.2006, 19:30

AD

Auf diesen Beitrag antworten »

Der erste Schritt ist zu zeigen, dass für $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ nur die Werte 16, 20, 24 oder 30 in Frage kommen. Das gelingt dadurch, dass wegen $\begin{eqnarray*} \varphi(\varphi(n))=8=2^3 \end{eqnarray*}$ durch entsprechende Faktorisierung nur Primfaktoren 2,3 und 5 in $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ in Frage kommen, dabei 3 und 5 höchstens einfach. Wie groß dann noch die enthaltene Zweierpotenz ist, kann man leicht feststellen. Der vermeintlich mögliche Wert $\begin{eqnarray*} \varphi(n)=15 \end{eqnarray*}$ kommt nicht in Frage: Der einzige mögliche ungerade Funktionswert von $\begin{eqnarray*} \varphi \end{eqnarray*}$ ist $\begin{eqnarray*} \varphi(2)=1 \end{eqnarray*}$ .

Nur Werte $\begin{eqnarray*} n=2,4,p^k,2p^k \end{eqnarray*}$ mit ungeraden Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ besitzen primitive Wurzeln. Wegen $\begin{eqnarray*} \varphi(\varphi(2))=\varphi(\varphi(4))=1 \end{eqnarray*}$ können wir uns auf die letzte Gruppe konzentrieren: $\begin{eqnarray*} \varphi(p^k) = \varphi(2p^k) = p^{k-1}(p-1) \end{eqnarray*}$ ...

Wie ich schon sagte, sehr mühsam. Aber einen anderen Weg kenne ich nicht.

P.S.: Die Gleichung $\begin{eqnarray*} \varphi(\varphi(n))=8 \end{eqnarray*}$ besitzt übrigens viel mehr Lösungen als nur 6 Stück. Aber die meisten davon sind Module, wo es keine primitiven Wurzeln gibt, z.B. $\begin{eqnarray*} n=33 \end{eqnarray*}$ .

11.12.2006, 23:18

piloan

Auf diesen Beitrag antworten »

da werde ich mich morgen noch mal ransetzen...
brauche noch mal einen tipp

wenn ich zeigen soll .dass

$\begin{eqnarray*} \sum_{n=1}^{p-1}~k^n \equiv 0 (mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1 \end{eqnarray*}$ n nicht teilt

oder

$\begin{eqnarray*} \sum_{n=1}^{p-1}~k^n \equiv -1(mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1|n \end{eqnarray*}$

hierzu soll ich eine Primitivwurzel mod p nehmen...habe schon versucht es anzufangen aber braeuchte mal einen wink in die richtige richtung

11.12.2006, 23:20

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
wenn ich zeigen soll .dass

$\begin{eqnarray*} \sum_{n=1}^{p-1}~k^n \equiv 0 (mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1 \end{eqnarray*}$ n nicht teilt

oder

$\begin{eqnarray*} \sum_{n=1}^{p-1}~k^n \equiv -1(mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1|n \end{eqnarray*}$

Das ist Unsinn, denn n ist doch nur der Summenindex - an den kannst du keine Bedingungen stellen. Meinst du vielleicht

(p-1) teilt/teilt nicht k

?

11.12.2006, 23:24

piloan

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
da werde ich mich morgen noch mal ransetzen...
brauche noch mal einen tipp

wenn ich zeigen soll .dass

$\begin{eqnarray*} \sum_{k=1}^{p-1}~k^n \equiv 0 (mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1 \end{eqnarray*}$ n nicht teilt

oder

$\begin{eqnarray*} \sum_{k=1}^{p-1}~k^n \equiv -1(mod)p \end{eqnarray*}$ wenn $\begin{eqnarray*} p-1|n \end{eqnarray*}$

hierzu soll ich eine Primitivwurzel mod p nehmen...habe schon versucht es anzufangen aber braeuchte mal einen wink in die richtige richtung

srz schon so spaet smile

smile

...die summe laeuft von k bis p-1

11.12.2006, 23:28

AD

Auf diesen Beitrag antworten »

Das zweite ist einfach mit Fermat; beim ersten muss ich auch noch ein bissel nachdenken. verwirrt

verwirrt

11.12.2006, 23:35

piloan

Auf diesen Beitrag antworten »

Ich seh momentan auch net was das mitm fermat zu tun hat ....also
n=(p-1)* weitere Primzahlen....
ach ich glaube ich muss erstmal ins bettchen ...melde mich dann morgen wieder
gute nacht und dankeschoen Wink

Wink

11.12.2006, 23:42

AD

Auf diesen Beitrag antworten »

Na, mit n=s(p-1) folgt doch $\begin{eqnarray*} k^n = (k^{p-1})^s \equiv 1\mod p \end{eqnarray*}$ für alle $\begin{eqnarray*} k=1,\ldots,p-1 \end{eqnarray*}$ , das muss man sehen!

Und bei 1. habe ich den Hinweis nicht gelesen: Mit Primitivwurzel $\begin{eqnarray*} g \end{eqnarray*}$ durchläuft ja $\begin{eqnarray*} g^j \end{eqnarray*}$ für $\begin{eqnarray*} j=0,1,\ldots,p-2 \end{eqnarray*}$ alle primen Restklassen modulo $\begin{eqnarray*} p \end{eqnarray*}$ , also gilt gerade

$\begin{eqnarray*} \sum\limits_{k=1}^{p-1} k^n \equiv \sum\limits_{j=0}^{p-2} (g^j)^n = \sum\limits_{j=0}^{p-2} g^{jn} = \sum\limits_{j=0}^{p-2} (g^n)^j\mod p \end{eqnarray*}$

12.12.2006, 13:07

piloan

Auf diesen Beitrag antworten »

hi

also den 2. teil hab ich

beim 1. bin ich noch am ueberlegen

wenn

$\begin{eqnarray*} ggT(n,\varphi(p))=ggT(n,p-1)=1 \end{eqnarray*}$ dann ist

$\begin{eqnarray*} g^n \end{eqnarray*}$ eine Primitivwurzel und $\begin{eqnarray*} (g^n)^j \end{eqnarray*}$ erzeugt wieder alle primen Resklassen ...wenn ich dann die summe bilde kann ich die summanden quasi umordnen und die Summe des ersten und letzten,zweiten und vorletzten usw usw ergeben jeweils immer

$\begin{eqnarray*} p\equiv 0(modp) \end{eqnarray*}$

nur was mach ich wenn der ggt nicht =1 ist?

hatte gedacht ich zerlege

$\begin{eqnarray*} n=s*l, p-1=t*l \end{eqnarray*}$

dann hab ich ja
$\begin{eqnarray*} (g^{s*l})^j=(g^s)^{l*j} \end{eqnarray*}$ somit waer $\begin{eqnarray*} g^s \end{eqnarray*}$ wieder Primitivwurzel ...
aber hier haenge ich dann bei l*j

gruß

12.12.2006, 13:14

AD

Auf diesen Beitrag antworten »

Primitivwurzel ist $\begin{eqnarray*} g^n \end{eqnarray*}$ i.a. nicht, da hast du Recht. Aber im Fall $\begin{eqnarray*} (p-1)\not | n \end{eqnarray*}$ gilt zumindest $\begin{eqnarray*} g^n\not\equiv 1\mod p \end{eqnarray*}$ , und das reicht. Tipp: Summe geometrischer Folge

12.12.2006, 14:07

piloan

Auf diesen Beitrag antworten »

ok dann hab ich

$\begin{eqnarray*} \frac{(g^n)^{p-1}-1}{g^n-1}=\frac{(g^{\varphi(p)})^{n}-1}{g^n-1}\equiv \frac{1^n-1}{g^n-1} \end{eqnarray*}$

und das wars?

habe uebrigens den kram rueckwaerts gerechnet und da muss man ja andauernd zu große primzahlen bzw 2-er Potenzen ausschließen. Ich hoffe, das reicht dem Prof..aber sollte ja mathematisch korrekt sein .... Augenzwinkern

Augenzwinkern

12.12.2006, 14:50

AD

Auf diesen Beitrag antworten »

Ja, das war's - weil der Nenner ungleich 0 modulo p ist.

12.12.2006, 16:15

piloan

Auf diesen Beitrag antworten »

super
und komm ich mit dem ansatz weiter...

ZZ

a,b teilerfremd zu m
a,b in den ganzen Zahlen
m in den natuerlichen

$\begin{eqnarray*} ord_m ab=(ord_ma)*(ord_mb) \end{eqnarray*}$

fuer $\begin{eqnarray*} ggT(ord_ma,ord_mb)=1 \end{eqnarray*}$

$\begin{eqnarray*} ord_mab=x \end{eqnarray*}$ dann gilt $\begin{eqnarray*} (ab)^x\equiv 1 (mod)m \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »