CH9 Some other rings of integers

Question 1

Definition 9.1.1
Z[√d]

Answer 1

Let d ∈ Z and assume that d is not a square. We define

Z[√d] :={a + b√d : a, b ∈ Z}

We remark that if α, β ∈ Z[√d] Then so are α ± β and αβ,
shows Z[√d]is a subring of C.

(The case when d = −1 is simply the ring of Gaussian integers Z[ı].)

Question 2

Z[√d] aside

Answer 2

Z[√d] is an integral domain, we have the notions of units, divisors and greatest common divisors. However, greatest
common divisors do not always exist (see Theorem 9.1.5 for some details).

Question 3

Definition 9.1.2
norm on Z[√d]

Answer 3

norm on Z[√d]

N(a + b√d):= |a² − db²|

Question 4

norm on Z[√d]

N(a + b√d):= |a² − db²|

when d<0

Answer 4

norm is
|a − b√d|²

the square of the absolute
value of a complex number. If d > 0, however, this norm is something new.

so if d=-1 recover gaussian integers
if d is a square recover integers?

if d<0 we get the norm of complex numbers
if d>0 and ot squared like 7 then this function is different

Question 5

property:
norm on Z[√d]

Answer 5

Just like with the ring of Gaussian integers, we have that N(αβ) = N(α) N(β).

N(α) = 0 if and only if α = 0,

and similarly

α is a unit if and only if N(α) = 1.

Question 6

remark in Z[√d]

Answer 6

Any prime element in Z[√d]
is irreducible, but in general irreducible elements need
not be prime

Question 7

Theorem 9.1.3
using division algorithm Z[√d]

When can we use it?

Answer 7

If d is one of −1, ±2, 3,

then the division algorithm holds forZ[√d]. That is,
given elements α, β ∈ Z[√d]
with β ̸= 0, there are q,r ∈ Z[√d]
with α = qβ + r
and 0 ≤ N(r) < N(β)

Question 8

PROOF
Theorem 9.1.3
using division algorithm Z[√d]

When can we use it?

If d is one of −1, ±2, 3,

then the division algorithm holds forZ[√d]. That is,
given elements α, β ∈ Z[√d]
with β ̸= 0, there are q,r ∈ Z[√d]
with α = qβ + r
and 0 ≤ N(r) < N(β)

Answer 8

for every d ∈ {−2, −1, 2, 3}, we have order strictly smaller than 1
|0.25/0.25d|<1

choose α, β in Z[√d] ith β ̸= 0
α/β= A+ B√d with A, B ∈ Q
choose a, b ∈ Z with
|a-A| ≤ 0.5
|b-B| ≤ 0.5
closest integers to them
set
q := a + b√d
r := α − qβ.
N(r) = N(α − qβ)
=N((A+B√d)β -(a+b√d)β)
multiplicative property
=||a-A|²-d|b-B|²| N(β)
≤((0.5)² -d(0.5)²)N(β)
<N(β)

Just to note:
there is a distinction between this for euclids integers- here not stated unique, if we fix the norm and two possibilities + or0 for integers we have uniqueness as choose positive

here no such thing as + or - can’t choose

Question 9

remark 9.1.4.

Answer 9

This argument will fail for d = −3, because the first observation does not
hold in that case. In fact, we will see later on in Remark 9.1.7 a result showing that the
ring Z√−3 cannot have a division algorithm

Question 10

Theorem 9.1.5 (Bézout’s lemma: a more general version)

Answer 10

Let d be one of −1, ±2, 3.

Any two α, β ∈ Z[√d] have a greatest common divisor
γ.

Moreover γ = sα + tβ for some s, t ∈ Z[√d]

Question 11

PROOF
Let d be one of −1, ±2, 3.

Any two α, β ∈ Z[√d] have a greatest common divisor
γ.

Moreover γ = sα + tβ for some s, t ∈ Z[√d]

Answer 11

consider the set of all possible combos
{sα+tβ s.t a,t in Z[√d] }
choose γ in this set with smallest positive norm

Proof. (Identical to Theorem 8.3.6!) I
) If α = β = 0, just take γ = 0, so suppose that one of α, β is not zero. Among all numbers γ = sα + tβ with s, t ∈ Z[√d]
pick one with N(γ) positive and minimum possible.

