Kongruenzrechnung beweise < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:51 Sa 10.12.2011 | | Autor: | Catman |
| Aufgabe | 1.Beweisen Sie mittels Kongruenzrechnung 47|2^23 - 1
2. Mit welcher Ziffer endet 777^777? Begründen Sie Ihre Antwort.
3. Bestimmen Sie die letzten 3 Ziffern der Zahl 2^30.
4. Beweisen Sie mittels Kongruenzrechnung, dass [mm] 2^{2^{2011}} [/mm] -1 durch 3 teilbar ist.
5. Beweisen Sie mittels Kongruenzrechnung [mm] 7|[2^{2^{n}}]^3 [/mm] -1 |
Hallo,
Also das sind alles Aufgaben, die ich mit Kongruenzrechnung lösen muss.
Ich denke mal, dass die Lösung bei allen Aufgaben nach dem selben Prinzip erfolgen müsste. Es wäre echt super, wenn wir das jemand exemplarisch an den ersten beiden Aufgaben erklären könnte. Also ich weiß, dass ich wahrscheinlich von einer Kongruenz von der ich auf jedenfall weiß, dass sie stimmt durch Umformung auf das kommen muss, was in der Aufgabe steht, oder? Nur irgendwie weiß ich nicht wie ich das tun soll. (Habe bisher noch nicht mit Kongruenzen gerechnet)
Und bei der 2 und 3 weiß ich, dass ich mod10 bzw. mod1000 rechnen muss. Aber auch da habe ich keine Vorstellung davon, was ich dann rechnen muss. Wäre also super wenn mir da jemand helfen würde. Die anderen Aufgaben werde ich dann versuchen selber zu lösen.
Vielen Dank schonmal...
Gruß
Andy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:41 So 18.12.2011 | | Autor: | felixf |
Moin Andy!
> 1.Beweisen Sie mittels Kongruenzrechnung 47|2^23 - 1
> 2. Mit welcher Ziffer endet 777^777? Begründen Sie Ihre
> Antwort.
> 3. Bestimmen Sie die letzten 3 Ziffern der Zahl 2^30.
> 4. Beweisen Sie mittels Kongruenzrechnung, dass
> [mm]2^{2^{2011}}[/mm] -1 durch 3 teilbar ist.
> 5. Beweisen Sie mittels Kongruenzrechnung [mm]7|[2^{2^{n}}]^3[/mm]
> -1
>
> Also das sind alles Aufgaben, die ich mit Kongruenzrechnung
> lösen muss.
> Ich denke mal, dass die Lösung bei allen Aufgaben nach dem
> selben Prinzip erfolgen müsste. Es wäre echt super, wenn
> wir das jemand exemplarisch an den ersten beiden Aufgaben
> erklären könnte. Also ich weiß, dass ich wahrscheinlich
> von einer Kongruenz von der ich auf jedenfall weiß, dass
> sie stimmt durch Umformung auf das kommen muss, was in der
> Aufgabe steht, oder? Nur irgendwie weiß ich nicht wie ich
> das tun soll. (Habe bisher noch nicht mit Kongruenzen
> gerechnet)
Ich rechne dir mal vor, wie man $13 [mm] \mid (3^{30} [/mm] - 1)$ zeigt.
Dazu berechnet man erstmal [mm] $3^{30}$ [/mm] modulo 13 aus. Dazu beachte, dass $30 = [mm] 2^4 [/mm] + [mm] 2^3 [/mm] + [mm] 2^2 [/mm] + [mm] 2^0$ [/mm] ist. Damit ist [mm] $3^{30} [/mm] = [mm] 3^{2^4} \cdot 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^0}$. [/mm] Wegen [mm] $3^{2^4} [/mm] = [mm] 3^{2^3 \cdot 2} [/mm] = [mm] (3^{2^3})^2$ [/mm] und [mm] $3^{2^3} [/mm] = [mm] (3^{2^2})^2$ [/mm] und [mm] $3^{2^2} [/mm] = [mm] (3^{2^1})^2$ [/mm] und [mm] $3^{2^1} [/mm] = [mm] 3^2$ [/mm] und [mm] $3^{2^0} [/mm] = [mm] 3^1 [/mm] = 3$ kannst du damit die Faktoren nur durch quadrieren bestimmen.
Am besten reduzierst du das nach jedem Schritt modulo 13, damit die Zahlen klein bleiben.
Damit ist [mm] $3^{2^0} [/mm] = 3$, [mm] $3^{2^1} [/mm] = 9$, [mm] $3^{2^2} [/mm] = [mm] 9^2 [/mm] = 81 [mm] \equiv [/mm] 3 [mm] \pmod{13}$, $9^{2^3} [/mm] = [mm] (9^{2^2})^2 \equiv 3^2 [/mm] = 9 [mm] \pmod{13}$, $9^{2^4} [/mm] = [mm] (9^{2^3})^2 \equiv 9^2 [/mm] = 81 [mm] \equiv [/mm] 3 [mm] \pmod{13}$.
[/mm]
Damit ergibt sich [mm] $3^{30} [/mm] = [mm] 3^{2^4} \cdot 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^1} \equiv [/mm] 3 [mm] \cdot [/mm] 9 [mm] \cdot [/mm] 3 [mm] \cdot [/mm] 9 = [mm] 27^2 \equiv 1^2 [/mm] = 1 [mm] \pmod{13}$.
[/mm]
Damit ist schliesslich [mm] $3^{30} [/mm] - 1 [mm] \equiv [/mm] 1 - 1 [mm] \equiv [/mm] 0 [mm] \pmod{13}$, [/mm] was gerade $13 [mm] \mid (3^{30} [/mm] - 1)$ bedeutet.
Alternativ haettest du das auch mit dem Satz von Euler vereinfachen koennen: [mm] $\phi(13) [/mm] = 12$, und $30 = 2 [mm] \cdot [/mm] 12 + 6$, womit [mm] $3^{30} [/mm] = [mm] (3^{12})^2 \cdot 3^6 \equiv 1^2 \cdot 3^6 \pmod{13}$ [/mm] ist. Dann musst du nur noch [mm] $3^6$ [/mm] modulo 13 bestimmen.
Der Trick mit der Eulerschen [mm] $\phi$-Funktion [/mm] sollte dir gerade bei (b) helfen, da [mm] $\phi(10)$ [/mm] recht klein ist und somit nur ein kleiner Rest bleibt. Und da du modulo 10 rechnest sind es eh nur sehr kleine Zahlen, die du multiplizieren musst. (Das kleine Einmaleins reicht.)
> Und bei der 2 und 3 weiß ich, dass ich mod10 bzw. mod1000
> rechnen muss.
Genau.
LG Felix
|
|
|
|
