Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 3.3.21* (Subgroup of elements satisfying $a^{(m-1)/2} = \genfrac{(}{)}{}{}{a}{m}$)

An Introduction to the Theory of Numbers

Exercise 3.3.21* (Subgroup of elements satisfying $a^{(m-1)/2} = \genfrac{(}{)}{}{}{a}{m}$)

Let m be a positive odd integer, and let 𝒢 denote the set of those reduced residue classes a ( mod m ) such that a ( m − 1 ) ∕ 2 ≡ ( a m ) ( mod m ) . Show that if a ∈ 𝒢 and b ∈ 𝒢 , then ab ∈ 𝒢 . Show also that if a ∈ 𝒢 and a a ¯ ≡ 1 ( mod m ) , then a ¯ ∈ 𝒢 . (Thus 𝒢 is a subgroup of the multiplicative group of reduced residue classes ( mod m ) .)

Answers

Since a ∈ ℤ ∕ mℤ is a class, we write a a − 1 = 1 rather than a a ¯ ≡ 1 ( mod m ) , and a ( m − 1 ) ∕ 2 = ( a m ) ¯ the class of ( a m ) in ℤ ∕ mℤ . With a slight abuse of language, we write 0 , 1 , − 1 for the classes of 0 , 1 , − 1 , and ( a m ) for the class of ( a m ) in ℤ ∕ mℤ .

Proof. Here ( ℤ ∕ mℤ ) × is the multiplicative group of invertible elements of ℤ ∕ mℤ , with order ϕ ( m ) . Put

𝒢 = { a ∈ ( ℤ ∕ mℤ ) × ∣ a ( m − 1 ) ∕ 2 = ( a m ) } .

We want to prove that 𝒢 is a subgroup of ( ℤ ∕ mℤ ) × .

(i)
Since 1 ( m − 1 ) ∕ 2 = 1 = ( 1 m ) , 1 ∈ 𝒢 , so 𝒢 ≠ ∅ .
(ii)
If a ∈ 𝒢 and b ∈ 𝒢 , then a ( m − 1 ) ∕ 2 = ( a m ) , b ( m − 1 ) ∕ 2 = ( b m ) .

Therefore

( ab ) ( m − 1 ) ∕ 2 = a ( m − 1 ) ∕ 2 b ( m − 1 ) ∕ 2 = ( a m ) ( b m ) = ( ab m ) .

Thus ab ∈ 𝒢 .

(iii)
If a ∈ 𝒢 , write a − 1 the inverse of a in the group ( ℤ ∕ mℤ ) × . Since a ϕ ( m ) = 1 by Euler’s Theorem, 1 = a ⋅ a − 1 = a ⋅ a ϕ ( m ) − 1 , thus a − 1 = a ϕ ( m ) − 1 .

We know that 1 = a 0 ∈ 𝒢 . Moreover, if a k ∈ 𝒢 for some k ≥ 0 , then a k + 1 = a ⋅ a k ∈ 𝒢 by part (ii). We have proved by induction that a k ∈ 𝒢 for all integer k ≥ 0 . In particular, for k = ϕ ( m ) − 1 , we obtain a ϕ ( m ) − 1 ∈ 𝒢 , so

a − 1 ∈ 𝒢 .

This shows that 𝒢 is a subgroup of ( ℤ ∕ mℤ ) × . □

User profile picture
2024-11-08 11:37
Comments