Proofs of divisibility

Question

I have the following question for homework.

Fix positive integers $a$ and $b$ . Here’s an inductive definition of a set $S$ :

Foundation rule: $a,b ∈ S$.

Constructor rule: If $m,n ∈ S$ , then $m − n ∈ S$.

(a) Suppose $h$ is a common factor of $a$ and $b$ . Use the exclusion rule to prove that for every $n ∈ S$ , $h$ divides $n$ .

(b) Suppose $k ∈ S$ is a positive integer which is not a factor of $a$ . Prove that there is some $l ∈ S $ such that $0 < l < k$ . (Hint: Consider the sequence $a,a − k,a − 2 k,...$ and use the fact that $\mathbb{N}$ is well-ordered.)

(c) In the same way that you proved (b), we may also prove the following fact: if $k ∈ S$ is a positive integer which is not a factor of $b$ , then there is some $l ∈ S$ such that $0 < l < k$ . Use (b) and the above fact to prove that there is some positive integer in $S$ which is a common factor of $a$ and $b$ . (Hint: Use the fact that $\mathbb{N}$ is well-ordered.)

(d) Use (a) and (c) to conclude that S contains gcd($a,b$).

I'm unsure about how to even start (a) and (b).

For (a) I thought something along the lines of "because $h$ is a common factor of $a$ and $b$, as $n ∈ S$, $h$ must be a divisor of $n$" yet apparently this is quite far off what we are supposed to do.

I have literally no idea how to even start (b).

Any help would be appreciated.

Answer 1

(a)
Bass case. As h divides a and b, show h divides a - b.
Induction step. If h divides r,s, show h divides r - s.

There's such a thing as the exclusion rule?

Answer 2

Some greetings

Hello @zhl44304, welcome to MSE. Concerning your problem, I think you should first read about Ideal and Ring theory.

My proof of a direct result down here will help you solve all four questions in one note.

Restate the question

Let there be a set $\mathbb{I}$ with 2 foundation numbers $a$ and $b$, and if $x$ and $y$ $\in \mathbb{I}$ then $x+y \in \mathbb{I}$

We now prove that $\mathbb{I} = k\mathbb{Z}$, which is all the integers that is divisible by $k$, for some $k \in \mathbb{Z}$

Prove the properties

• If $\mathbb{I} = \left\{ 0 \right\}$, then $k=0$
• If $\mathbb{I} \neq \left\{ 0 \right\}$, then $k=0$

Consider the set $\mathbb{I^*}$ that consists of positive numbers.

It is easy to show that $\mathbb{I^*}$ has a lower bound, therefore, $\exists$ $m \in \mathbb{I^*}, m= min \left\{ \mathbb{I^*} \right\}$

We now prove that $k=m$.

Indeed, take a random $e \in \mathbb{I^*}$, write $e=qm +r $. If r is not 0, then it is easy to show that $r \in \mathbb{I^*}$, which is a contradiction since $r<m$ and $m= min \left\{ \mathbb{I^*} \right\}$

Thus, all number of $\mathbb {I^*}$ is divisible by m.

Reversely, it can also be conclude that because the smallest number is already $1\times m$, then every numbers divisible by $m$ is also belongs to $\mathbb{I^*}$

Back to your question...

So now, it is clear that your set $\mathbb{S}$ is an ideal on $\mathbb{R}$, thus it has the form of $ \mathbb{S}=k\mathbb{Z}$

Therefore, $k \vert gcd(a,b) $. But it is also apparent that because a and b are foundation numbers, which is, the set $\mathbb{S}$ is constructed upon these two numbers, then all numbers must be divisible by k, and their common divisor must be no more than k (otherwise, due to the proof above, either $a$ or $b$ does not belong to $\mathbb{S}$

Thus, the following conclusions are made:

1. $\mathbb{S}$ consists of and only of all the integers divisible by k.
2. $k=gcd(a,b)$

And hence we have a, b, c, d proven. Q.E.D

P/s: If you like this solution, vote up. If you don't like it, comment below so I can improve it. Thank you for your very interesting question!