Chapter 8 Flashcards
Theorem. Analogue of FlT for ℤ[i]
Let p be a prime and α∈ℤ[i]
αᵖ = {α modp if p≡1mod4, α* modp if p≡3mod4
Lemma (α + β)ᵖ ≡ αᵖ + βᵖ modp
Let R be a ring, p a prime number and α,β∈R. Then
(α + β)ᵖ ≡ αᵖ + βᵖ modp
idea of proof for (α + β)ᵖ ≡ αᵖ + βᵖ modp
- use binomial theorem on (α + β)ᵖ
2. if 1 ≤ k < p then p chose k is an integer that is congruent to 0 modulo p.
idea for proof of analogue of FlT in ℤ[i]
αᵖ = {α modp if p≡1mod4, α* modp if p≡3mod4
- write α=a+bi
- apply lemma to get αᵖ≡aᵖ+(bi)ᵖmodp
- apply FlT in the integers to get αᵖ≡a+biᵖmodp
- we claim that iᵖ= {i if p≡1mod4, -i if p≡3mod4
- if p≡1mod4, p = 1 + 4k so iᵖ = i*i⁴ᵏ = i
(similar for p≡3mod4)
Theorem. Analogue of FlT for ℤ[√3]
Let p>3 be a prime and α∈ℤ[√3]
αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12
idea of proof for Analogue of FlT for ℤ[√3]
αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12
- write α=a+b√3
- apply lemma to get αᵖ≡aᵖ+(b√3)ᵖmodp
- apply FlT in the integers to get αᵖ≡a+b√3ᵖmodp ≡ a+b√3√3ᵖ⁻¹modp ≡ a+b√3(3/p)modp
- use GLQR we get
αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12
Mersenne Number
Let n∈ℕ, the nth Mersenne number is Mₙ=2ⁿ-1
Mersenne Prime
A Mersenne number Mₙ=2ⁿ-1 which is prime
Lemma. If Mₙ is prime…
Let n∈ℕ. if Mₙ is prime then n is prime
Proof of lemma if Mₙ is prime then n is prime
contradiction. Suppose n=ab. Then 2ⁿ-1 = 2ᵃᵇ-1 which we can factorise which contradicts the hypothesis that Mₙ is prime.
The Lucas test
Define a sequence of numbers r₀, r₁, . . . bᵧ
r₀=4 rᵢ₊₁ = rᵢ²-2
Let n be a prime, n ≥ 3. Then Mₙ is prime if an only if rₙ₋₂≡0modn
μ =
μ = 1 + √3
𝜏 =
𝜏 = 2 + √3
𝜏𝜏* =
1
2𝜏 =
μ²
Lemma. rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ
Let {rᵢ} be as in the lucas test. Then for each i≥ 0 rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ
idea for proof of rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ
- for i define sᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ
- find s₀ and show the same as r₀
- find sᵢ²-2 and show its equal to sᵢ₊₁
Lemma. Mₙ≡-5mod12.
Let n≥3 be prime. Then Mₙ≡-5mod12.
idea for proof of Mₙ≡-5mod12.
- Mₙ≡4mod4
- Mₙ ≡ (-1)ⁿ -1mod3 ≡ 1mod3
- choose a CSR mod 12 and show Mₙ≡-5mod12
Idea for proof of 1st half of lucas test. Let n≥3 be prime and suppose Mₙ is prime. Then rₙ₋₂≡0modn
- apply FlT. Since p=Mₙ≡-5mod12
μᵖ≡μmod p
2.multiply through by μ. (μμ=-2) - since p+1 is even factorise to replace μ² by 2𝜏. (μ²)¹/²⁽ᵖ⁺¹⁾≡-2 mod p
- expand out. Then cancel by 2.
- apply euler criterion. Since p=Mₙ=2ⁿ-1 then p≡-1mod8. => 2¹/²⁽ᵖ⁺¹⁾≡1 => 𝜏¹/²⁽ᵖ⁺¹⁾≡-1modp.
- take conjugates add this to original then apply rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ formula.
- by defining relation for rᵢ we get the result
if rₙ₋₂/≡0modn then
Mₙ is not prime
Lemma. Cancelling by 2 in ℤ[√3]
Let p be an odd prime, α,β∈ℤ[√3]. suppose that
2α≡2β mod p
Then, α≡βmodp
Lemma. taking conjugates in ℤ[√3]
Let p be an odd prime, α,β∈ℤ[√3]. suppose that
α ≡ β mod p
Then, α* ≡ β* mod p
order (in an arbitrary ring)
Let R be a ring, n∈{0} and a∈R. The order of a modulo n in R is the smallest natural number d s.t. aᵈ≡1modn. if such d exists. if not a does not have an order modulo n.
Lemma. order in arbitrary rings (same as in ℤ)
Let R be a ring, q∈R and a∈R. Assume that a has order d modulo n. Let k∈ℕ. Then
aᵏ≡1modq
if and only if d|k
proof of second half of lucas test
- choose a suitable factor q of Mₙ s.t. q≡±5mod12
(Mₙ is odd and not a factor of 3 look at CSR. Also Mₙ≡±5mod12.)
- work out the order of 𝜏 mod q.
(rₙ₋₂≡0modn, use rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ equation, multiple by 𝜏 to get rid of conjugate, square this. Then let d be the order of 𝜏 mod q => d|2ⁿ so d=2ᵐ for some m≤n. n-1=m+k. Then 𝜏^Mₙ≡1modq )
- use FlT in ℤ[√3] to obtain further information about the order
(𝜏ᑫ≡𝜏*modq , multiply by 𝜏. Then by the lemma and step 2 q≥Mₙ. Also, q|Mₙ so q≤Mₙ so q=Mₙ)
- deduce that Mₙ = q => Mₙ is prime
