Potenz endet auf .... Zahl < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich hätt da mal ne Frage:
Ich überlege, wie ich berechnen kann, ob es zu einer Zahl eine Potenz geben kann, so dass sie auf bestimmte Zahlen endet.
Konkret:
Gibt es eine Potenz von 17, die auf ... 25 oder ... 39 endet.
Nun muss ich dass ja modulo 100 betrachten:
Ich überlege also, ob es ein d gibt mit
[mm] 17^d\equiv25mod100
[/mm]
oder
[mm] 17^d\equiv39mod100
[/mm]
Wie kann ich nun die Potenz auflösen?
Ich habe irgendwie das Gefühl, es könnte auch etwas mit Primitivwurzeln zu tun haben, und 100 besitzt ja nun keine Primitivwurzeln... aber wie kann ich jetzt da weiter schließen?
Wär schön, wenn da jemand Bescheid wüsste und mit weiterhelfen würde. Danke!
|
|
| |
|
moin,
Die 17 ist eine Einheit modulo 100, also gilt dies auch für alle Potenzen.
Da die 25 keine Einheit ist, kann also keine Potenz von 17 auf 25 enden.
Für eine allgemeine Berechnung der Potenzen von 17 modulo 100 würde ich dir empfehlen, $17 = 10+7$ zu schreiben.
Nun ist [mm] $17^k [/mm] = [mm] (10+7)^k [/mm] = [mm] \summe_{i=0}^k [/mm] {k [mm] \choose [/mm] i} [mm] 10^i*7^{k-i}$.
[/mm]
Da [mm] $10^2 \equiv [/mm] 0$ (mod 100) fällt von der Summe fast alles weg und für deine Frage reicht es Potenzen von $7$ zu betrachten.
Wendest du schließlich noch den gleichen Trick auf [mm] $7^2 [/mm] = 49 = (50-1)$ an so solltest du das von Hand hinkriegen.
lg
Schadow
|
|
|
| |
|
| Aufgabe | [das ist nicht die Aufgabenstellung aber ich komm aus dem Fenster nicht raus]
Hallo,danke!
Ich hab mir Deinen Lösungsvorschlag durch den Kopf gehen, lassen, allerdings reicht er nicht aus.
Gut, für 25 kann ich mit der Einheit schließen. (Oder trivialerweise, dass [mm] 17^p [/mm] nicht durch 5 teilbar sein wird.)
Aber bei den anderen Zahlen kann ich das nicht so einfach begründen.
Nun ist ja 39 eine Einheit, es gibt aber trotzdem keine Darstellung ... 39.
Oder die 89 ist eine Einheit, und es gibt eine Darstellung ... 89, da [mm] 17^2\equiv89mod100. [/mm]
Also ist "Einheitsein" eine notwendige, aber keine hinreichende Voraussetzung.
Also muss hinter der Begründung noch mehr stecken... aber was? Jemand ne Idee? Doch was mit den Einheitswurzeln?
Oder kann ich das mod4 und mod25 betrachten?
Und noch kurz was zur Berechnung der Potenzen: So einfach erscheint mir das nicht, ich muss ja für jede Potenz von 7 noch darauf achten, ob ich x*10 dazuaddieren kann, damit es eine Potenz von 17 wird, da sich die Binomische ja nicht ganz auflöst (41 ist eine Potenz von 17, aber nicht von 7, ... etc. Hmmm.) |
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:17 Mi 25.04.2012 | | Autor: | felixf |
Moin!
> Ich hab mir Deinen Lösungsvorschlag durch den Kopf gehen,
> lassen, allerdings reicht er nicht aus.
>
> Gut, für 25 kann ich mit der Einheit schließen. (Oder
> trivialerweise, dass [mm]17^p[/mm] nicht durch 5 teilbar sein
> wird.)
>
> Aber bei den anderen Zahlen kann ich das nicht so einfach
> begründen.
>
> Nun ist ja 39 eine Einheit, es gibt aber trotzdem keine
> Darstellung ... 39.
>
> Oder die 89 ist eine Einheit, und es gibt eine Darstellung
> ... 89, da [mm]17^2\equiv89mod100.[/mm]
>
> Also ist "Einheitsein" eine notwendige, aber keine
> hinreichende Voraussetzung.
Exakt.
> Also muss hinter der Begründung noch mehr stecken... aber
> was? Jemand ne Idee? Doch was mit den Einheitswurzeln?
Du musst die von $17 + [mm] 100\IZ$ [/mm] erzeugte zyklische Untergruppe von der Einheitengruppe [mm] $(\IZ/100\IZ)^\ast$ [/mm] betrachten. Die Ordnung ist hoechstens [mm] $kgV(\phi(25), \phi(4)) [/mm] = kgV(20, 2) = 20$, koennte aber auch kleiner sein. Alle Restklassen in dieser zyklischen Gruppe sind genau die Reste, die auftreten koennen.
> Oder kann ich das mod4 und mod25 betrachten?
Ja, kannst du. Es gilt $17 [mm] \equiv [/mm] 1 [mm] \pmod{4}$ [/mm] und $17 [mm] \equiv [/mm] 17 [mm] \pmod{25}$. [/mm] Daraus folgt schonmal, dass wenn [mm] $17^k \equiv [/mm] x [mm] \pmod{100}$ [/mm] gilt, dass $x [mm] \equiv [/mm] 1 [mm] \pmod{4}$ [/mm] sein muss.
Modulo 25 gilt [mm] $17^2 \equiv [/mm] 14 [mm] \pmod{25}$, $17^4 \equiv 14^2 \equiv [/mm] 21 [mm] \pmod{25}$, $17^5 \equiv [/mm] 21 [mm] \cdot [/mm] 17 [mm] \equiv [/mm] 7 [mm] \pmod{25}$, $17^{10} \equiv 7^2 \equiv [/mm] 24 [mm] \pmod{25}$. [/mm] Daraus folgt, dass die Ordnung von 17 in der multiplikativen Gruppe von [mm] $\IZ/25\IZ$ [/mm] gleich 20 ist, also maximal. Damit ist jedes Element in [mm] $(\IZ/25\IZ)^\ast$ [/mm] eine Potenz von 17.
Insgesamt kann man also schliessen: fuer $x [mm] \in \IZ$ [/mm] gibt es ein $k [mm] \in \IN$ [/mm] mit [mm] $17^k \equiv [/mm] x [mm] \pmod{100}$ [/mm] genau dann, wenn $x [mm] \equiv [/mm] 1 [mm] \pmod{4}$ [/mm] und $5 [mm] \nmid [/mm] x$ gilt (letzteres ist aequivalent zu $x + [mm] 25\IZ \in (\IZ/25\IZ)^\ast$).
[/mm]
LG Felix
|
|
|
| |
|
Hi,
Ich denke du solltest dir vielleicht etwas zum Begriff "diskreter Logarithmus" durchlesen. Das ist deine Problemstellung.
Das Lösen der Kongruenz [mm] $a^x\equiv b\mod [/mm] p$ mit [mm] $p\in \mathbb{P}$ [/mm] (ges.: x) ist i.A. recht kompliziert.
Es gibt dafür diverse (ineffektive) Algorithmen. (Babystep-Giantstep, [mm] Pollards-$\rho$,Pohlig-Hellman-Algo)
[/mm]
Gruß
|
|
|
|