First, we claim that γ | α. By Theorem 9.1.3, α = qγ + r where N(r) < N(γ).

Then
r = α − qγ = α − q(sα + tβ) = (1 − qs)α − qtβ,
(clearly r belongs to the original set, r must be 0!)
thus N(r) = 0 because of the minimality of N(γ).

Hence γ | α. Similarly, γ | β, so γ is
a common divisor.

checking greatest:
Now if δ is another common divisor, then δ | (sα + tβ) = γ.

Question 12

Theorem 9.1.6

Answer 12

Let d be one of −1, ±2, 3. For every α ∈ Z[√d]
, α is irreducible if and only if α is
prime.

proof: irreducible always prime prev lemma 8.1.13
converse: suppose …. (didnt save?)

. (Identical to Corollary 8.3.9!) First suppose that α is irreducible, that α | βγ, and that α ∤ β. Let δ be a greatest common divisor of α and β. Write α = δϵ: since α is irreducible, one of δ, ϵ is a unit. Since δ | β and α ∤ β, δ must be the unit.
We have determined that a greatest common divisor of α and β is 1. Write it as 1 = sα + tβ. Then sαγ + tβγ = γ. Since α divides the left hand side, we find that α | γ. This
shows that α is prime.

Question 13

Let d be one of −1, ±2, 3. For every α ∈ Z[√d]
, α is irreducible if and only if α is
prime.

Answer 13

Let d be one of −1, ±2, 3. For every α ∈ Z[√d]
, α is irreducible if and only if α is
prime.

proof: prime is always irreducible prev lemma

suppose it divides the product but show it does not divide one of the fators:

we know existence by bezouts
we use alpha as irreducible meaning one of them has to be a unit, delta or epsilon
delta divides bete and alpha divides beta * gamme so impossible that epsilon is a unit as implies epislon in invertible but alpha divides beta… cuts offf

implication: supposeα is irreducible, that α | βγ,
and that α ∤ β. Let δ be a greatest common divisor of α and β. Write α = δϵ: since α is
irreducible, one of δ, ϵ is a unit. Since δ | β and α ∤ β, δ must be the unit.
We have determined that a greatest common divisor of α and β is 1. Write it as 1 =
sα + tβ. Then sαγ + tβγ = γ. Since α divides the left hand side, we find that α | γ. This
shows that α is prime.
Conversely, suppose now that α is prime. The result follows by Lemma 8.1.13. □

Question 14

prime means irreducible?

Answer 14

yes
IFF

Question 15

irreducible means prime?

Answer 15

yes
IFF

Question 16

.
Theorem 9.1.8 (Fundamental theorem of Arithmetic: a more general version)

When can we use FTOA

Answer 16

Suppose d = −1, ±2, 3, then the Fundamental Theorem of Arithmetic holds in Z[√d]
That is to say, if α ∈ Z[√d]
is not zero and not a unit, we can write
α = π_1 · · · π_r
where each πi
is prime in Z[√d]. Moreover, if
α = σ_1 · · · σ_s
is also a product of primes, then r = s and, after rearranging the factors, we have
σ_i = u_iπ_i
for some units u_i ∈ Z[√d]

(uniqueness is missing here, we use units here instead add or remove units is allowed)

Question 17

in Z√−3 can we find division algortithm?

is element 2 prime or irreducible?

Answer 17

(here the equivalent prime IFF irreducible doesnt hold!)

the element 2 is irreducible but not prime, and so
Z√−3 does not have a division algorithm
2 is irreducible in Z√−3

Proceed by contradiction, so
suppose that we can write 2 = βγ with β and γ not units, then 4 = N(2) = N(β) N(γ),
(2 positive integers, 1,4,2 only one way)
and since β, γ are not units, N(β), N(γ) > 1. Thus N(β) = N(γ) = 2. But this is impossible, for if β = a + b√−3, then N(β) = a^2 + 3b^2, and there are no a, b ∈ Z such that this is 2, these are positive. This shows that 2 is irreducible.

