Exercise 2.1.31 (Complete residue system)

Show that − ( m − 1 ) ∕ 2 , − ( m − 3 ) ∕ 2 , … , ( m − 3 ) ∕ 2 , ( m − 1 ) ∕ 2 is a complete residue system modulo m if m is odd, and that − ( m − 2 ) ∕ 2 , − ( m − 4 ) ∕ 2 , … , ( m − 2 ) ∕ 2 , m ∕ 2 is a complete residue system modulo m if m is even.

Answers

Proof. Let m = 2 k + 1 a positive odd number. Then

{ − ( m − 1 ) ∕ 2 , − ( m − 3 ) ∕ 2 , … , ( m − 3 ) ∕ 2 , ( m − 1 ) ∕ 2 } = { − k , − k − 1 , … , k − 1 , k } = [ [ − k , k ] ]

is a set m = 2 k + 1 consecutive positive numbers.

Moreover, if

i ≡ j ( mod 2 k + 1 ) ,  where  − k ≤ i ≤ j ≤ k ,

then m = 2 k + 1 ∣ j − i , where 0 ≤ j − i < 2 k + 1 = m : this implies i = j , so no two distinct integers among the m integers of [ [ − k , k ] ] are congruent modulo m . This proves that − ( m − 1 ) ∕ 2 , − ( m − 3 ) ∕ 2 , … , ( m − 3 ) ∕ 2 , ( m − 1 ) ∕ 2 is a complete residue system modulo m .

Now let m = 2 k a positive even integer. Then

{ − ( m − 2 ) ∕ 2 , − ( m − 4 ) ∕ 2 , … , ( m − 2 ) ∕ 2 , m ∕ 2 } = { − ( k − 1 ) , − ( k − 2 ) , … , k − 1 , k = [ [ − k + 1 , k ] ]

is a set of m = 2 k consecutive numbers, and similarly no two distinct integers among the m integers of [ [ − k + 1 , k ] ] are congruent modulo m . This proves that − ( m − 2 ) ∕ 2 , − ( m − 4 ) ∕ 2 , … , ( m − 2 ) ∕ 2 , m ∕ 2 is a complete residue system modulo m . □

User profile picture
2024-07-31 09:11
Comments