Show description

Set β0 = a0 , γ0 = 1, β1 = a0 a1 + 1, γ1 = a1 , βi = ai βi−1 + βi−2 , γi = ai γi−1 + γi−2 , for i ≥ 2. Then 1) βi γi−1 − βi−1 γi = (−1)i−1 , i ≥ 1; 2) gcd(βi , γi ) = 1; 3) bi = βi and ci = γi , where bi , ci ∈ Z≥0 are such that gcd(bi , ci ) = 1 and bi ci Proof. 1) We use induction. For i = 1 we have β1 γ0 − β0 γ1 = (a0 a1 + 1)1 − a0 a1 = 1 = (−1)0 . For i ≥ 1 we get, using the induction hypothesis βi+1 γi − βi γi+1 = (ai+1 βi + βi−1 )γi − βi (ai+1 γi + γi−1 ) = βi−1 γi − βi γi−1 = −(−1)i−1 = (−1)i .

For α ∈ R, α > 0 and m ∈ Z, m > 0, we have m = √ n the following observation . ⌊α⌋ m Proof. Write α = u + β with u an integer and β ∈ R, 0 ≤ β < 1. Write u = qm + r with 0 ≤ r < m. Then u β r+β α = + = q+ =q m m m m because r + β < m and hence r+β m < 1. On the other hand, r u ⌊α⌋ = q+ = q. 19 We want to √ factorise n = 33. The continued fraction for 33: a0 = 5 a1 = 1 a2 = 2 a3 = 1 a4 = 10 √ −5 x ˜0 = x − a0 = 33 √ 5+ 33 1 x1 = √33−5 = 8 √ x ˜1 = x0 − a1 = −3+8 33 √ x2 = x11 = −3+8√33 = 3+ 3 33 x ˜ 2 = x1 √ − a2 = 3+ 33 x3 = 8 x ˜3 = x2 −√a3 = x4 = 5 + 33 ...

8 Let f ∈ k[x], then there exist c ∈ k, irreducible monic f1 , . . , fr ∈ k[x] and e1 , . . , er ∈ Z>0 with f = cf1e1 · · · frer . Moreover, this factorisation is “essentially unique”; meaning that if we have another one f = dg1d1 · · · gsds , then c = d, r = s, and after a permutation of the indices, fi = gi , ei = di . Proof. Note that c is the coefficient of the highest degree monomial in f , hence it is uniquely determined. So without loss of generality we may assume that f is monic. If f is irreducible then there is nothing to prove.