Now we will show that 2 is not prime in Z√−3 . Observe that,(1 +√−3)(1 −√−3)= 4, so
2 |(1 +√−3)( 1 −√−3).
2 doesn’t divide these factors though as coefficients of terms aren’t even numbers.

notes: If there was α ∈ Z√−3
satisfying 1 ±√−3 = 2α, we would have that 4 = N
1 ±√−3 = N(2) N(α) = 4 N(α), so N(α) = 1. But the only
way that a, b ∈ Z satisfy a^2 + 3b^2 = 1, then is if a = ±1 and b = 0. This shows then that
2 ∤ 1 ±√−3, so 2 is not prime in Z√-3

Question 18

thm 9.2.1

is: which numbers can be written in the form
x^2 +2y^2

Answer 18

A positive integer n can be written in the form
x² + 2y² with x, y ∈ Z
if and only if
primes of the form 8k + 5 and 8k + 7 have even exponent in the factorisation of n

if a number can be written n this form then the primes of those types are even powers
(Note its a special case of the sum of 3 squares)

Question 19

PROOF
A positive integer n can be written in the form
x² + 2y² with x, y ∈ Z
if and only if
primes of the form 8k + 5 and 8k + 7 have even exponent in the factorisation of n

Answer 19

Being written in this form is the same as saying its the norm of something in the form:
n=x² + 2y²
IFF
n=N(a+√-2 b)
lets prove this:

Question 20

Being written in this form is the same as saying its the norm of something in the form:
n=x² + 2y²
IFF
n=N(a+√-2 b)
lets prove this:

Answer 20

converse: we can show the prime divisors have this property, thus N will as the norm is multiplicative and we can write the prod in this way.
2=0²+2x1²
m²=m²+2x0²

left to show that if p is prime in Z and congruent to 1 or 3 mod 8
then p=X^2+2Y^2 for some X and Y

Legendre’s symbols:
(-2/p)=1 (exercise)
so X² ≡-2 mod p
ie
p| X²+2
=(X+√2)(X-√-2)
but p doesn’t divide these factors as coefficients arent multiples of p
so p is not prime in Z[√-2 ]

This ring has the division algorithm, so not prime means not irreducible as here theyre the same
So p is not irreducible so p = aβ a,b non units
p^2=N(p) =N(a)N(β)
so N(a)=p

implication direction:
Suppose n= x²+2y²
take p| n (p prime in integers)
with p≡5 or 7 mod 8
(-2/p)=-1

on the other hand, because n is of the given form,
x²+2y²≡0 nod p
X²≡-2y² mod p

if p does not divide y then p and y are coprime GCD(p,y)=1 so y has multiplicative invers mod p
So i can take
X²y⁻²≡-2 mod p

This contradicts (-2/p)=-1 QR
as -2 is now written as a square
so p|y

p^2 | n
so p|x
finish by induction

Question 21

□
Example 9.2.2
using the thm to write 113

Is 113 prime in Z[root -2]

Answer 21

step 1 check conditions
113 is prime in Z and congruent to 1 mod 8
so I can write in the form x^2+2y^2

(-2/113)=-1 tells us its a QR
step 2
26^2=676≡ -2 mod 113

