Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Potenzdifferenz mod Differenz

Potenzdifferenz mod Differenz

Universität / Fachhochschule

Tags: differenz, modulo, Potenz

Sukomaki aktiv_icon

13:57 Uhr, 10.08.2019

Hallo liebe Community,

ich sitze gerade an einem Beweis, der eigentlich recht einfach sein sollte.
Aber irgendwie stehe ich dabei auf dem Schlauch.

Also es geht um folgendes :

(b - a) ∣ (2^{b} - 2^{a}) \Rightarrow

(b - a) ∣ (3^{b} - 3^{a}) \land

(b - a) ∣ (4^{b} - 4^{a}) \land

(b - a) ∣ (5^{b} - 5^{a}) \land

(b - a) ∣ (6^{b} - 6^{a}) \land

(b - a) ∣ (7^{b} - 7^{a})

⋮

oder kurz :

(b - a) ∣ (2^{b} - 2^{a}) \Rightarrow \forall q \in ℕ_{0} : (b - a) ∣ (q^{b} - q^{a})

(für

q = 0

und

q = 1

ist es klar)

Kann mir jemand dabei helfen?

Anmerkung : Ich möchte zeigen, dass für

M \in ℕ_{0}^{2 \times 2}

aus

2^{M} \in ℕ_{0}^{2 \times 2}

folgt,
dass für alle

q^{M} \in ℕ_{0}^{2 \times 2}

. Der Beweis mit

(b - a) ∣ (q^{b} - q^{a})

würde mir helfen,
das zugrundeliegende Prinzip zu verstehen.

Gruß
Maki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

abakus

14:14 Uhr, 10.08.2019

Der Term

(q^{b} - q^{a})

kann als

q^{a} (q^{b - a} - 1)

geschrieben werden.

Die Behauptung

(b - a) ∣ (q^{b} - q^{a})

nimmt somit die Form

(b - a) ∣ q^{a} (q^{b - a} - 1)

an bzw. die Form

q^{a} (q^{b - a} - 1) \equiv 0 m o d (b - a)

.
Letzteres wäre unbedingt wahr, wenn

q^{b - a} \equiv 1 m o d (b - a)

nachgewiesen werden könnte.
In Fällen wo das nicht geht müsste ersatzweise

q^{a} \equiv 0 m o d (b - a)

gelten.

Sukomaki aktiv_icon

14:45 Uhr, 10.08.2019

Das verstehe ich so weit.

Aus

(b - a) ∣ (2^{b} - 2^{a})

folgt jetzt, dass

2^{a} \equiv 0 m o d (b - a) \lor 2^{b - a} \equiv 1 m o d (b - a)

.
Wenn das nicht gilt, bin ich fertig.

Ansonsten frage ich mich wie ich

q^{a} \equiv 0 m o d (b - a) \lor q^{b - a} \equiv 1 m o d (b - a)

folgern kann.

abakus

09:16 Uhr, 11.08.2019

Betrachten wir doch mal den Spezialfall, dass (b-a) eine Primzahl ist, die zudem noch teilerfremd zu q ist. Nach dem kleinen Satz von Fermat gilt dann

q^{(b - a) - 1} \equiv 1 m o d (b - a)

, eines unserer Ziele ist allerdings

q^{(b - a)} \equiv 1 m o d (b - a)

.
Was hat das für Konsequenzen?

ermanus aktiv_icon

16:39 Uhr, 11.08.2019

Hallo,
das ist ein sehr bedenkenswerter Beitrag von abakus;
denn sollte

b - a

die Prämisse der untersuchten Implikation
erfüllen können, würde nach abakus daraus folgen, dass die behauptete
Implikation falsch ist.

Ist nun aber

b - a = p

eine ungerade Primzahl, so hat man

p ∣ 2^{a} (2^{p} - 1)

als Prämisse zu erfüllen, damit das "abakus-Problem" auftritt.
Das aber liefert

2^{p} \equiv 1

mod

p

, folglich (kleiner Fermat)

2^{p} \equiv 2 \equiv 1

