AA The Integer #1

Well-ordering principle

Well-ordering principle: Any nonempty set of nonnegative integers has the smallest member.

조건1. 공집합이면 안된다.
조건2. 음수가 없는 정수 집합이어야 한다.
결과1. 가장 작은 원소가 존재한다.

nonnegative set이라는 조건2는 lower bound를 주기 위해서 존재하는 것 같다. lower bound가 없다면 가장 작은 원소가 없다.

Thm 1.5.1 Eucild’s Algorithm

If \(m\) and and \(n\) are integers with \(n>0\), then there exist integers \(q\) and \(r\), with \(0\leq r<n\), such that \(m=qn+r\)

결과를 보면 나누기 연산이라는 것을 알 수 있다. \(n(n>0)\)이 나누는 수, \(q\) 가 몫, \(r(0\leq r<n)\)이 나머지와 같은 역할을 한다.

proof

Let \(W\) be the set of \(m-tn\) for any integers \(t\). i.e. \( W=\{m-tn|t\in\mathbb{Z}\} \). \(W\) has both negative and nonnegative integers. Especially, when \(t\) is negative and absolute value is large enough, then \(m-tn>0\). Let \(V\) be the subset of \(W\) with all of nonnegative elements of \(W\). i.e \(V=\{v\in W|v\geq0\}\). Since \(V\) is nonempty set of nonnegative elements, \(V\) has the smallest elements \(r\) by well-ordering principle.

Since \(r\) is an element of \(V\), \(r\geq 0\). Also, \(r<n\). If not, \(r\geq n\). \(r\) is an element of \(W\) so, there is an integer \(q\) such that \(r=m-qn\geq n\), \(m-(q+1)n\geq 0\). It means there exists smaller element than \(r\) in \(V\). Contradiction

There exists \(r=m-qn\) satisfying \(0\leq r<n\) for some integer \(q\). Therefore, Euclid’s Algorithm is proved.

Division

Def
Given integers \(m\neq 0\) and \(n\) we say that \(m\) divides \(n\), writen as \(m|n\), if \(n=cm\) fpr some integer \(c\).

위에서 정수의 나누기에 대해서 정리를 해보았으니 \(r\)이 \(0\)인 상황에 대해서 정의해본다.
\(n|m\)라고 정의할 때 왼쪽이 나누는 수, 오른쪽이 나눠지는 수이다.

왼쪽: 나누는 수
오른쪽: 나뉘지는 수

나누는 수가 \(0\)이면 안 되지만 음수는 가능하다.

properties

\(1|n\) for all \(n\).
If \(m\neq 0\), then \(m|0\)
If \(m|n\) and \(n|q\), then \(m|q\).
If \(m|n\) and \(m|q\), then \(m|(un+vm)\) for all \(u\), \(v\).
If \(m|1\), then \(m=1\) or \(m=-1\)
If \(m|n\) and \(n|m\), then \(m=\pm 1\)

0hoo