CH9 Some other rings of integers Flashcards
Definition 9.1.1
Z[√d]
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[ı].)
Z[√d] aside
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).
Definition 9.1.2
norm on Z[√d]
norm on Z[√d]
N(a + b√d):= |a² − db²|
norm on Z[√d]
N(a + b√d):= |a² − db²|
when d<0
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
property:
norm on Z[√d]
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.
remark in Z[√d]
Any prime element in Z[√d]
is irreducible, but in general irreducible elements need
not be prime
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(β)
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(β)
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
remark 9.1.4.
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
Theorem 9.1.5 (Bézout’s lemma: a more general version)
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]
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]
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β) = γ.
Theorem 9.1.6
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.
Let d be one of −1, ±2, 3. For every α ∈ Z[√d]
, α is irreducible if and only if α is
prime.
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. □
prime means irreducible?
yes
IFF
irreducible means prime?
yes
IFF
.
Theorem 9.1.8 (Fundamental theorem of Arithmetic: a more general version)
When can we use FTOA
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)
in Z√−3 can we find division algortithm?
is element 2 prime or irreducible?
(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
thm 9.2.1
is: which numbers can be written in the form
x^2 +2y^2
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)
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
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:
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:
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
□
Example 9.2.2
using the thm to write 113
Is 113 prime in Z[root -2]
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
Theorem 9.2.3
missed?
The only integer solutions of x^2 + 2 = y^3 are x = ±5, y = 3.
Eisenstein integers
(ring of)
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.
ring of eisenstein integers
norm defined
We define the norm on Z[ω] by
N(a + bω) := a² − ab + b² = |a + bω|²
= (a + bω)(a + bω²).
Again N(αβ) = N(α) N(β).
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).
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(β).
Theorem 9.3.4 (Euler, 1770)
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(β).
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
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
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.
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.
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…
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
a continued fraction is simple if
a continued fraction is simple if a₀,…,aₙ are all integers
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
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ₙ]
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₂<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ₖ₊₁]
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
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
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
Example 9.5.4. We will show how to write 289/119 as a finite continued fraction.
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 .
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
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….
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
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
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
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.
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
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
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ₖ₊₁
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?
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
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)
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
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
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
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
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
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
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²₀
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₀<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)