mod

p

, also ist die Prämisse mit diesen Werten nicht erfüllbar,
so dass die zu beweisende / zu widerlegende Implikation diesen "Angriff" überlebt.
Gruß ermanus

abakus

16:47 Uhr, 11.08.2019

Die Aufgabe sollte einfacher lösbar sein, wenn man sie zunächst nur für a=1 betrachtet und erst danach auf beliebige a ausweitet.

ermanus aktiv_icon

20:26 Uhr, 11.08.2019

Ist

b - a = p^{r}

die Potenz einer ungeraden Primzahl, so ist ebenfalls

p^{r} ∣ 2^{p^{r}} - 1

nicht möglich.
Interessant wäre nun, ganz allgemein zu wissen, wann für ungerade natürliche Zahlen

n

2^{n} - 1

durch

n

teilbar ist.

P.S.: habe auch schon versucht, den Fall

a = 1

gesondert in den Griff
zu bekommen. Leider habe ich dabei bisher keinen Erfolg gehabt.
Warum soll die Behauptung eigentlich überhaupt richtig sein.
Der Fragesteller hat uns bisher keine richtungsweisenden Belege für die
Gültigkeit der Behauptung vorgelegt.

Sukomaki aktiv_icon

21:19 Uhr, 11.08.2019

Zur Zeit ist es leider nur eine Vermutung.

Also die Geschichte dazu :

Ich beschäftige mich mit Matrizen der Form

M \in ℕ_{0}^{2 \times 2}

.
Und dabei speziell mit Potenzen

q^{M}, q \in ℕ

.
Da fiel mir auf, dass für manche

M

und manche

q

gilt

q^{M} \in ℕ_{0}^{2 \times 2}

und für andere nicht.

Dabei habe ich jedoch festgestellt, dass anscheinend

2^{M} \in ℕ_{0}^{2 \times 2} \Rightarrow \forall q \in ℕ : q^{M} \in ℕ_{0}^{2 \times 2}

Dann habe ich eine Untermenge von

ℕ_{0}^{2 \times 2}

betrachtet :

M := (\begin{array}{rcl} a & 1 \\ 0 & b \end{array}) \Rightarrow q^{M} = (\begin{array}{rcl} q^{a} & \frac{q^{b} - q^{a}}{b - a} \\ 0 & q^{b} \end{array})

Für

q^{a}

q^{b}

und

0

ist klar, dass sie in

ℕ_{0}

liegen.

Wenn

{q^{M}}_{1, 2} \in ℕ_{0}

sein soll, muss

(b - a) ∣ (q^{b} - q^{a})

gelten.

Für die Matrizen habe ich die Gültigkeit für einige Beispiele für

M

und jeweils

q \leq 12

untersucht.
Für

(b - a) ∣ (q^{b} - q^{a})

habe ich die Gültigkeit für einige Beispiele für

a, b

und jeweils

q \leq 30

untersucht.

Ich habe bis jetzt kein Gegenbeispiel finden können. Von daher habe ich noch die Hoffnung,
dass die Vermutung richtig ist. Vielleicht ist der Beweis doch nicht so trivial wie ich denke?

Gruß
Maki

ermanus aktiv_icon

22:06 Uhr, 11.08.2019

Es wäre nett, wenn du erklären würdest, wie

q^{M}

für eine

2 \times 2

-Matrix

M

definiert ist. Ich kenne bestenfalls

e^{M}

, was über das Einsetzen der Matrix

M

in die Exponentialreihe definiert ist.
Gruß ermanus

HAL9000

10:21 Uhr, 12.08.2019

> Interessant wäre nun, ganz allgemein zu wissen, wann für ungerade natürliche Zahlen

n

die Zahl

2^{n} - 1

durch

n

teilbar ist.

Zumindest in dieser Teilfrage kann ich Klarheit schaffen:

Angenommen es gibt ein

n > 1

mit

n ∣ (2^{n} - 1)

, offenbar muss dieses

n

ungerade sein. Wir betrachten nun den KLEINSTEN Primteiler

p

von

n

sowie

d = {ord}_{p} (2)

, aus dem kleinen Fermat folgt

1 < d < p

. Aus

2^{n} \equiv 1 mod p

folgt aber auch

d ∣ n

im Widerspruch dazu, dass

p

kleinster Primteiler von

n

ist. Damit war die Annahme falsch, es gibt also kein solches

n

.

---------------------------------------------------------------------------

Für

(b - a) ∣ (2^{b} - 2^{a})

mit o.B.d.A.

a \leq b

können wir ja

(b - a) = 2^{k} u

mit ungeradem

u

ansetzen.

Aus dem entstehenden

(2^{k} u) ∣ 2^{a} (2^{2^{k} u} - 1)

folgt einerseits

k \leq a

sowie andererseits

u ∣ (2^{2^{k} u} - 1)

.

Wie eben gezeigt geht das im Fall

k = 0

nur mit

u = 1

, das ist der Trivialfall

b - a = 1

, wo die Behauptung von Maki76 ja kein Problem ist.

Für

k \geq 1

gibt es aber sehr wohl Beispiele mit

u > 1

, z.B.

a = 1, b = 7

mit dann

k = 1, u = 3

, hier braucht man wohl noch eine schlaue Idee.

ermanus aktiv_icon

13:26 Uhr, 12.08.2019

Vieklen Dank, HAL9000. Das bringt uns ja ein ganzes Stück weiter,
obwohl die ganze Sache sich doch wohl zu einem eher vertrackten
zahlentheoretischen Problem mausert.
Ich greife mal den Fall

k = 1

heraus. Dann muss das ungerade

u

der Kongruenz

2^{2 u} \equiv 1

mod

u

genügen.
Wenn nun 3 kein Primteiler von

u

ist,
so kann man die Kongruenz

4^{u} \equiv 1

mod

u

mit deinem
Argument ebenso behandeln, und erhält so, dass dieser Fall nicht
eintreten kann.

u

muss also den Faktor

3

enthalten.
Betrachten wir

u = 3^{r}, k = 1

mit einer nat. Zahl

r \geq 1

:
Es ist

2^{2 u} = 2^{2 \cdot 3^{r}} = 2^{φ (3^{r + 1})} \equiv 1

mod

3^{r + 1}

,
also erst recht mod

u

.
Betrachtet man aber

u = 3 \cdot q

mit einer ungeraden Primzahl

q \neq 3

,
dann wird es total unübersichtlich ...

Gruß ermanus

HAL9000

14:35 Uhr, 12.08.2019

> Betrachtet man aber

u = 3 \cdot q

mit einer ungeraden Primzahl

q \neq 3

, dann wird es total unübersichtlich ...

Gefordert wird dann

(3 q) ∣ (2^{6 q} - 1)

. Die 3 ist kein Problem, während

q ∣ (6 4^{q} - 1)

in Kombination mit Fermat

q ∣ (6 4^{q - 1} - 1)

q ∣ (6 4^{q} - 1 - 64 (6 4^{q - 1} - 1)) = 63

führt, da bleibt ja nur noch

q = 7

.

Was dann tatsächlich den Voraussetzungen genügt:

k = 1, u = 21

mit z.B.

a = 1, b = 43

.

So oder ähnlich kann man auch noch andere Spezialfälle untersuchen, aber ich habe meine Zweifel, dass man beim Kampf durch dieses immer weitere verästelnde Gestrüpp dem Ziel entscheidend näher kommt.

Bisher drehen sich die Versuche mehr oder weniger darum, diejenigen

a, b

herauszufinden bzw. zu charakterisieren, welche der Voraussetzung genügen. Womöglich muss man das zur Erreichung des Ziels, d.h. für diese

a, b

dann

(b - a) ∣ (q^{b} - q^{a})

nachzuweisen aber gar nicht so genau wissen... (?!)

ermanus aktiv_icon

15:45 Uhr, 12.08.2019

