Chapter 8

Question 1

Theorem. Analogue of FlT for ℤ[i]

Answer 1

Let p be a prime and α∈ℤ[i]

αᵖ = {α modp if p≡1mod4, α* modp if p≡3mod4

Question 2

Lemma (α + β)ᵖ ≡ αᵖ + βᵖ modp

Answer 2

Let R be a ring, p a prime number and α,β∈R. Then

(α + β)ᵖ ≡ αᵖ + βᵖ modp

Question 3

idea of proof for (α + β)ᵖ ≡ αᵖ + βᵖ modp

Answer 3

1. use binomial theorem on (α + β)ᵖ

2. if 1 ≤ k < p then p chose k is an integer that is congruent to 0 modulo p.

Question 4

idea for proof of analogue of FlT in ℤ[i]

αᵖ = {α modp if p≡1mod4, α* modp if p≡3mod4

Answer 4

1. write α=a+bi
2. apply lemma to get αᵖ≡aᵖ+(bi)ᵖmodp
3. apply FlT in the integers to get αᵖ≡a+biᵖmodp
4. we claim that iᵖ= {i if p≡1mod4, -i if p≡3mod4
5. if p≡1mod4, p = 1 + 4k so iᵖ = i*i⁴ᵏ = i
   (similar for p≡3mod4)

Question 5

Theorem. Analogue of FlT for ℤ[√3]

Answer 5

Let p>3 be a prime and α∈ℤ[√3]

αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12

Question 6

idea of proof for Analogue of FlT for ℤ[√3]

αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12

Answer 6

1. write α=a+b√3
2. apply lemma to get αᵖ≡aᵖ+(b√3)ᵖmodp
3. apply FlT in the integers to get αᵖ≡a+b√3ᵖmodp ≡ a+b√3√3ᵖ⁻¹modp ≡ a+b√3(3/p)modp
4. use GLQR we get
   αᵖ = {α modp if p≡±1mod12, α* modp if p≡±5mod12

Question 7

Mersenne Number

Answer 7

Let n∈ℕ, the nth Mersenne number is Mₙ=2ⁿ-1

Question 8

Mersenne Prime

Answer 8

A Mersenne number Mₙ=2ⁿ-1 which is prime

Question 9

Lemma. If Mₙ is prime…

Answer 9

Let n∈ℕ. if Mₙ is prime then n is prime

Question 10

Proof of lemma if Mₙ is prime then n is prime

Answer 10

contradiction. Suppose n=ab. Then 2ⁿ-1 = 2ᵃᵇ-1 which we can factorise which contradicts the hypothesis that Mₙ is prime.

Question 11

The Lucas test

Answer 11

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

Question 12

μ =

Answer 12

μ = 1 + √3

Question 13

𝜏 =

Answer 13

𝜏 = 2 + √3

Question 14

𝜏𝜏* =

Answer 14

1

Question 15

2𝜏 =

Answer 15

μ²

Question 16

Lemma. rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ

Answer 16

Let {rᵢ} be as in the lucas test. Then for each i≥ 0 rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ

Question 17

idea for proof of rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ

Answer 17

1. for i define sᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ
2. find s₀ and show the same as r₀
3. find sᵢ²-2 and show its equal to sᵢ₊₁

Question 18

Lemma. Mₙ≡-5mod12.

Answer 18

Let n≥3 be prime. Then Mₙ≡-5mod12.

Question 19

idea for proof of Mₙ≡-5mod12.

Answer 19

1. Mₙ≡4mod4
2. Mₙ ≡ (-1)ⁿ -1mod3 ≡ 1mod3
3. choose a CSR mod 12 and show Mₙ≡-5mod12

Question 20

Idea for proof of 1st half of lucas test. Let n≥3 be prime and suppose Mₙ is prime. Then rₙ₋₂≡0modn

Answer 20

1. apply FlT. Since p=Mₙ≡-5mod12
   μᵖ≡μmod p
   2.multiply through by μ. (μμ=-2)
2. since p+1 is even factorise to replace μ² by 2𝜏. (μ²)¹/²⁽ᵖ⁺¹⁾≡-2 mod p
3. expand out. Then cancel by 2.
4. apply euler criterion. Since p=Mₙ=2ⁿ-1 then p≡-1mod8. => 2¹/²⁽ᵖ⁺¹⁾≡1 => 𝜏¹/²⁽ᵖ⁺¹⁾≡-1modp.
5. take conjugates add this to original then apply rᵢ = 𝜏²^ᶦ + 𝜏*²^ᶦ formula.
6. by defining relation for rᵢ we get the result

Question 21

if rₙ₋₂/≡0modn then

Answer 21

Mₙ is not prime

Question 22

Lemma. Cancelling by 2 in ℤ[√3]

Answer 22

Let p be an odd prime, α,β∈ℤ[√3]. suppose that
2α≡2β mod p
Then, α≡βmodp

Question 23

Lemma. taking conjugates in ℤ[√3]

Answer 23

Let p be an odd prime, α,β∈ℤ[√3]. suppose that
α ≡ β mod p
Then, α* ≡ β* mod p

Question 24

order (in an arbitrary ring)

Answer 24

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.

Question 25

Lemma. order in arbitrary rings (same as in ℤ)

Answer 25

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

Question 26

proof of second half of lucas test

Answer 26

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

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

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

4. deduce that Mₙ = q => Mₙ is prime