Berechnen Sie mit Python den Rest von a^(p-1) bei der Division durch p.

Question

Kleiner Satz von Fermat:

Wählen Sie eine beliebige Primzahl p und eine Zahl a, die kein Vielfaches von p ist. Berechnen Sie mit Python den Rest von a^(p-1) bei der Division durch p. Überprüfen Sie, ob das Ergebnis 1 ist und geben Sie den entsprechenden Wahrheitswert aus.

Weiß jemand, wie man das auf Python machen könnte. Mathematisch kann ich das zeigen, dass das Ergebnis 1 ist, aber ich weiß nicht, wie das auf Python funktioniert.

Comments

p = 7
a = 3

print(a**(p-1) % p == 1)

Answer 1

Antwort mit KI erzeugt

Um das gestellte Problem mit Python zu lösen, können wir eine Funktion definieren, die den Kleinen Satz von Fermat überprüft. Diese Funktion nimmt zwei Argumente entgegen: eine Primzahl \(p\) und eine beliebige Zahl \(a\), die kein Vielfaches von \(p\) ist. Die Funktion berechnet dann \(a^{(p-1)} \mod p\) und überprüft, ob das Ergebnis gleich 1 ist.

Hier ist ein Beispielcode, der das beschriebene Verhalten implementiert:

python
def fermats_little_theorem(a, p):
    """
    Überprüft den Kleinen Satz von Fermat, der besagt, dass für jede Primzahl p
    und jede ganze Zahl a, die kein Vielfaches von p ist, gilt:
    a^(p-1) % p = 1.
    
    :param a: Ganze Zahl, die kein Vielfaches von p ist
    :param p: Primzahl
    :return: Wahrheitswert, der angibt, ob a^(p-1) % p = 1 ist
    """
    # Berechnung von a^(p-1) modulo p
    result = pow(a, p-1, p)  # Die pow-Funktion unterstützt auch die Modulo-Operation
    
    # Überprüfen, ob das Ergebnis 1 ist
    return result == 1

# Beispiel
p = 7  # Beispiel für eine Primzahl
a = 3  # Beispiel für eine Zahl, die kein Vielfaches von p ist
ergebnis = fermats_little_theorem(a, p)

print(f"Das Ergebnis der Überprüfung des Kleinen Satzes von Fermat für a = {a} und p = {p} ist: {ergebnis}")

Dieses Script definiert eine Funktion fermats_little_theorem(), die überprüft, ob \(a^{(p-1)} \mod p = 1\) ist, was dem Kleinen Satz von Fermat entspricht. Beachten Sie, dass wir die eingebaute pow-Funktion von Python verwenden, um \(a^{(p-1)}\) effizient zu berechnen und gleichzeitig den Rest der Division durch \(p\) zu bestimmen. Diese Methode ist effizienter als die einfache Berechnung von \(a^{(p-1)}\) und dann die Nutzung des Modulo-Operators, da sie eine Optimierung für große Zahlen und exponentielle Operationen verwendet.