Hallo HAL9000,
ich denke, du hast vollkommen Recht. Leider habe ich noch überhaupt keine
Idee, wie man die Implikation des Fragestellers angehen könnte :(
Gruß ermanus

HAL9000

16:45 Uhr, 12.08.2019

Da sind wir dann schon zwei - ich hab auch keine zündende Idee, wie man das anstellen könnte. Den letzten Absatz hatte ich nur geschrieben, weil ich das Gefühl habe, man sollte seine Anstrengungen da nicht zu sehr einengen auf die Frage, wann die Voraussetzung erfüllt ist.

Roman-22

17:38 Uhr, 12.08.2019

>

oder kurz :

>

(b−a)∣(2b−2a)⇒∀q∈ℕ0:(b−a)∣(qb−qa)
>(für

q = 0

und

q = 1

ist es klar)

Ein paar Gegenbeispiele:

a = 1, b = 19, q = 3

oder

6, 12,15,21, . .

a = 1, b = 55, q = 3

oder

6,9,12,15,18,21,24,30, . .

a = 2, b = 56, q = 3

oder

6, 12,15,21, . .

HAL9000

18:25 Uhr, 12.08.2019

Upps, peinlich, da wir oben doch schon über

b - a = 2 \cdot 3^{r}

gesprochen hatten. :-)

ermanus aktiv_icon

18:32 Uhr, 12.08.2019

Nö, gar nicht peinlich; denn

a = 1, b = 19

erfüllt die Prämisse, und das war
es, was wir untersucht haben.
Ob daraus die vom Fragesteller "gewünschte" Teilbarkeit folgt, wäre ja dann
eine neue Untersuchung, die Roman uns nun freundlicherweise abgenommen hat :-)

Sukomaki aktiv_icon

22:24 Uhr, 12.08.2019

@Roman

darf ich fragen, wie Du die Gegenbeispiele bestimmt hast?

Ich habe es jetzt mal mit einem MAPLE-Code getan und
folgendes Resultat bekommen :

for a from 1 to 80 do for b from a+1 to 80 do for q from 3 to 30 do if ((2^b-2^a)
mod (b-a) = 0) and ((q^b-q^a) mod (b-a) !=0) then print(a,b,q) fi od od od
1, 19, 3
1, 19, 6
1, 19, 12
1, 19, 15
1, 19, 21
1, 19, 24
1, 19, 30
1, 55, 3
1, 55, 6
1, 55, 9
1, 55, 12
1, 55, 15
1, 55, 18
1, 55, 21
1, 55, 24
1, 55, 30
2, 56, 3
2, 56, 6
2, 56, 12
2, 56, 15
2, 56, 21
2, 56, 24
2, 56, 30

Gruß
Maki

Roman-22

23:37 Uhr, 12.08.2019

>

darf ich fragen, wie Du die Gegenbeispiele bestimmt hast?
Ganz genau so wie du - brute force.
Nur

100

anstelle von

80, q

von 3 bis

100

und ein anderes Programm.
Außerdem anstelle der mit AND verknüpften if -Anweisung in der q-Schleife lieber ein normale if-Anweiseung bereits in der b-Schleife, die nur wenn nötig die q-Schleife (dort dann ein weiteres if) triggert. Das sollte effizienter sein.

Langsam ist es in so einen Programm aber dennoch. Anstatt in einem Mathepropgramm ein interpretiertes Programm auszuführen wäre es ja deutlich flotter, da Ganze selbst in einer compilierbaren Programmiersprache zu implementieren. Allerdings müsste man dann eben eine Toolbox für das exakte Rechnen mit großen Zahlen verwenden, da man sonst viel zu rasch an die Grenzen des IEEE Formats stößt.

Sukomaki aktiv_icon

16:31 Uhr, 13.08.2019

Schade, dass sich die Implikation als falsch herausgestellt hat,
aber Danke trotzdem für eure Mühe.

Ich nehme es mit Humor. Vielleicht habe ich beim nächsten Mal
mehr Glück.

@Roman

