Partner von azubiworld.com - Logo
 
Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Potenzdifferenz mod Differenz

Potenzdifferenz mod Differenz

Universität / Fachhochschule

Tags: differenz, modulo, Potenz

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Maki76

Maki76 aktiv_icon

13:57 Uhr, 10.08.2019

Antworten
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)(2b-2a)
(b-a)(3b-3a)
(b-a)(4b-4a)
(b-a)(5b-5a)
(b-a)(6b-6a)
(b-a)(7b-7a)


oder kurz :

(b-a)(2b-2a)q0:(b-a)(qb-qa)
(für q=0 und q=1 ist es klar)

Kann mir jemand dabei helfen?

Anmerkung : Ich möchte zeigen, dass für M02×2 aus 2M02×2 folgt,
dass für alle qM02×2. Der Beweis mit (b-a)(qb-qa) 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."
Antwort
abakus

abakus

14:14 Uhr, 10.08.2019

Antworten
Der Term (qb-qa) kann als qa(qb-a-1) geschrieben werden.

Die Behauptung (b-a)(qb-qa) nimmt somit die Form (b-a)qa(qb-a-1) an bzw. die Form
qa(qb-a-1)0mod(b-a).
Letzteres wäre unbedingt wahr, wenn qb-a1mod(b-a) nachgewiesen werden könnte.
In Fällen wo das nicht geht müsste ersatzweise qa0mod(b-a) gelten.
Maki76

Maki76 aktiv_icon

14:45 Uhr, 10.08.2019

Antworten
Das verstehe ich so weit.

Aus (b-a)(2b-2a) folgt jetzt, dass 2a0mod(b-a)2b-a1mod(b-a).
Wenn das nicht gilt, bin ich fertig.

Ansonsten frage ich mich wie ich qa0mod(b-a)qb-a1mod(b-a) folgern kann.


Antwort
abakus

abakus

09:16 Uhr, 11.08.2019

Antworten
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)-11mod(b-a), eines unserer Ziele ist allerdings q(b-a)1mod(b-a).
Was hat das für Konsequenzen?
Antwort
ermanus

ermanus aktiv_icon

16:39 Uhr, 11.08.2019

Antworten
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
p2a(2p-1) als Prämisse zu erfüllen, damit das "abakus-Problem" auftritt.
Das aber liefert 2p1 mod p, folglich (kleiner Fermat)
2p21 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

Antwort
abakus

abakus

16:47 Uhr, 11.08.2019

Antworten
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.
Antwort
ermanus

ermanus aktiv_icon

20:26 Uhr, 11.08.2019

Antworten
Ist b-a=pr die Potenz einer ungeraden Primzahl, so ist ebenfalls
pr2pr-1 nicht möglich.
Interessant wäre nun, ganz allgemein zu wissen, wann für ungerade natürliche Zahlen n
2n-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.
Maki76

Maki76 aktiv_icon

21:19 Uhr, 11.08.2019

Antworten
Zur Zeit ist es leider nur eine Vermutung.

Also die Geschichte dazu :

Ich beschäftige mich mit Matrizen der Form M02×2.
Und dabei speziell mit Potenzen qM,q.
Da fiel mir auf, dass für manche M und manche q gilt qM02×2 und für andere nicht.

Dabei habe ich jedoch festgestellt, dass anscheinend 2M02×2q:qM02×2

Dann habe ich eine Untermenge von 02×2 betrachtet :

M:=(a10b)qM=(qaqb-qab-a0qb)

Für qa, qb und 0 ist klar, dass sie in 0 liegen.

Wenn qM1,20 sein soll, muss (b-a)(qb-qa) gelten.

Für die Matrizen habe ich die Gültigkeit für einige Beispiele für M und jeweils q12 untersucht.
Für (b-a)(qb-qa) habe ich die Gültigkeit für einige Beispiele für a,b und jeweils q30 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
Antwort
ermanus

ermanus aktiv_icon

22:06 Uhr, 11.08.2019

Antworten
Es wäre nett, wenn du erklären würdest, wie qM für eine 2×2-Matrix M
definiert ist. Ich kenne bestenfalls eM, was über das Einsetzen der Matrix
M in die Exponentialreihe definiert ist.
Gruß ermanus
Antwort
HAL9000

HAL9000 aktiv_icon

10:21 Uhr, 12.08.2019

Antworten
> Interessant wäre nun, ganz allgemein zu wissen, wann für ungerade natürliche Zahlen n die Zahl 2n-1 durch n teilbar ist.

Zumindest in dieser Teilfrage kann ich Klarheit schaffen:

Angenommen es gibt ein n>1 mit n(2n-1), offenbar muss dieses n ungerade sein. Wir betrachten nun den KLEINSTEN Primteiler p von n sowie d=ordp(2), aus dem kleinen Fermat folgt 1<d<p. Aus 2n1 mod p folgt aber auch dn 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)(2b-2a) mit o.B.d.A. ab können wir ja (b-a)=2ku mit ungeradem u ansetzen.

