CH9 Some other rings of integers Flashcards

1
Q

Definition 9.1.1
Z[√d]

A

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[ı].)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Z[√d] aside

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition 9.1.2
norm on Z[√d]

A

norm on Z[√d]

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

norm on Z[√d]

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

when d<0

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

property:
norm on Z[√d]

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

remark in Z[√d]

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Theorem 9.1.3
using division algorithm Z[√d]

When can we use it?

A

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(β)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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(β)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

remark 9.1.4.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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]

A

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β) = γ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Theorem 9.1.6

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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. □

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

prime means irreducible?

A

yes
IFF

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

irreducible means prime?

A

yes
IFF

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

When can we use FTOA

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

in Z√−3 can we find division algortithm?

is element 2 prime or irreducible?

A

(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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

thm 9.2.1

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

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

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:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q


Example 9.2.2
using the thm to write 113

Is 113 prime in Z[root -2]

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Theorem 9.2.3
missed?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Eisenstein integers

(ring of)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

ring of eisenstein integers
norm defined

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Lemma 9.3.2 (Units of Eisenstein integers)
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).
26
Theorem 9.3.3 (Division algorithm for Eisenstein integers)
Let α, β ∈ Z[ω] with β ̸= 0. Then there are q,r ∈ Z[ω] (the “quotient and remainder”) such that α = qβ + r and 0 ≤ N(r) < N(β).
27
Theorem 9.3.4 (Euler, 1770)
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
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(β).
29
Theorem 9.3.4 (Euler, 1770)
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
30
defn 9.4.1 Pell's eq
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
31
We know units of Z[√d] are numbers of the form a +b√d with
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.
32
Example 9.4.2. Consider Pell’s equation for d = 2
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.
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.
Skipped...
34
DEF 9.5.1 A continued fraction
**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
35
a continued fraction is **simple** if
a continued fraction is **simple** if a₀,...,aₙ are all integers
36
**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
37
notation of continued fraction
[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ₙ]
38
Lemma 9.5.2 division algorithm
Given m, n ∈ Z with n > 0, denote the corresponding division algorithm m=r₀=q₂r₁ +r₂ where 0 r₂
39
proof of division algorithm with continued fractions
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
40
every rational number can be written as a finite continuous fraction
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
41
Corollary 9.5.3. When is x rational
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
42
Example 9.5.4. We will show how to write 289/119 as a finite continued fraction.
skipped? perform Euclids division algorithm 289=2*119 +51 119=2*51+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 .
43
pi as a continued fraction
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
44
benefits of continued fractions
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....
45
def 9.5.6 periodic continued fractions
**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
46
example periodic continued fraction with all coefficients equal to 1
α = [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
47
quadratic equation from a periodic continued fraction
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
48
Irrational numbers can always be written uniquely as an infinite simple continued fraction.
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.
49
definition 9.5.9 kth convergent
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
50
Proposition 9.5.10. Given an infinite continued fraction (not necessarily simple)
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
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
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ₖ₊₁
52
So if we are writing a number alpha as an infinite continued fraction how good are our approximations?
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?
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?
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
54
Theorem 9.5.11 √d
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)
55
Example 9.5.12. We will now find the continued fraction for √7
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
56
Theorem 9.6.1 HOW TO SOLVE PELLS EQUATION
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
57
Example 9.6.2. Let us find integer solutions to x² − 7y²2 = 1. d=7
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
58
HOW TO SOLVE PELLS EQUATION x^2-dy^2=1 s positive integer non square
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
59
alternative sols to pell's lemma 9.6.3
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
60
always a solition trivial sol of Pell's equation
there is a trivial solution of pells (+-1,0) regardless of d always a solution here we can see powers generate the same solution
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
* 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²₀
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
(we have p_k, q_k strictly incresing sequences to approximate square root of d) Let n be s.t qₙ≤ y₀