Apropos exaktes Rechnen mit großen Zahlen. Hast Du gewusst, dass
es einen Algorithmus gibt, der im Hexadezimalsystem eine beliebige
Stelle von pi extrahieren kann? Dazu bräuchte man auch gar nicht
mehr viel Speicher für den benutzten Datentyp.

Roman-22

16:48 Uhr, 13.08.2019

>

Schade, dass sich die Implikation als falsch herausgestellt hat,

Du könntest ja versuchen, allgemein die Sonderfälle zu isolieren, in denen sie falsch ist.

>Apropos exaktes Rechnen mit großen Zahlen. Hast Du gewusst, dass
es einen Algorithmus gibt, der im Hexadezimalsystem eine beliebige
Stelle von

π

extrahieren kann? Dazu bräuchte man auch gar nicht
mehr viel Speicher für den benutzten Datentyp.

Ich nehme an, dass du den "Tröpfchen-Algorithmus" (spigot-algorithm) meinst. War damals eine ziemlich große Überraschung, dass das möglich ist ohne Langzahlarithmetik.

Sukomaki aktiv_icon

18:16 Uhr, 13.08.2019

Ich meine den BBP(Bailey-Borwein-Plouffe)-Algorithmus.

Unter Wikipedia findet sich unter der BBP-Formel nichts zu dem Tröpfchen-
Algorithmus. Daher nehme ich an, dass es sich nicht um den Tröpfchen-
Algorithmus handelt.

Wie auch immer :

Ich habe mal geschaut, für welche

a

und

b

die Implikation falsch ist.

Etwas habe ich schon herausgefunden :

Wenn

a \geq 3

und

b = a + 136 \cdot 3^{n}, n \in ℕ_{0}

dann ist die Implikation ungültig.
Wenn

a \geq 2

und

b = a + 124 \cdot 5^{n}, n \in ℕ

dann ist die Implikation ungültig.
Wenn

a \geq 3

und

b = a + 248 \cdot 5^{n}, n \in ℕ

dann ist die Implikation ungültig.
Wenn

a \geq 2

und

b = a + 164 \cdot 5^{n}, n \in ℕ

dann ist die Implikation ungültig.

136 = 2^{3} \cdot 17

124 = 2^{2} \cdot 31

248 = 2^{3} \cdot 31

164 = 2^{2} \cdot 41

Und dann gibt es noch vereinzelte

a, b

, für die die Implikation falsch ist.

Ich habe (noch) kein Muster in der Verteilung der

a, b

finden können.

Im Übrigen gebe ich Dir Recht. Ich sollte nicht so schnell aufgeben.

Das erinnert mich daran, dass ich einmal versucht habe, die "Reihen-Algebra"
aufzustellen, war aber nicht konsequent genug, um die darin verborgenen
Zusammenhänge aufzudecken. Bald darauf las ich, dass ein gewisser Markus
Müller mit seiner Arbeit zum Thema "Reihen-Algebra" den Jugend forscht-Preis
gewonnen hat :-)

Sukomaki aktiv_icon

15:10 Uhr, 14.08.2019

Ich verfolge jetzt einen anderen Ansatz. Anstatt die Sonderfälle zu isolieren, bestimme
ich die Schranke

s_{p}

, oberhalb derer die Implikation falsch sein könnte.

Zu diesem Zweck betrachte ich die

(a, b)

mit

((2^{b} - 2^{a}) m o d (b - a) = 0) \land ((3^{b} - 3^{a}) m o d (b - a) = 0) \land \dots \land ((p^{b} - p^{a}) m o d (b - a) = 0)

Falls es jetzt ein

q > p

gibt, für das

((q^{b} - q^{a}) m o d (b - a) \neq 0)

, so ist die Implikation falsch.

Die Schranke

s_{p}

ist

(a, b, q)

mit

a \in {1, 2}

und

q^{b} - q^{a}

minimal, wobei

\underset{m p r i m \leq p}{⋀} ((m^{b} - m^{a}) m o d (b - a) = 0) \land ((q^{b} - q^{a}) m o d (b - a) \neq 0)