just by trying numbers it can be hard
step 3
so 113| (26^2 + 2
=(26+√-2)(26-√-2)

but 113 doesnt divide either factor, coeffs arent factors
meaning that113 is not prime in Z√−2

step 4
so
113=
(9+4√-2)(9-4√2-)

step 5 we can apply the norm
because113 is prime and we know they are not units
N(9+4√-2)=113
as 9^2 +2(4^2)=113

Question 22

Theorem 9.2.3
missed?

Answer 22

The only integer solutions of x^2 + 2 = y^3 are x = ±5, y = 3.

Question 23

Eisenstein integers

(ring of)

Answer 23

Let ω:= (-1+√−3)/2 = exp(2πi/3)
this is a primitive cubic root of unity

ω²+ ω+1=0 and ω³=1

ring of Eisenstein integers
Z[ω] := {a + bω : a, b ∈ Z}.
If α, β ∈ Z[ω] then so are α ± β and αβ, so it is a subring of C.

Question 24

ring of eisenstein integers
norm defined

Answer 24

We define the norm on Z[ω] by
N(a + bω) := a² − ab + b² = |a + bω|²
= (a + bω)(a + bω²).
Again N(αβ) = N(α) N(β).

Question 25

Lemma 9.3.2 (Units of Eisenstein integers)

Answer 25

Thus, the units in Z[ω] are
±1, ±ω, and
±ω^2 = ±(1 + ω)

Proof. Let α = a + bω be a unit in Z[ω]. From N(α) = 1 we obtain a^2 − ab + b^2 = 1.
Using a^2 + b^2 ≥ 2|ab|, it is easy to see that ab = 0 or ±1.

(only options for this are 0 and 1,-1)

As a result, the only solutions
for (a, b) are (±1, 0), (0, ±1), (1, 1), (−1, −1).

Question 26

Theorem 9.3.3 (Division algorithm for Eisenstein integers)

Answer 26

Let α, β ∈ Z[ω] with β ̸= 0. Then there are q,r ∈ Z[ω] (the “quotient and remainder”) such that α = qβ + r and 0 ≤ N(r) < N(β).

Question 27

Theorem 9.3.4 (Euler, 1770)

Question 28

PROOF
Let α, β ∈ Z[ω] with β ̸= 0. Then there are q,r ∈ Z[ω] (the “quotient and remainder”) such that α = qβ + r and 0 ≤ N(r) < N(β).

division algorithm for Eisenstein integers

Answer 28

Take α,β in Z[ω]
α = p + qω and β = r + sω t β not equal to 0

α/β in Q[ω] field
α/β= [(p + qω)/(r + sω)] ·[(r + sω^2)/(r + sω^2)] =
(p + qω)(r + sω^2))/N(β)
= A + Bω
with A, B ∈ R. (Q in lectures?)

Choose integers a, b with
|a − A| ≤ 1/2 and |b − B| ≤ 1/2
Then
set quotient=a+bω and remainder =a- quotientβ
N(r) = N(a- quotientβ)
N(α/β - (a+bω))
= N((A-a) +(B-b)ω)
≤ (1/2)^2 +(1/2)^2 +(1/2)^2 = 3/4
Take q = a + bω and r = α − qβ ∈ Z[ω]. Then N(r) ≤ (3/4) N(β).

Question 29

Theorem 9.3.4 (Euler, 1770)

Answer 29

The equation x^3 + y^3 + z^3 = 0 does not admit integer solutions with xyz ̸= 0.

proof is extra….
* 3 has to divide xyz mod 9
* 3 diivides only one factor

Question 30

defn 9.4.1 Pell’s eq

Answer 30

Let d be a positive integer which is not a square. Pell’s equation is
x² − dy² = 1

this is a Diophantine eq
x,y in Z
if d is a square we can easily factorise
(x-ky)(x+ky) =1 so only plus or -1 factors

another way to say pells equation is those such that norm =1

to solve we need to find the units of the ring

Question 31

We know units of Z[√d] are numbers of the form a +b√d with

Answer 31

We know units of Z[√d] are numbers of the form a +b√d with
N(a+b√d) = a ^2 -db^2 = +or - 1

pells equation LHS is precisely the norm of an element in the ring

Furthermore, by the multiplicative property of the norm, given two solutions, the
product of the corresponding units gives another solution to Pell’s equation. Similarly,
taking powers (including negative powers) of a unit will also produce solutions.

Question 32

Example 9.4.2. Consider Pell’s equation for d = 2

Answer 32

3^2 − 2 · 2^2 = 1 corresponds
to the unit 3 + 2√2 and that 172 − 2 · 122 = 1 corresponds to the unit 17 + 12√2. Their
product is
(3 + 2√2)(17 + 12√2)
= 3 · 17 + 2 · 2 · 12 + (3 · 12 + 2 · 17)
√2 = 99 + 70√2
corresponding to the solution 99^2 − 2 · 70^2 = 1.

Question 33

Exercise 9.4.3. Suppose that d is either a negative integer or a non-zero square. Show
that the equation x
2 − dy2 = 1 only has a finite number of integer solutions.

Answer 33

Skipped…

Question 34

DEF 9.5.1
A continued fraction

Answer 34

