Elementare Zahlentheorie: Blatt 3

Aufgabe 1

crt([13,16], [51,49])

liefert das gesuchte Ergebnis. Alternativ kann man auch den chinesischen Restsatz manuell anwenden. In Sage geht das so:

(13*49*Integer(Mod(49, 51)^-1) + 16*51*Integer(Mod(51, 49)^-1)) % (49*51)

Aufgabe 2

Für Teil 2 erhalten wir aus den Lösungen modulo 71 bzw. 73 die Lösungen modulo 71·73=5183 mithilfe des chinesischen Restsatzes:

xs = [32,37]
ys = [36,41]
for a in xs:
    for b in ys:
        print crt([a, b], [71, 73])

Aufgabe 3

pr = [2,3,5]
counters = [0,0,0]
low = 50000
high = 1000000
for p in prime_range(low, high):
    for i in range(len(pr)):
        if Mod(pr[i], p).multiplicative_order() == p-1:
            counters[i] += 1

print [N(c/(prime_pi(high) - prime_pi(low))) for c in counters]

Aufgabe 5

Mit @interact könnt ihr euch die Primitivwurzeln module einer ausgewählten Primzahl zum Beispiel so anzeigen lassen:

def list_of_primitive_roots(p):
    result = []
    for a in [2..p-1]:
        if Mod(a, p).multiplicative_order() + 1 == p:
            result.append((p,a))
    return result

@interact
def pw_dist(p=slider([a for a in [3..100] if a.is_prime()])):
    show(scatter_plot([(a,1) for (b,a) in list_of_primitive_roots(p)],
                      markersize=10, xmin=0, xmax=p))

Alternativ könnt ihr euch auch die Plots für verschiedene Primzahlen gleichzeitig anzeigen lassen:

scatter_plot(sum([list_of_primitive_roots(p) for p in prime_range(5, 100)], []))