p : a,b,q
2 : 1,19,3 (

3^{19} - 3^{1}

hat

9

Ziffern)
3 : 1,295,7 (

7^{295} - 7^{1}

hat

249

Ziffern)
5 : 1,295,7
7 : 2,26622,11 (

1 1^{26622} - 1 1^{2}

hat

27723

Ziffern)
11 : 2,26366,13 (

1 3^{26366} - 1 3^{2}

hat

29370

Ziffern)
13 : 2,123464,19 (

1 9^{123464} - 1 9^{2}

hat

157880

Ziffern)

\Rightarrow

Die Schranke wächst sehr schnell.

Für

p = 2

ergibt sich einer der von Roman genannten Sonderfälle a=1, b=19, q=3

Sukomaki aktiv_icon

10:22 Uhr, 16.08.2019

Was meint Ihr?

So zeige ich, dass bereits für

p = 7

für fast alle

(a, b)

für die

(b - a) ∣ (2^{b} - 2^{a}) \land \dots \land (b - a) ∣ (p^{b} - p^{a})

gilt auch

(b - a) ∣ (q^{b} - q^{a})

gilt. Und wenn

(a, b)

nicht zu den eher wenigen Ausnahmen gehört, so gilt die Implikation für sehr, sehr viele

q

HAL9000

14:55 Uhr, 16.08.2019

Mit dem "fast alle" bzw. "sehr, sehr viele" ist das so eine Sache - vor allem beweistechnisch sind die vielleicht wenigen, aber dann doch vorhandenen Ausnahmen ziemlich hinderlich. ;-)

Sukomaki aktiv_icon

21:51 Uhr, 16.08.2019

Und wenn

(a, b)

nicht zu den eher wenigen Ausnahmen gehört, so gilt die Implikation
für alle

q

Roman-22

22:13 Uhr, 18.08.2019

Dieses ständige Pushen des Threads ist eine überaus lästige Unsitte!

Sukomaki aktiv_icon

22:27 Uhr, 18.08.2019

Aber wie soll ich anders vermeiden, dass der Thread geschlossen wird, wenn ich noch Interesse an einer Antwort habe? Ich bekomme eine Mail "Besteht noch Interesse?". Das bejahe ich. Meine Absicht ist es nicht, den Thread zu pushen.

Roman-22

22:36 Uhr, 18.08.2019

Ah, ich wusste nicht, das man da ein Mail bekommt. Dann versteh ich deine Reaktion zu antworten, auch wenn es vl eher unwahrscheinlich ist, dass noch Antworten kommen. Mich irritierts halt wenn ein Thread, in dem sich nichts geändert hat, immer wieder nach oben bubbled.
Wirklich geschlossen wird ein Thread hier ja nie. Es wird nur am Ende ein Vermerk angebracht und das Ziel ist, den Thread nicht als offene Frage stehen zu lassen, da manche Antwortgeber gezielt nach diesen filtern und man verhindern möchte, dass da alte Leichen zutage gefördert werden.
Im Thread kann auch dem "Schließen" nichtsdestotrotz jederzeit weiter geschrieben werden - er wird nicht im Sinne von "read only" geschlossen wie in anderen Foren.

Sukomaki aktiv_icon

21:50 Uhr, 20.08.2019

Ich bedanke mich herzlich bei allen Beteiligten dieses Threads.

Immerhin bin ich jetzt so weit, sagen zu können :
Gegeben

(a, b)

mit

(b - a) ∣ (2^{b} - 2^{a}) \land (b - a) ∣ (3^{b} - 3^{a}) \land \dots \land (b - a) ∣ (p^{b} - p^{a})

\Rightarrow

für solche

(a, b) < S : \forall q : (b - a) ∣ (q^{b} - q^{a})

wobei

S

sehr schnell mit

p

wächst.

Dabei heisst "

(a, b) < S

" ausgeschrieben :

(q^{b} - q^{a}) < min ((w^{b} - w^{a}) m o d (b - a) \neq 0) :

1478587

1477894

	Status: nicht eingeloggt	Noch nicht registriert?