Chapter 6 Flashcards
Wallis’ equation method (where you can factorise x,y and n has only a few factors)
- factorise the x,y expression via difference of two squares
- take cases for each of the factors of n
- solve simultaneous equations for each set of factors with the factorisation (since the powers of x,y are even it suffices to find the non -ve soltuions then the others are found by multiplying through by -1)
Lemma. no integer solutions to equation.
Let f(X₁,…,Xᵣ) be a polynomial with integer coefficients. Suppose that there is a n∈ℕ s.t. f(X₁,…,Xᵣ)≡0modn has no solutions. Then there are no integer solutions to f(X₁,…,Xᵣ)=0
How to prove there are no integer solutions to any equation
- define f(X₁,…,Xᵣ) and p ( is coefficient of X)
- suppose there is a solution for a contradication. then Xᵏ≡cmodn
- since k is even the legendre symbol (Xᵏ/p)-1 => (c/p)=1
- by GLQR find another value for (c/p)
- not equal => contradiction
Lemma. in a UFD irreducible => prime.
Let a,b and p be non-zero elements of R with p irreducible. Suppose that p|ab then p|a and p|b. i.e. p is prime.
idea for proving that in a UFD irreducible => prime
- suppose p|ab then ab=pc for some c
- find a factorisation into irreducibles by multiplying p by a factorisationof c
- a second factorisation of ab is obtained by multiplying a factorisation of a by a factorisation of b
- since R is a UFD and p appears in the 2st factorisation then an associate of p appears in the 2nd factorisation so p|a or p|b
coprime
Two elements of R are coprime if their only common factors are units.
Theorem. a and b associate to kth powers.
Let a,b,c∈R{0} and k∈ℕ. Suppose that ab is associate to cᵏ and that a and b are coprime. then a and b are associate to kth powers of elements of R.
idea for proving that a and b associate to kth powers.
- factorise ab into irreducibles by a factorisation of a x factorisation of b
- factorise ab into irreducibles by a factorisation of c k times (times by a unit)
- since UFD 1. and 2. are essentially the same.
- let p be an irreducible that appears in 1. then an associate appears in 2. k times (multiple of k). so this p must appear a multiple of k times in 1.
- now a,b are coprime so p can only appear in a factorisation of a (not b). So a is associate to a kth power of p.
How to find the integer solutions to an equation of the form yˡ =xᵏ+n when l is odd and k is even
- factorise xᵏ+n to determine what ring to work in
- determine if the ring is a UFD, what its units are and what the norm is in this ring
- show y is odd. work mod4/mod8 for each yˡ and xᵏ+n to show that y≡1mod4
- show that the factors are coprime. let d be a common factor then d is a factor of the difference, take norms. also d|yˡ, take norms. note y is odd.
- apply theorem so that factor = uαˡ
- find a way to absorb the units or replace uαˡ with βˡ
- chose integers a,b to define α set this equal to the factor.
- expand using binomial method.
- equate real and imaginary parts. factorise fully.
- use the fact that a,b are integers to take cases for each possible value of b.
lemma. make two elements coprime.
Let α,β be non-zero members of a ring R and suppose that δ is a HCF of α,β. Then,
α/δ,β/δ are coprime.
idea of proof for making two elements of a ring coprime.
Let α,β be non-zero members of a ring R and suppose that δ is a HCF of α,β. Then,
α/δ,β/δ are coprime.
- let γ be a common factor of α,β. We must show gamma is a unit.
- γ|α/δ and γ|β/δ so α/δ=aγ β/δ=bγ
- rearranging we get that γδ is a common factor of alpha and beta
- since delta is a HCF this forces γδ|δ
- so δ = γδε => 1 = γε so gamma is a unit
ordₚ(a)
Let a∈R{0} and let p∈R be irreducible. Define, ordₚ(a) to be the number of associates of p that occur in a factorisation of a into irreducibles.
if a’ is associate to a and p’ is associate to p then ords…
ordₚ’(a’) = ordₚ(a)
ordₚ(ab) =
ordₚ(a)+ordₚ(b)
if δ|α then ordₚ(α/δ) =
ordₚ(α) - ordₚ(δ)
Lemma. factors and ords.
Let α,β be non-zero elements of a ring, Then α|β iff ordₚα ≤ ordₚβ for every irreducible p in R
Lemma. HCF and ord.
Let α,β be non-zero elements of a ring, let δ be a HCF of α and β. Then ordₚδ = min(ordₚα, ordₚβ) for every irreducible r in R
Lemma. factors of an irreducible to a power.
Suppose that π∈R is irreducible and that n is a natural number. Then the factors of πⁿ are the associates of πᵏ for 0≤k≤n
How to solve a Diophantine equations when the factors are not coprime y³=x²+n
- factorise the lower power and constant part. Work in the ring implied by this factorisation.
- let δ be the highest common factor of these factors
- divide the equation through by δ. now the factors are coprime.
- δ| difference of factors (find explicit value)
- Let π be an irreducible. Where πᵉˣᵖˡᶦᶜᶦᵗ ᵛᵃˡᵘᵉ is associate to the explicit value.
- Consequently, δ is associate to πᵗ for some t, 0≤t≤4. Since associates of HCFs are HCFs we may replace δ with πᵗ
- Now get more information about t using the ord function to show 3|t
- Now we have the LHS is a cube but still need to show the value being cubed is an element of the ring.
Apply the theorem to get the factor/ delta = uα³ - absorb the unit
- chose α=a+bi and equate real and imaginary parts.
- take cases for each value
Method of descent
To show f has no non-trivial integer solutions we need
1. a formula for measuring the size of a solution
2. a machine which when given a solution produces another smaller solution
The machine produces infinitely many solutions which is a contradiction since only a finite number of non-negative integers less than a.
How to prove an equation has no non-trivial integer solutions by the method of descent (hard example)
(since all exponents are even only consider positive solutions)
- Divide through by a highest common factor to get that x and y are coprime.
- Suppose (x,y,z) is a solution. Swap x,y if neccessary suppose x is odd.
- Then find integers a and b that represent x²,y²,z by theorem
- apply theorem again to equation in correct form to get integers u,v to replace a,b.
- Manipulate to get a solution smaller than the previous solution (machine).
- find a formula
How to prove an equation has no non-trivial integer solutions by the method of descent (easier example)
- suppose (x,y,z) is a solution
- check the coefficiants. Show that there is a common factor of all of them.
- divide through by the common factor to get a smaller solution. (machine)
- define the formula.
Mod in any ring
Let R be a ring and n̸=0, α,β∈R define α≡βmodn to mean n|(α-β) in R.
if n|α <=>
α≡0modn
CSR
Let R be a ring and 0 ̸= n ∈ R. A complete set of residues mod n in R is a set S of elements of R such that each member of R is congruent modulo n to exactly one member of S