import math

def euklid(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = euklid(b, a % b)
        return (d, y, x - (a // b) * y)

p = 685969
q = 536101

n = p * q
phi_n = (p - 1) * (q - 1)

# Find an e that fits, 5000 is arbitrary in this case
for i in range(5000, phi_n):
    if math.gcd(i, phi_n) == 1:
        e = i
        break

# Find the d
_, d, _ = euklid(e, phi_n)

print("n = ", n)
print("phi(n) = ", phi_n)
print("e = ", e)
print("d = ", d)