Chapter 14 - Continued Fraction Expansions of Quadratic Irrationals.sagews

Chapter 14 - Continued Fraction Expansions of Quadratic Irrationals

Example 14.11

c = continued_fraction_list((1+sqrt(21))/2,nterms=14)
c

[2, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1]

Example 14.14 - Fermat Factoring

ceil(sqrt(15251))

124

124^2-15251

125

sqrt(125)

5*sqrt(5)

N((sqrt(124^2-15251)))

11.1803398874989

125^2-15251

374

sqrt(374)

sqrt(374)

N(sqrt(374))

19.3390796058137

︠a34321f3-cbd2-43ad-b88c-ed83f20a42e3︠
126^2-15251

625

sqrt(625)

25

(126-25)*(126+25)

15251

Example 14.17 - Continued Fraction Factorization

d=320813
P0=0
Q0=1
a0=floor(sqrt(d))
p0=a0
[P0,Q0,a0,p0]

[0, 1, 566, 566]

P1=a0*Q0-P0
Q1=(d-P1^2)/Q0
a1=floor((P1+sqrt(d))/Q1)
p1=a1*a0+1
[P1,Q1,a1,p1]

[566, 457, 2, 1133]

P2=a1*Q1-P1
Q2=(d-P2^2)/Q1
a2=floor((P2+sqrt(d))/Q2)
p2=a2*p1+p0
[P2,Q2,a2,p2]

[348, 437, 2, 2832]

The function defined below will compute values of P_n, Q_n, and a_n as defined in Lemma 14.6 and outputs values of p_n (mod d) and the factorization of (-1)^n-1Q_n+1

def cf_congruences(d,k):
    P=[0]
    Q=[1]
    a=[floor(sqrt(d))]
    p=[a[0]]
    P.append(a[0])
    Q.append(d-(P[1])^2)
    a.append(floor((P[1]+sqrt(d))/Q[1]))
    p.append(a[1]*a[0]+1)
    for n in [1..k]:
        P.append(a[-1]*Q[-1]-P[-1])
        Q.append((d-P[-1]^2)/Q[-1])
        a.append(floor((P[-1]+sqrt(d))/Q[-1]))
        p.append(a[-1]*p[-1]+p[-2])
    return(table([(n,mod(p[n],d),factor((-1)^(n-1)*Q[n+1])) for n in [0..k]], header_row=["n", "p_n","(-1)^(n-1) Q_(n+1)"]))
    

cf_congruences(320813,15)

n p_n (-1)^(n-1) Q_(n+1) +----+--------+--------------------+ 0 566 -1 * 457 1 1133 19 * 23 2 2832 -1 * 101 3 29453 857 4 32285 -1 * 2^2 * 53 5 158593 449 6 28658 -1 * 2^2 * 79 7 244567 11 * 13 8 136562 -1 * 659 9 60316 2^2 * 109 10 196878 -1 * 19 * 31 11 257194 353 12 69640 -1 * 521 13 6021 2^2 * 11 * 13 14 75661 -1 * 251 15 233004 839