Aus dem entstehenden (2ku)2a(22ku-1) folgt einerseits ka sowie andererseits u(22ku-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 k1 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.

Antwort
ermanus

ermanus aktiv_icon

13:26 Uhr, 12.08.2019

Antworten
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 22u1 mod u genügen.
Wenn nun 3 kein Primteiler von u ist,
so kann man die Kongruenz 4u1 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=3r,k=1 mit einer nat. Zahl r1:
Es ist 22u=223r=2φ(3r+1)1 mod 3r+1,
also erst recht mod u.
Betrachtet man aber u=3q mit einer ungeraden Primzahl q3,
dann wird es total unübersichtlich ...

Gruß ermanus

Antwort
HAL9000

HAL9000 aktiv_icon

14:35 Uhr, 12.08.2019

Antworten
> Betrachtet man aber u=3q mit einer ungeraden Primzahl q3, dann wird es total unübersichtlich ...

Gefordert wird dann (3q)(26q-1). Die 3 ist kein Problem, während q(64q-1) in Kombination mit Fermat q(64q-1-1) zu q(64q-1-64(64q-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)(qb-qa) nachzuweisen aber gar nicht so genau wissen... (?!)
Antwort
ermanus

ermanus aktiv_icon

15:45 Uhr, 12.08.2019

Antworten
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
Antwort
HAL9000

HAL9000 aktiv_icon

16:45 Uhr, 12.08.2019

Antworten
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.
Antwort
Roman-22

Roman-22

17:38 Uhr, 12.08.2019

Antworten
> 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,...



B
Antwort
HAL9000

HAL9000 aktiv_icon

18:25 Uhr, 12.08.2019

Antworten
Upps, peinlich, da wir oben doch schon über b-a=23r gesprochen hatten. :-)
Antwort
ermanus

ermanus aktiv_icon

18:32 Uhr, 12.08.2019

Antworten
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 :-)
Maki76

Maki76 aktiv_icon

22:24 Uhr, 12.08.2019

Antworten
@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
Antwort
Roman-22

Roman-22

23:37 Uhr, 12.08.2019

Antworten
> 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.
Maki76

Maki76 aktiv_icon

16:31 Uhr, 13.08.2019

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



Antwort
Roman-22

Roman-22

16:48 Uhr, 13.08.2019

Antworten
> 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.
Maki76

Maki76 aktiv_icon

18:16 Uhr, 13.08.2019

Antworten
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 a3 und b=a+1363n,n0 dann ist die Implikation ungültig.
Wenn a2 und b=a+1245n,n dann ist die Implikation ungültig.
Wenn a3 und b=a+2485n,n dann ist die Implikation ungültig.
Wenn a2 und b=a+1645n,n dann ist die Implikation ungültig.

136=2317
124=2231
248=2331
164=2241

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

Maki76

Maki76 aktiv_icon

15:10 Uhr, 14.08.2019

Antworten
Ich verfolge jetzt einen anderen Ansatz. Anstatt die Sonderfälle zu isolieren, bestimme
ich die Schranke sp, oberhalb derer die Implikation falsch sein könnte.

Zu diesem Zweck betrachte ich die (a,b) mit
((2b-2a)mod(b-a)=0)((3b-3a)mod(b-a)=0)((pb-pa)mod(b-a)=0)

Falls es jetzt ein q>p gibt, für das ((qb-qa)mod(b-a)0), so ist die Implikation falsch.

Die Schranke sp ist (a,b,q) mit a{1,2} und qb-qa minimal, wobei
mprimp((mb-ma)mod(b-a)=0)((qb-qa)mod(b-a)0)

p : a,b,q
2 : 1,19,3 (319-31 hat 9 Ziffern)
3 : 1,295,7 (7295-71 hat 249 Ziffern)
5 : 1,295,7
7 : 2,26622,11 (1126622-112 hat 27723 Ziffern)
11 : 2,26366,13 (1326366-132 hat 29370 Ziffern)
13 : 2,123464,19 (19123464-192 hat 157880 Ziffern)

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


Maki76

Maki76 aktiv_icon

10:22 Uhr, 16.08.2019

Antworten
Was meint Ihr?

So zeige ich, dass bereits für p=7 für fast alle (a,b) für die (b-a)(2b-2a)(b-a)(pb-pa)
gilt auch (b-a)(qb-qa) gilt. Und wenn (a,b) nicht zu den eher wenigen Ausnahmen gehört, so gilt die Implikation für sehr, sehr viele q.
Antwort
HAL9000

HAL9000 aktiv_icon

14:55 Uhr, 16.08.2019

Antworten
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. ;-)
Maki76

Maki76 aktiv_icon

21:51 Uhr, 16.08.2019

Antworten
Und wenn (a,b) nicht zu den eher wenigen Ausnahmen gehört, so gilt die Implikation
für alle q.
Antwort
Roman-22

Roman-22

22:13 Uhr, 18.08.2019

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

Maki76 aktiv_icon

22:27 Uhr, 18.08.2019

Antworten
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.
Antwort
Roman-22

Roman-22

22:36 Uhr, 18.08.2019

Antworten
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.
Frage beantwortet
Maki76

Maki76 aktiv_icon

21:50 Uhr, 20.08.2019

Antworten
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)(2b-2a)(b-a)(3b-3a)(b-a)(pb-pa)
für solche (a,b)<S:q:(b-a)(qb-qa) wobei S sehr schnell mit p wächst.

Dabei heisst "(a,b)<S" ausgeschrieben : (qb-qa)<min((wb-wa)mod(b-a)0):