temaC1

# Hello World program in Python
import math

def modulo(x, n):
    if x % n > (n//2):
        return int((x % n) - n)
    else:
        return int(x % n)

def factors(n):
    a = []
    i = 2

    while True:

      c = 0

      while n % i == 0:
            c = c + 1
            n = n / i

      if c != 0:
         a.append([i,c])

      i = i + 1

      if n == 1:
         break
    return a



def compute_table(m):
    b_1 = 1
    a = []
    a0 = b0 = int(math.sqrt(m))
    x0 = math.sqrt(m) - int(math.sqrt(m))
    b_patrat = modulo(b0*b0, m)
    a.append({"a":a0, "b":b0, "x":x0, "b^2":b_patrat})

    a1 = int(1/x0)
    x1 = 1/x0 - a1
    b1 = a1*b0 + b_1
    b1_patrat = modulo(b1*b1, m)
    a.append({"a":a1, "b":b1, "x":x1, "b^2":b1_patrat})

    for i in range(2,16):
        ai = int(1/a[i-1]["x"])
        xi = 1/a[i-1]["x"] - ai
        bi = ((ai*a[i-1]["b"] + a[i-2]["b"]) % m)
        bi_patrat = modulo(bi*bi, m)
        a.append({"a":ai,"b":bi,"x":xi,"b^2":bi_patrat})


    for i in range(0,16):
        print(a[i])
        if(a[i]["b^2"] < 0):
            print(a[i]["b^2"], factors((-1)*a[i]["b^2"]))
        else:
            print(a[i]["b^2"], factors(a[i]["b^2"]))

compute_table(7601)