www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Potenz endet auf .... Zahl
Potenz endet auf .... Zahl < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Potenz endet auf .... Zahl: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:12 Sa 21.04.2012
Autor: dudelidei

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!


        
Bezug
Potenz endet auf .... Zahl: Antwort
Status: (Antwort) fertig Status 
Datum: 20:36 Sa 21.04.2012
Autor: Schadowmaster

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

Bezug
                
Bezug
Potenz endet auf .... Zahl: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:47 So 22.04.2012
Autor: dudelidei

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.)




Bezug
                        
Bezug
Potenz endet auf .... Zahl: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Potenz endet auf .... Zahl: diskrete Logarithmen
Status: (Antwort) fertig Status 
Datum: 11:51 So 22.04.2012
Autor: wieschoo

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ß

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]