Modulorechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:32 Fr 06.10.2006 | | Autor: | Aeolus |
| Aufgabe | | [mm]11^{181} \mod 27[/mm] |
Hi!
Bisher hab ich solche Aufgaben folgendermaßen gerechnet, es ist gut möglich, dass das Verfahren fehlerhaft ist und nur manchmal stimmt:
[mm]
\begin{matrix}
9^{32} &\mod& 14 \equiv 9^{32} \mod 2*7\\
9^{32} &\equiv& 9^{5*6} * 9^2 &\equiv &11 \mod 7\\
9^{32} &\equiv& 9^0 &\equiv & 1 \mod 2\\
&\Rightarrow& 9^{32} \equiv 1*11 \mod 14\\
\end{matrix}
[/mm]
In der 2. und 3. Zeile wende ich den kleinen Fermat'schen Satz an. Mit dem Verfahren komm ich aber bei o.g. Ausdruck nicht weiter. Ich vermute, es liegt daran, dass 27=3*3*3 ist und der Restsatz nicht anwendbar ist, da ggT(3,3) != 1? Kann ich das Verfahren in dem Fall ganz vergessen? Oder ist gar die Vorgehensweise an sich fehlerhaft?
(Ich weiß, dass es mit der schnellen Exponentiation, also Umwandlung von 32 in Binärsystem usw., hier schneller geht, nur würde ichs gerne anders lösen)
[Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.]
|
|
| |
|
Hallo,
man könnte die Frage ja umformulieren und sich fragen: Welchen Rest lässt [mm] 11^{181} [/mm] bei Division durch 27? Man könnte versuchen geeignet zu faktorisieren und den chinesischen Restsatz anzuwenden, aber das wird sehr umständlich. Schau dir mal den Anhang an. Da findest du Beispiele, die analog laufen.
Viele Grüße
Daniel
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:51 Fr 06.10.2006 | | Autor: | Aeolus |
Es müsste aber (hoffentlich  ) einen einfacheren Weg geben. Ich werd das Gefühl nicht los, da ist irgendein Trick bei der Aufgabe, denn es kommt als Ergebnis wieder 11 heraus. Die Rechnung kann eigentlich gar nicht aufwändig sein, die Aufgabe gab in der Klausur so gut wie keine Punkte, und ein Taschenrechner ist auch nicht erlaubt gewesen.
Erkennt möglicherweise jemand mit dem Wissen, dass 11 herauskommen soll, einen schnellen Lösungsweg?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:21 Sa 07.10.2006 | | Autor: | felixf |
Hallo!
> Es müsste aber (hoffentlich ) einen einfacheren Weg
> geben. Ich werd das Gefühl nicht los, da ist irgendein
> Trick bei der Aufgabe, denn es kommt als Ergebnis wieder 11
> heraus. Die Rechnung kann eigentlich gar nicht aufwändig
> sein, die Aufgabe gab in der Klausur so gut wie keine
> Punkte, und ein Taschenrechner ist auch nicht erlaubt
> gewesen.
Bei dieser konkreten Aufgabe geht es auch ganz einfach: Es ist naemlich $27 = [mm] 3^3$ [/mm] und somit [mm] $\phi(27) [/mm] = [mm] 3^2 \cdot [/mm] 2 = 18$ (Eulersche [mm] $\phi$-Funktion). [/mm] Nun ist $11$ teilerfremd zu $27$, und nach dem kleinen Satz von Fermat ist [mm] $11^{\phi(27)} \equiv [/mm] 1 [mm] \pmod{27}$.
[/mm]
Da $181 = 10 [mm] \cdot [/mm] 18 + 1$ ist, ist also [mm] $11^{181} [/mm] = [mm] (11^{18})^{10} \cdot [/mm] 11 [mm] \equiv 1^{10} \cdot [/mm] 11 = 11 [mm] \pmod{27}$.
[/mm]
Nachtrag: Bei [mm] $9^{32} \mod [/mm] 14$ hast du [mm] $\phi(14) [/mm] = 1 [mm] \cdot [/mm] 6 = 6$, und $9$ ist teilerfremd zu $14$. Somit ist [mm] $9^6 \equiv [/mm] 1 [mm] \pmod{14}$ [/mm] und somit [mm] $9^{32} [/mm] = [mm] (9^6)^5 \cdot 9^2 \equiv 1^5 \cdot [/mm] 81 [mm] \equiv [/mm] 11 [mm] \pmod{27}$. [/mm] Somit kannst du diese Aufgabe genauso loesen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:43 Sa 07.10.2006 | | Autor: | Aeolus |
Cool, vielen Dank! Wir hatten leider nur den speziellen kleinen Satz von Fermat mit p als Primzahl besprochen und der allgemeinerere Euler-Fermat war mir nicht bekannt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:38 Fr 06.10.2006 | | Autor: | felixf |
Hallo!
> [mm]11^{181} \mod 27[/mm]
> Hi!
>
> Bisher hab ich solche Aufgaben folgendermaßen gerechnet, es
> ist gut möglich, dass das Verfahren fehlerhaft ist und nur
> manchmal stimmt:
>
> [mm]
\begin{matrix}
9^{32} &\mod& 14 \equiv 9^{32} \mod 2*7\\
9^{32} &\equiv& 9^{5*6} * 9^2 &\equiv &11 \mod 7\\
9^{32} &\equiv& 9^0 &\equiv & 1 \mod 2\\
&\Rightarrow& 9^{32} \equiv 1*11 \mod 14\\
\end{matrix}
[/mm]
Ein Kommentar zu dieser Rechnung: Es mag ja sein dass das hier zufaellig klappt, aber im Allgemeinen kannst du nicht einfach die Ergebnisse modulo 2 und 7 zusammenmultiplizieren, sondern du musst den Chinesischen Restsatz benutzen und ein Element $a [mm] \in \IZ$ [/mm] finden mit $a [mm] \equiv [/mm] 0 [mm] \pmod{2}$, [/mm] $a [mm] \equiv [/mm] 1 [mm] \pmod{7}$ [/mm] und ein Element $b [mm] \in \IZ$ [/mm] finden mit $b [mm] \equiv [/mm] 1 [mm] \pmod{2}$, [/mm] $b [mm] \equiv [/mm] 0 [mm] \pmod{7}$ [/mm] (etwa ueber den erweiterten Euklidischen Algorithmus), und dann $11 [mm] \cdot [/mm] a + 1 [mm] \cdot [/mm] b$ nehmen. Und nicht einfach $1 [mm] \cdot [/mm] 11$.
LG Felix
|
|
|
|
