Beweis für eine Kongruenzgleichung gesucht

Neue Frage »

blackdrake Auf diesen Beitrag antworten »
Beweis für eine Kongruenzgleichung gesucht
Hallo,

ich suche einen Beweis für folgende Theorie:

Gegeben ist


Theorie:
Es gibt für alle ein Tupel (mit ), für das diese Formel erfüllt ist.

Ich habe ein kleines Python-Programm geschrieben, und es scheint wirklich so zu sein, aber mich würde sehr der mathematische Beweis interessieren.

Ich wäre sehr dankbar für einen Beweis. Meine Hochschulmathematik-Kenntnisse sind über die Jahre ziemlich "eingestaubt".


Hintergrund:

Eine Zahl ist "unsterblich" mit Potenz "p" und Basis "b", wenn in Basisnotation der Basis "b" auf "n" endet.

Beispiel: 625 ist unsterblich mit Potenz 2 und Basis 10, da (auf 625 endet)

Die Gleichung ist:


Meine Theorie ist, dass jede Zahl "n" in irgendeiner Basis "b" und Potenz "p" unsterblich ist.

Beispiel: Die Zahl 26036 ist unsterblich mit Basis 165 und Potenz 111.
Finn_ Auf diesen Beitrag antworten »

Sei . Nach dem Satz von Euler-Fermat gilt dann

Demnach gilt auch


Ist nun eine Primzahl, die nicht als Primfaktor in vorkommt, dann kommt auch die Primzahlpotenz nicht als Primfaktor in vor. Ergo muss sein, sofern ist.

Man bekommt dann .
Finn_ Auf diesen Beitrag antworten »

Es stellt sich noch die Frage, wie man eine möglichst kleine Potenz findet. Setzen wir mal voraus, dass ist. Dann gilt auch

wobei nun aber die kleinste Zahl mit dieser Eigenschaft ist, wobei vorausgesetzt wird. Hierbei ist die Carmichael-Funktion. Der Wert ist in einigen Fällen kleiner als .

In deinem Beispiel ist und . Es ergibt sich . Man erhält

und
.

Es gilt aber auch schon
,
woraus dann

folgt. Das ist so, weil bei die kleinste Zahl gefragt ist, so dass die Kongruenz für alle gilt. Wir haben aber nur ein spezielles vorliegen. Daher kann es auch noch kleinere Potenzen als geben.

Es ist nun so, dass mit die Zahl ein Element der Einheitengruppe ist. Die kleinste Zahl mit modulo ist gleichbedeutend mit der Ordnung des Gruppenelements . Das wiederum ist gleichbedeutend mit der Ordnung der zyklischen Gruppe . Da eine Untergruppe von ist, muss nach dem Satz von Lagrange die Zahl ein Teiler von sein.

Man berechnet nun die Teilerliste von und sucht nach dem ersten Teiler , für welchen modulo ist.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
from math import log
from fractions import gcd

# Eulersche Phi-Funktion als Ordnung der Einheitengruppe.
# Die Gruppe besteht genau aus den Gruppenelementen g mit
# ggT(g,m)=1.
def phi(m):
    order = 0        
    for g in range(1,m):
        if gcd(g,m)==1: order += 1
    return order

# Teilerliste
def divisors(n):
    return (d for d in range(1,n+1) if n%d==0)

def first_exponent(n,b):
    m = b**int(log(n,b)+1)
    for d in divisors(phi(m)):
        if pow(n,d,m)==1: return d

print(first_exponent(n=26036,b=165))
blackdrake Auf diesen Beitrag antworten »

Hallo Finn,

vielen Dank für diesen schönen Beweis!
Den eigentlichen Beweis (erste Antwort) habe ich gut verstanden.
Die zweite Antwort muss ich mir noch genauer anschauen, die ist etwas komplexer.

Ich mache mir wegen einer großen Potenz eigentlich weniger Sorgen. Super wäre es jedoch, wenn man die Basis auf 2..36 beschränken könnte, sodass man die Zahl mit dem Alphabet 0..9,A..Z notieren kann.

Kann man mit einer auf 2..36 beschränkten Basis für jede Zahl ein finden?
Finn_ Auf diesen Beitrag antworten »

Das läuft auf die Frage hinaus, ob die Kongruenz

für eine Lösung besitzt. Dann gilt
.

Die Kongruenz

besagt nun aber, dass im Restklassenring ein multiplikativ inverses Element mit und besitzen soll.

Gemäß dem Satz zum erweiterten euklidischen Algorithmus besitzt genau dann multiplikativ inverse Elemente, wenn ist.

Nun ist es aber so, dass die Potenz der Zahl ist, dass also verlangt wird, denn jeder Primteiler von wird auch in enthalten sein.

Gibt es ein Gegenbeispiel? Eine entsprechend hoch zusammengesetzte Zahl hat alle Zahlen 2, 3, ..., 36 in ihrer Teilerliste. Man braucht bloß zu berechnen und bekommt
144403552893600.

Eigentlich genügt es schon, wenn jeden Primteiler in 2, 3, ..., 36 einmal enthält. Man findet
200560490130.

Für diese Zahl sollte die Kongruenz unter der Einschränkung der Wahl der Basis unlösbar sein.

Sofern mir jetzt nicht irgendwo ein Fehler unterlaufen ist.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »