Exercise 4.16

Calculate the solutions to x 3 ≡ 1 ( mod 19 ) and x 4 ≡ 1 ( mod 17 ) .

Answers

Proof. Here we note a the class of x in ℤ ∕ pℤ .

Let a ∈ 𝔽 19 . Then

a 3 − 1 = 0 ⟺ a − 1 = 0  or  a 2 + a + 1 = 0 .

a 2 + a + 1 = 0 ⟺ ( a + 10 ) − 99 = 0 ⟺ ( a + 10 ) 2 − 4 = 0 ⟺ ( a + 8 ) ( a + 12 ) = 0

So, for all x ∈ ℤ ,

x 3 ≡ 1 ( mod 19 ) ⟺ x ≡ 1 , 7 , 11 ( mod 19 ) .

Let a ∈ 𝔽 17 .

a 4 = 1 ⟺ a 2 = 1 or a 2 = − 1 = 4 2 ⟺ a = ± 1 or a = ± 4

So, for all x ∈ ℤ ,

x 4 ≡ 1 ( mod 17 ) ⟺ x ≡ − 1 , 1 , − 4 , 4 ( mod 17 ) .

Alternatively, we can take primitives roots modulo 19 and 17.

2 is a primitive root modulo 19 , Let a = 2 k ∈ 𝔽 19 .

a 3 = 1 ⟺ 2 3 k = 1 ⟺ 18 ∣ 3 k ⟺ 6 ∣ k ⟺ a = 1 , 2 6 = 7 , 2 12 = 11

3 is a primitive root modulo 17. Let a = 3 k ∈ 𝔽 17 .

a 4 = 1 ⟺ 3 4 k = 1 ⟺ 16 ∣ 4 k ⟺ 4 ∣ k ⟺ a = 1 , 3 4 = − 4 , 3 8 = − 1 , 3 12 = 4 □
User profile picture
2022-07-19 00:00
Comments