Subgroup of ℤ+

이번에는 덧셈을 law of composition으로 하는 정수 group인 ℤ⁺ 의 subgroup 들을 살펴보자. 우선 특정 정수 b의 배수로 이루어진 ℤ⁺ 의 subgroup은 아래와 같이 쓸 수 있다.

bℤ = {n ∈ ℤ | n = bk for some k ∈ ℤ}.

그러면 여기서 (놀랍게도!) ℤ⁺ 의 모든 subgroup은 위와 같은 형태가 된다는 명제가 하나 나온다.

Proposition. 모든 정수 b에 대해서 부분집합(subset) bℤ 는 ℤ⁺의 subgroup이다. 게다가 (심지어) ℤ⁺의 모든 subgroup H는 'H = bℤ for some integer b' 이렇게 쓸 수 있다!

책에서는 bℤ가 ℤ⁺의 subgroup이라는 것에 대한 증명은 생략하고 모든 subgroup이 bℤ 와 같은 형태라는 것만 증명한다.

우선 H를 ℤ⁺의 subgroup이라고 하자. law of composition이 덧셈이고, identity 엘리먼트는 0이고, 엘리먼트 a의 inverse는 −a 이므로 아래와 같은 axiom(룰) 들을 정리할 수 있다.

1. if a ∈ H and b ∈ H, then a + b ∈ H;
2. 0 ∈ H;
3. if a ∈ H, then −a ∈ H.

두 번째 axiom 에 의해서 0이 H의 유일한 엘리먼트일 경우(자명한 subgroup {0}), H = 0ℤ 이므로 해당 명제는 만족한다.

그리고 a ∈ H인 a가 음수이든 양수이든 세 번째 axiom에 의해서 −a는 H에 포함된다.

그리고 H에서 가장 작은 양의 정수를 뽑아서 H = bℤ 라고 해보자. 이것을 다르게 표현하면 양의 정수 k에 대해서 bk = b + b + ... + b (k 번 반복) 이 된다. 이를 첫 번째 axiom 과 induction을 사용하면 bk는 H의 엘리먼트임을 만족하게 된다. k가 음수인 경우는 -bk 이므로 역시 H의 엘리먼트임을 만족한다(세 번째 axiom).

마지막으로 H ⊂ bℤ 인 것을 보이자. 이 말은 H의 모든 엘리먼트 n ∈ H 가 b의 배수인 정수라는 말이다. n을 b의 배수와 나머지 형태로 수식으로 표현하면 아래와 같이 쓸 수 있다.

n = bq + r

여기서 q, r 은 정수이고 나머지(remainder)인 r은 0 ≤ r < b 의 범위를 갖는다. 그러면 n과 bq는 모두 H의 엘리먼트이다(위의 내용과 이어지니 잘 따라오자). 그리고 위 식을 r에 대하여 고쳐쓰면 r = n - bq 가 되는데 이것 역시 첫 번째 axiom과 세 번째 axiom에 의하여 H의 엘리먼트가 된다. 또한 b가 H에서 가장 작은 양의 정수라고 정했고 0 ≤ r < b 이니 r = 0 이고 n = bq ∈ bℤ 이다(끝).

한편, subgroup bℤ는 b로 나누어 떨어지는 정수들이다. 그렇다면 여기서 두 정수 a와 b를 정하고 a와 b로 생성되는 subgroup을 만들어 볼 수 있을 것이다. 책에서는 'subgroups which are generated by two integers a, b' 라고 표현한다. 즉 아래 집합은 ℤ⁺의 subgroup 이다.

aℤ + bℤ = {n ∈ ℤ | n = ar + bs for some integers r, s}

위와 같은 형태로 구성된 subgroup을 subgroup generated by a and b 라고 한다. 이런 subgroup은 두 엘리먼트를 모두 포함하는 가장 작은 규모의 subgroup 이다.

앞의 proposition을 잠시 떠올려보면(bℤ 형태의 subgroup) aℤ + bℤ 이것도 어떤 정수 d 에 의해서 dℤ 로 표현될 수 있다(ℤ⁺의 subgroup이기 때문에). 즉 d 로 나뉘어 떨어지는 정수들의 집합인 것이다. 여기서 d는 'greatest common divisor of a and b'라고 불린다. 이어서 아래 proposition을 살펴보자.

Proposition. a, b를 0이 아닌 정수라고 하자. 그리고 d는 subgroup aℤ + bℤ 를 generate하는 양의 정수라고 하자. 그러면,

1. d can be written in the form d = ar + bs for some integers r and s.
2. d divides a and b
3. If an integer e divides a and b, it also divides d

위 proposition을 증명해보자. 우선 첫 번째 assertion은 d가 subgroup aℤ + bℤ 의 generator 라고 한 사실을 다시 적은 것일 뿐이다. 두 번째는 dℤ = aℤ + bℤ 이기 때문에 d 가 a와 b를 나눌 수 있다. 마지막으로 e가 a와 b를 나눌 수 있다면 a와 b는 eℤ 의 형태가 된다. 이 말은 어떤 정수 n = ar + bs 가 eℤ 에 포함된다는 이야기이고, d역시 이러한 형태이기 때문에 e가 d를 나눌 수 있게된다(끝).