Elementare Zahlentheorie: Blatt 10

Aufgabe 1

def find_solution(a,b,c, N=10, all=False):
    """Löse ax^2+by^2+cz^2=0 mit 1≤x,y,z≤N, nicht alle 0, wobei standardmäßig
    N=10 ist."""
    results = []

    # Iteriere einfach über alle möglichen (x,y,z) im zu relevanten Bereich.
    for x in range(1, N):
        for y in range(1, N):
            for z in range(1, N):
                if x == y == z == 0:
                    continue
                if a*x^2 + b*y^2 + c*z^2 == 0:
                    if all:
                        results.append((x,y,z))
                    else:
                        return (x,y,z)

    return results

# Suche nach allen Lösungen mit Koordinaten ≤ 10
for lst in [(3, -10, 13), (5, 7, -13), (-7, 11, 13)]:
    print find_solution(*lst, all=True)

Das liefert die Ausgabe
[(1, 8, 7), (3, 2, 1), (6, 4, 2), (7, 4, 1), (9, 6, 3)]
[(1, 4, 3), (2, 8, 6), (3, 1, 2), (5, 7, 6), (6, 2, 4), (9, 3, 6)]
[(3, 1, 2), (4, 3, 1), (6, 2, 4), (8, 6, 2), (9, 3, 6)]

Aufgabe 2

Alternativ zur Funktion aus dem Skript geht es auch auch etwas kürzer:

def fundamental_solution(n):
    "Finde die Fundamentallösung von x^2-nx^2=1, wobei n kein Quadrat ist."
    # Definiere Polynomring über ℚ
    R.<x> = QQ[]
    # und erweitere ℚ um √n
    K.<a> = NumberField(x^2-n)
    # Berechne die multiplikative Gruppe von K
    G = K.unit_group()

    # G.1 ist der Erzeuger der zu ℤ isomorphen Untergruppe von K^*
    return list(K(G.1))

x, y = fundamental_solution(571)
assert(x^2-571*y^2 == 1)
(x,y)

Mit den Mitteln aus der Vorlesung kann man das Problem aber mit dem Programm aus dem Skript lösen:

def Pell_fs(n) :
    """Returns the fundamental solution of xˆ2−ny ˆ2=1."""
    U = lambda a : matrix (ZZ, 2, [a, 1, 1, 0])
    phi = lambda x : 1 / (x - floor(x))
    w = QQbar(sqrt(n))
    s = phi(w); lst = [w, s]
    k = 2; t = phi(s)
    while is_even(k) or t != s:
        lst.append(t)
        k += 1; t = phi(t)
    cf = map(lambda t : floor(t) , lst)
    M = prod(U(a) for a in cf)*U(cf[0])^-1
    return M[0,0], M[1,0], len(cf)-1

(x,y,n) = Pell_fs(571); (x,y,n)

Das Ergebnis kann man schön ausgeben lassen mittels

print 'x = {:27,}\ny = {:27,}'.format(int(x), int(y)).replace(",", " ")

Das liefert als Ausgabe x und y als 27-stellige Zahl mit führenden Leerzeichen und Zifferngruppierung.

Aufgabe 3

Finde mithilfe der Parametrisierung pythagoräische Tripel und sammle die dabei gefundenen Kongruenzzahlen. Dabei werden zunächst quadratfreie Kongruenzzahlen gesucht und diese anschließend mit allen in frage kommenden Quadraten multipliziert werden.

def find_congruent_numbers(N=100, k=100):
    # Menge der gefundenen Kongruenzzahlen
    congruent_numbers = set()

    for p in range(1, N):
        for q in range(1, p):
            if gcd(p, q) != 1:
                continue

            # a = (p^2-q^2), b = 2*p*q ⇝ n = ab/2 = (p^2-q^2)pq
            n = (p^2-q^2)*p*q

            if n.is_integral():
                n = n.squarefree_part()
                if n > k:
                    continue
                congruent_numbers.add(n)

    for c in list(congruent_numbers):
        for square in [x^2 for x in ([2..9] + [2*3, 2*4, 3*3, 2*5])]:
            if c*square <= k:
                congruent_numbers.add(c*square)

    return congruent_numbers

# Berechne nun für 0<p,q<1000 die auftretenden Kongruenzzahlen.
S = find_congruent_numbers(1000); print S
print len(S)

So findet man 33 der insgesamt 50 Kongruenzzahlen ≤100: 5, 6, 7, 13, 14, 15, 20, 21, 22, 24, 28, 30, 34, 39, 41, 45, 46, 52, 54, 55, 56, 60, 63, 65, 69, 70, 78, 80, 84, 85, 86, 88, 96.