Number theory

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

egcd(240, 46)

(2, -9, 47)

# Fermat numbers and Euler's factor of F5
F = [2**(2**n) + 1 for n in range(7)]
print(F[5], F[5] % 641)

4294967297 0

# Modular inverse and RSA in a few lines
p, q = 2**127 - 1, 2**89 - 1
N, e = p * q, 65537
d = pow(e, -1, (p - 1) * (q - 1))
m = 1234567890123456789
c = pow(m, e, N)
pow(c, d, N) == m

True

# Pell's equation x^2 - D y^2 = 1 by continued fractions
from math import isqrt
def pell(D):
    a0 = isqrt(D); m, d, a = 0, 1, a0
    p0, p1, q0, q1 = 1, a0, 0, 1
    while p1*p1 - D*q1*q1 != 1:
        m = d*a - m; d = (D - m*m) // d; a = (a0 + m) // d
        p0, p1 = p1, a*p1 + p0
        q0, q1 = q1, a*q1 + q0
    return p1, q1

pell(61), pell(991)

((1766319049, 226153980), (379516400906811930638014896080, 12055735790331359447442538767))