Proof using well ordering principle

Question

Assume that the set $I \subseteq\mathbb{Z}$ satisfies the following properties:

a.) There exists $n \in I$ such that $n \neq 0$

b.) If $m,n \in I$ , then $m+n \in I$

c.) If $m \in I$ and $a \in \mathbb{Z}$, then $am \in I$

This was a hint that was given: Let $J = (m \in I : m >0)$

Prove that there exists $n_0 \in \mathbb{Z}$, such that $I = (kn_0 | k \in \mathbb{Z})$

Seeing as this is from the section of number theory, specifically division algorithm and well ordering principle, I would imagine those are what I am expected to use.

Intuitively I believe this could be proven by contradiction, but I have no clue how to start and what to do.

Can someone help?

Answer 1

I'm going to guess you've been asked to prove that $I$ is the set of all multiples of $k$ for some $0 \lt k \in \Bbb Z$.

First, assumption a tells us that for some $n \neq 0, n \in I$. Note that either $n \gt 0$ or $-n \gt 0$ and if $n \in I$, then assumption c tells us also $-n = -1 \cdot n \in I$, so now we know $\exists n \gt 0$ with $n \in I$.

Let $k$ be the least positive element of $I$. Such an element has to exist because the positive integers are well ordered and we've just demonstrated that the set of positive elements of $I$ is non-empty. Claim: $I = \{km~|~m \in \Bbb Z\},$ which we'll denote by $k \Bbb Z.$ We'll prove this by showing $k \Bbb Z \subseteq I$ and $I \subseteq k \Bbb Z$.

Assumption c tells us that $k \Bbb Z \subseteq I$ because we know that $k \in I$ so assumption c tells us any multiple of $k$ is in $I$.

Choose $n \in I$ and assume $n \gt 0$. We want to prove $n \in k \Bbb Z$. For some $q, r \in \Bbb Z, n = qk+r$ with $0 \leq r \lt k$ -- that's the Euclidean division algorithm. (If you haven't already proved this fact, it can also be proved in a similar manner to the proof below.) We know that $qk \in I$, so $-qk \in I$ and assumption b tells us $n-qk=r \in I$. But $k$ was the smallest positive element of $I$, so that $0 \leq r \lt k$ and $r \in I$ forces $r=0$, which in turn means $n=qk \in k \Bbb Z$. If $n \lt 0$ and $n \in I$, perform the same analysis on $-n$. Thus, we conclude $I \subseteq k \Bbb Z$, completing the proof.

Answer 2

Are you familiar with Bezout's Lemma?

If $m,n \in I\subset \mathbb Z$ there are $a,b \in \mathbb Z$ so that $am + bn =\gcd(m,n)$. Now c; says that $am, bn \in I$ and b; says that $am + bn = \gcd(m,n) \in I$.

Now take the hint: $J \subset \mathbb N$ and $J$ is not empty (because an $n \ne 0$ is in $I$ and $(-1)n \in I$ so $\pm n \in I$ and one of $n, -n$ must be positive.) So $J$ has a least element, $n_0$.

If we take any other element $n \in I$ then $\gcd(n_0, n)\in I$. But... $0 < \gcd(n_0, n) \le n_0$. But $n_0$ is the least positive value so $\gcd(n_0, n) < n_0$ is impossible. So $\gcd(n_0, n) = n_0$. So all $n\in I$ are multiples of $n_0$ and $I\subset \{kn_0|k\in \mathbb Z\}$.

And by c; $\{kn_0|k\in \mathbb Z\} \subset I$.

So $\{kn_0|k\in \mathbb Z\}=I$.