A continued fraction is an expression of the form
a₀+ [1/[a₁+ [1/a₂+……+[1/aₙ₋₁+[1/aₙ+……….
where
a₀,…aₙ,… are reals
a₁,..,aₙ,… are all positive
a₀ can be any reak
(partial quotients or coefficients )

finite continued fraction
If the list of coefficients terminates, then we say that this is a finite continued fraction. On the other hand, if the list of coefficients is infinitely long, then we say
that this is an infinite continued fraction

a continued fraction is simple if a₀,…,aₙ are all integers

Question 35

a continued fraction is simple if

Answer 35

a continued fraction is simple if a₀,…,aₙ are all integers

Question 36

finite continued fraction

Answer 36

If the list of coefficients terminates, then we say that this is a finite continued
fraction. On the other hand, if the list of coefficients is infinitely long, then we say
that this is an infinite continued fraction

Question 37

notation of continued fraction

Answer 37

[a₀;a₁,…aₙ,…]
:=a₀+ [1/[a₁+ [1/a₂+……+[1/aₙ₋₁+[1/aₙ+……….

we only need to note the coefficients

if finite last coefficient write [a₀;a₁,…aₙ]

Question 38

Lemma 9.5.2
division algorithm

Answer 38

Given m, n ∈ Z with n > 0, denote the corresponding division algorithm
m=r₀=q₂r₁ +r₂ where 0 r₂<r₁=n
r₁=q₃r₂+r₃ where 0≤ r₃ <r₂
…..
r_l = q_{l+2}r_{l+1} +r_{l+2} where 0 ≤ r_{l+2}<r_{l+1}
….
r_{k-1}=qₖ₊₁rₖ

then we can writhe m/n as finite simple continued frction
m/n= [q₂;q₃,…qₖ₊₁]

Question 39

proof of division algorithm with continued fractions

Answer 39

m/n
= q₂ +r₂/r₁
=q₂+ 1/(₁r₃/r₂)
=q₂ + [1/(q₃ +(r₃/r₂) +…..
=[q₂;q₃,…qₖ₊₁]

taking apart fraction sep into parts again and again

Question 40

every rational number can be written as a finite continuous fraction

Answer 40

every rational number can be written as a finite continuous fraction

and a finite continued fraction
this is a finite sum/sequence of rational numbers

a real number is rational IFF continued fraction is finite

Question 41

Corollary 9.5.3.

When is x rational

Answer 41

Corollary 9.5.3. Let x denote a real number. Then x is rational if and only if x can be
written as a finite simple continued fraction

Question 42

Example 9.5.4. We will show how to write 289/119 as a finite continued fraction.

Answer 42

skipped?
perform Euclids division algorithm
289=2119 +51
119=251+17
51=3*17

289/119=
2 + 51/119
= 2 + 1/(119/51)
= 2 + 1/(2 + (17/51))
= 2+ 1/(2 +(1/3))
=
[2;2,3]

we could also write rational numbers as
[2;2,3] = [2;2,2,1]
since 3 = 2 + 1/1 .

Question 43

pi as a continued fraction

Answer 43

irrational number and goes on forever
3.14.159

3+ 0.1415926….
3+ (1/7.062513…)
3+ 1/7( + 1/(15.99659976+…

= [3;7,15,1,292,1,1,…].

so can’t be a finite continued fraction as irrational

these offer a way to code a number

Question 44

benefits of continued fractions

Answer 44

vs a decimal number
every rational number has a finite continued fraction expansion

1/3 cannot be written as finite but infinite decimal expansion 0.33333….

Question 45

def 9.5.6
periodic continued fractions

Answer 45

infinite continued fraction
[a₀; a₁, . . . , aₙ, . . .] is
periodic
if there exists a positive integer m such that for all n ≥ 1 we have
aₙ₊ ₘ = aₙ. In this case, the smallest value of m satisfying this condition is called the period of the continued fraction. We denote a periodic continued fraction of period m as
[a₀;a₁,…,aₘ,a₁,…] =
________
[a₀;a₁,…,aₘ]

overline from 1 to m

only need to consider first n values,repeates

Question 46

example periodic continued fraction with all coefficients equal to 1

Answer 46

α = [1;1,1,1,1,1,…] = [1;1_overline] = 1+ 1/(1+1/(1+…

periodic
due to periodicity, the part below also equals alpha
note
α=1+1/α
so α is the golden ratio
α=(1+ sqrt(5))/2
alpha has to be positive

if we have a periodic continued fraction we can always find an equation in alpha

Question 47

quadratic equation from a periodic continued fraction

Answer 47

if we have an infinite periodic fraction

alpha= 1+(… something with alpha

we can always find an equation for alpha which is going to be quadratic

if a simple continued fraction is periodic then its value satisfies a quadratic equation with integer coefficients

Question 48

Irrational numbers can always be written uniquely as an infinite simple continued fraction.

Answer 48

If x Is an irrational number, we begin by considering the integer part
a_0 := ⌊x⌋if x > 0
or
a_0 := ⌊x⌋+1if x < 0.

Then the number x−a_0 is both positive and smaller than 1, so define
a_1 := ⌊1/(x-a_0)⌋. Then we define

a_2:= ⌊1 /((1/(x-a_0)) -a_1 ⌋
By repeating this process one can obtain the representation of x as a continued frac- tion.

Question 49

definition 9.5.9

kth convergent

Answer 49

Given an infinite continued fraction [a₀; a₁, . . . , aₙ, . . .] and k ∈ N, we define the k-th convergent as the finite continued fraction defined by a₀, a₁, . . . , aₖ:
C_k :=[a₀;a₁,…,aₖ].

take the sequence up to k

Question 50

Proposition 9.5.10. Given an infinite continued fraction (not necessarily simple)

Answer 50

Proposition 9.5.10. Given an infinite continued fraction (not necessarily simple)
[a₀; a₁, . . . , aₙ, . . .]
C_k sequence of convergents

define pₖ and qₖ by setting
p₀:= a₀
q₀:=1
p₁:= a₀a₁ +1
q₁:= a₁

and recurrence relations
pₖ:= aₖpₖ₋₁+pₖ₋₂
qₖ:= aₖpₖ₋₁ +qₖ₋₂
for k>1

Then Cₖ=pₖ/qₖ for all k in M

• so we take continued fraction up to k (kth convergent)
  *algorithm for computing this value efficiently without writing out all fractions
• build the sequence of integers following this rule will give you the kth convergent
  *proof too long we miss by induction

Question 51

proof was extra but discussed

why does this work let’s spend some time on it?

continued fracctions
Proposition 9.5.10. Given an infinite continued fraction (not necessarily simple)

[a₀; a₁, . . . , aₙ, . . .]
C_k sequence of convergents

define pₖ and qₖ by setting
p₀:= a₀
q₀:=1
p₁:= a₀a₁ +1
q₁:= a₁

and recurrence relations
pₖ:= aₖpₖ₋₁+pₖ₋₂
qₖ:= aₖpₖ₋₁ +qₖ₋₂
for k>1

Then Cₖ=pₖ/qₖ for all k in M

Answer 51

by induction on k
k=0 defn C₀=[a₀]=a₀/1 =p₀/q₀

k=1 continued fraction
[a₀,a₁]
=C₁=a₀ +(1/a₁)
= (a₀a₁+1)/a₁ =p₁q₁

assume statement true for some value of k,
Cₖ =[x₀,x₁,…xₖ] =p’ₖ/q’ₖ
( they are not necessarily integers!, here p’ₖ and q’ₖ are instead defined on x’s)

consider
Cₖ₊₁ = [a₀,a₁,..aₖ₊₁] for k+1 terms
=[a₀, a₁,…,aₖ + (1/aₖ₊₁)] for k terms, we can do as reals

thus by induction hypothesis with
xₖ = aₖ + (1/aₖ₊₁)]
=[aₖpₖ₋₁+pₖ₋₂]/[aₖpₖ₋₁ +qₖ₋₂]
=[ (aₖ + (1/aₖ₊₁))pₖ-₁ + pₖ₋₂]/
[(aₖ + (1/(aₖ₊₁))qₖ-₁ +qₖ₋₂]
= pₖ₊₁/qₖ₊₁

Question 52

So if we are writing a number alpha as an infinite continued fraction

how good are our approximations?

Answer 52

Cₖ will converge to alpha as k tends to infinity

Cₖ’s will approximate alpha

we have shown Cₖ =pₖ/qₖ

best approximation of alpha among all rational numbers whose denominator is at most q_n

e.g square root 7 between 2 and 3, we can approximate using convergence
from the magic table one of the approximations is 8/3

suppose we fix denominator by 3: but allow any integer in numerator , can we find a better approximation?

Question 53

e.g square root 7 between 2 and 3, we can approximate using convergence
from the magic table one of the approximations is 8/3

suppose we fix denominator by 3: but allow any integer in numerator , can we find a better approximation?

Answer 53

no, best apporox using solution found from table

best rational number/closest approx

converges have the property that they are good approximations as long as you bound the denominator

Question 54

Theorem 9.5.11
√d

Answer 54

Let d be a positive integer that is not a square.

Then the infinite continued fraction for √d is periodic

(equivalent to √d being irrational, converse of the thm that says if periodic then there is a quadratic equation for it)

Question 55

Example 9.5.12. We will now find the continued fraction for √7

Answer 55

procedure is always the same

integer part of x ⌊x⌋

a₀= ⌊√7⌋= 2,
a₁= ** ⌊1/((√7)-2)⌋** = ⌊(2+√7)/3 ⌋=1 invert the fractional part and take integer part
a₂= ⌊1/((2+√7)/3-1)⌋ = ⌊(1+√7)/2 ⌋=1
a₃= ⌊1/((1+√7)/2-1)⌋ = ⌊(1+√7)/3 ⌋=1
a₄= ⌊1/([1+√7]/3)-1)⌋ = ⌊2+√7⌋=4
a₅= ⌊1/(2+(√7)-4)⌋ = ⌊1/[(√7)-2] ⌋=1
and here we observe that the coefficients will repeat with period 4, so
√7 = [2; 1, 1, 1, 4, 1, 1, 1, 4, . . .] = [2; (1, 1, 1, 4)_overline]

here the fractional part, inverted, minus the integer part and find the integer part of it

rationalising the denominator as you go

with square roots of integers will always eventually repeat
period m=4

Question 56

Theorem 9.6.1

HOW TO SOLVE PELLS EQUATION

Answer 56

Theorem 9.6.1
Assume d is a positive integer which is not a square.

Let m denote the period of the continued fraction of √d, and let pₖ and qₖ be defined as in Proposition 9.5.10.

Then an integer solution of

x² − dy² = 1 is given by
(x, y) =

{(pₘ₋₁, qₘ₋₁) , if m is even
{(p₂ₘ₋₁, q₂ₘ₋₁) , if m is odd

Gives you one sol: we could figure out more as
(units form a multiplicative subgroup: closed under multiplication, given one solution to pells this corresponds to one unit in the ring, if we square this this will also be a solution

Question 57

Example 9.6.2. Let us find integer solutions to
x² − 7y²2 = 1.

d=7

Answer 57

root 7 has period 4
[2;(1114)_overline]

find the sequences we need using formulae
pₖ:= aₖpₖ₋₁+pₖ₋₂
qₖ:= aₖpₖ₋₁ +qₖ₋₂
for k>1:

we compute the magic table
k 0 1 2 3 4 5 6 8
aₖ 2 1 1 1 4 1 1 1 4 (continued fraction)
pₖ 2 3 5 8 37 45 81 127 590 (
qₖ 1 1 2 3 14 17 31 48 223
pₖ²-7qₖ² -3 2 -3 1 -3 2 -3 1 -3

(i know that m is even, (p_3,q_3) will be a solution)

So the smallest solution is (8, 3). This agrees with Theorem 9.6.1 as the pair (8, 3) corresponds to the index k = 3 = 4 − 1. We can also observe that (127, 48) is another solution of the equation from multiplying solution we found e.g by squaring
by lemma
xₖ₊₁:= x₁xₖ + dy₁yₖ
yₖ₊₁:= x₁yₖ + y₁xₖ
64+79=127
48

or use magic table again for column 7, by periodicity

Question 58

HOW TO SOLVE PELLS EQUATION
x^2-dy^2=1 s positive integer non square

Answer 58

1) Find the continued fraction of square root of d which is periodic period m
giving us [a₀;a₁,…,a_n,….].

2) find the sequences pₖ and qₖ
which satisfy [a₀;a₁,…,aₖ]= pₖ/qₖ (convergence)

3) find one solution by saying pair

(x, y) =

{(pₘ₋₁, qₘ₋₁) , if m is even
{(p₂ₘ₋₁, q₂ₘ₋₁) , if m is odd
4) we can more solutions by
squaring
multiplying
lemma

Question 59

alternative sols to pell’s
lemma 9.6.3

Answer 59

Let d be a real number. Suppose that (x₁, y₁) is a solution of x² − dy² = 1.
For every integer k ≥ 1 define
xₖ₊₁:= x₁xₖ + dy₁yₖ
yₖ₊₁:= x₁yₖ + y₁xₖ
.
Then for all k ≥ 1, (xₖ, yₖ) is also a solution
——————————————————————–
IF WE HAVE ONE SOL WE CAN FORM MORE IN THIS WAY
multiplication in the ring
works by taking solutions in the ring and multiplying the parts give us more solutions

Question 60

always a solition trivial sol of Pell’s equation

Answer 60

there is a trivial solution of pells (+-1,0) regardless of d

always a solution
here we can see powers generate the same solution

Question 61

Suppose we write as a periodic continued fraction
√d=
________
[a₀;a₁,…,aₘ]

trying to solve equation
x²-dy²=1
Suppose (x₀,y₀) sol with x₀,y₀>0

LEFT OUT OF LECTURE NOTES

Answer 61

• because they are a solution of the equation they have to be coprime gcd(x₀,y₀)=1
• because any divisor of x cannot also be a divisor of y because if it did it would also divide 1

*factorise:
( x₀-y₀√d)(x₀+y₀√d)=1
so 0< x₀-y₀√d = 1/[(x₀+y₀√d)]

0< (x₀/y₀) - √d = 1/y₀ [(x₀+y₀√d)]
< (√d)/(y₀ [(x₀+y₀√d)]) still true as multiplying by number at least 1
=1/(y²₀[1+(x₀/y₀)√d)])

also we have √d < (x₀/y₀) from positivity
so 1 < (x₀/y₀)/ √d

thus 1/(y²₀[1+(x₀/y₀)√d)]) < 1/2y²₀

conclusion
|x₀/y₀-√d|< 1/2y²₀
this close to √d
|x₀-y₀√d|< 1/2y₀
so a good approximation to it,

(x₀/y₀) - √d| < 1/2y²₀

Question 62

Suppose we write as a periodic continued fraction
√d=
________
[a₀;a₁,…,aₘ]

trying to solve equation
x²-dy²=1
Suppose (x₀,y₀) sol with x₀,y₀>0

COMPARING TO ONE OF THE CONVERGENTS

LEFT OUT OF LECTURE NOTES

Answer 62

(we have p_k, q_k strictly incresing sequences to approximate square root of d)
Let n be s.t
qₙ≤ y₀<qₙ₊₁

Suppose
|qₙ√d-pₙ| ≤|(y₀√d)- x₀|< 1/2y₀
approximation at most this good
|√d-pₙ/qₙ| < 1/(2y₀qₙ)

so if (x₀,y₀) not equal to (pₙ,qₙ) then
1/y₀qₙ
≤|y₀pₙ-x₀qₙ|/y₀qₙ (numerator at least 1, as not 0)
= |(pₙ/qₙ)-(x₀/y₀)|
≤ |√d- (pₙ/qₙ)|+ |√d- (x₀/y₀)| (triangle inequality)
<1/(2y₀qₙ)+ 1/2y²₀

giving qₙ<y₀ contradiction therefore solution
(x₀,y₀)= (pₙ,qₙ)

(case assumption |qₙ√d-pₙ| ≤|(y₀√d)- x₀|< 1/2y₀ true because if |(y₀√d)- x₀| <|qₙ√d-pₙ| we conclude y₀ < qₙ and qₙ< y₀≤qₙ₊₁ but also |√d- x₀/y₀|< |√d- pₙ/qₙ| problem as this was the best approximation so we cant use this and thus above case)