zahlentheoretische Fragen

19.12.2006, 13:55	piloan	Auf diesen Beitrag antworten »
zahlentheoretische Fragen hi jungs... ich soll einmal kongruenzen fuer das Legendre Symbol berechnen ... nun habe ich erstmal eine Frage wie ich darauf komme,dass die Kongruenzen zu 1 oder -1 kongruent sind ...komme da rechnerisch nicht drauf weil der exponent so hoch ist... $\begin{eqnarray} 5^{11} \equiv ? (mod23) \end{eqnarray}$ und $\begin{eqnarray} 17^{15} \equiv ? (mod31) \end{eqnarray}$ $\begin{eqnarray} 241^{128} =(241^2)^{2^6}\equiv(-1)^{2^6} \equiv 1 (mod 257) \end{eqnarray}$ bei dem letzten bin ich auf eine vernuenftige umformung gekommen , bei den ersten beiden wuerde ich das sonst mit dem taschenrechner ausrechnen gruß
19.12.2006, 14:06	20_Cent	Auf diesen Beitrag antworten »
$\begin{eqnarray} 5^{11} = 5 5^{10} \end{eqnarray*}$ vllt nützt dir das was.
19.12.2006, 14:18	AD	Auf diesen Beitrag antworten »
Es gibt immer nette Umformungen, wenn man weiß, wonach man sucht, z.B. $\begin{eqnarray} 17^{15} \equiv (17-6\cdot 31)^{15} = (-169)^{15} = -13^{30} \equiv -1\mod 31 \end{eqnarray}$ nach Fermat. EDIT: Bei den anderen beiden Aufgaben kann man übrigens ähnlich vorgehen: $\begin{eqnarray} 5^{11} \equiv (5-3\cdot 23)^{11} = (-64)^{11} = -8^{22} \equiv -1\mod 23 \end{eqnarray}$ $\begin{eqnarray} 241^{128} \equiv (241-257)^{128} = (-16)^{128} = 4^{256} \equiv 1\mod 257 \end{eqnarray}$
22.12.2006, 13:49	piloan	Auf diesen Beitrag antworten »
hi soll hier zeigen, $\begin{eqnarray} p=2^{2^n}+1 \end{eqnarray}$ ist Fermatsche Primzahl. ZZ a ist genau dann Primitivwurzel wenn gilt $\begin{eqnarray} (\frac{a}{b})=-1 \end{eqnarray}$ das soll das Legendre Symbol sein nun hab ich $\begin{eqnarray} a^{\frac{2^{2^n}+1-1}{2}}= a^{\frac{2^{2^n}}{2}}=a^{2^{2^n}-2^{-1}} \end{eqnarray}$ nun muss ich ja beide richtungen zeigen.....der hiwi meinte eine Primitivwurzel $\begin{eqnarray} a \end{eqnarray}$ $\begin{eqnarray} a^{2k} \end{eqnarray}$ ist immer kongruent zu 1 ...aber das kann doch net sein oder ??
22.12.2006, 14:00	20_Cent	Auf diesen Beitrag antworten »
was ist denn b?
22.12.2006, 14:02	piloan	Auf diesen Beitrag antworten »
b= p sorry
Anzeige

22.12.2006, 15:53	AD	Auf diesen Beitrag antworten »
Deine Exponentenumformung ist mehr als merkwürdig... Nach Potenzgesetzen gilt jedenfalls $\begin{eqnarray} \frac{2^{2^n}}{2} = 2^{2^n-1} \end{eqnarray}$ Zum Problem: Kennst du die Darstellung $\begin{eqnarray} \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \mod p \end{eqnarray}$ für ungerade Primzahlen und $\begin{eqnarray} p\not \| a \end{eqnarray}$ ? Falls ja, dann ist ja nur noch ein kleiner Schritt zu tun. Siehe z.B. hier oder dort.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »