Ich habe es jetzt so gelöst, komme auf die selben Primitivwurzeln.
Jetzt stelle ich mir aber noch zwei Fragen.
1. Soll ich bei Primzahlen die PW berechnen, z.B. für 19, dann ist es ja Φ(19-1)=Φ(18)=6, gibt also 6 PW modulo 19.
Wenn ich die PW bei den anderen Zahlen n berechnen muss, muss ich immer Φ(Φ(n) rechnen, um die Anzahl der PW rauszubekommen?
2. Gibt es einen Trick/Möglichkeit einfacher mit den Potenzen zu rechnen? Ich kann mir zwar auf meinen Zettel die Potenzen von 2^k, 3^k,… schreiben, aber das dauert ja dann dennoch Ewigkeiten um es runter zu modden.
Würde ich jetzt hier 2^5≡3(25) rechnen, könnte ich für 2^10=2^5*2^5=3*3≡9(25) rechnen, aber bei 2^17 oder so, gibt es ja, meines Wissens nach, keine einfachere Alternative oder?
Text erkannt:
PW \( \bmod 25 \)
\( f(25)=5^{2} \)
\( =\left(5^{2}-5^{1}\right) \)
\( \begin{array}{l} P(P(25)=P(20)=2 \cdot 10 \\ 2.2 .5 \\ =2^{2} \cdot 5 \\ =\left(2^{2}-2^{1}\right) \cdot\left(5^{1}-5^{0}\right) \\ =(4-2) \cdot(5-1) \\ =2.4 \\ =8 \\ \end{array} \)
\( \rightarrow \) es gibt 8PW modulo 25
1. eine Pl bestimmen
Teiler von 20:1,2,4,5,10,20
Teilesfr. z) \( 25: 12,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,2223,24 \)
\( \begin{aligned} a=1 \quad 1^{1} & \equiv 1(25) \rightarrow \text { keine } P W \\ a=2 \quad 2^{1} & =2(25) \\ 2^{2} & =4(25) \\ 2^{4} & =16(25) \\ 2^{5} & =32 \equiv 7(25) \\ 2^{10} & =2^{5} \cdot 2^{5}=7 \cdot 7=49=-1(25 \\ 2^{20} & =2^{10} \cdot 2^{10}=(-1) \cdot(-1) \equiv 1(25) \quad \rightarrow 2 \text { ist eine PW mod } 25 \end{aligned} \)
Teilesfrend a 20:1,37,9,11,13,17,19
\( \begin{array}{l} 2^{1}=2 \quad(25) \\ 2^{3}=8(25) \\ 2^{7}=128 \equiv 3(25) \\ 2^{9}=12(25) \\ 2^{1}=2048=23(25) \\ 2^{13}=8192 \equiv 17(25) \\ 2^{17}=131072 \equiv 22(25) \\ 2^{11}=524288 \equiv 13(25) \end{array} \)
