1
$\begingroup$

Theorem Let $a,n \in Z$ with $n \neq 0$. There are $q,r \in Z$ with $a = nq+r$ and $0 \leq r < |n|$, and both $q$ and $r$ are unique with these properties.

Proof The author intends to prove the existence of $q$ and $r$ using well-ordering principle. So it is required to prove that $r \geq 0$ with $r= a-qn$. Consider $S = \{a-zn|z \in Z\}$ and show that the intesection of $S$ and $N$ (set of natural numbers) is non-empty. If $z = -(|a|+1)$ then $a-zn=a+(|a|+1)n \geq a + |a| + n \geq n > 0$. Consequently intersection of $S$ and $N$ is non-empty. The proof continues further.

Question

  1. How was the author able to choose the value of $z$ as $-(|a|+1)$?
  2. How does proving $n >0 $ allow us to conclude that the intersection of $S$ and $N$ is non-empty?
$\endgroup$
1
$\begingroup$

The argument is erroneous as stated: the step $a+(|a|+1)n\ge a+|a|+n$ requires that $n$ be positive, which was not assumed. It can be corrected by letting $e=-\frac{|n|}{n}$, so that $en=-|n|$. Let $S=\{a-zn:z\in\Bbb Z\}$ as before, but take $z_0=e(|a|+1)$. Then

$$a-z_0n=a-e(|a|+1)n=a+|n|(|a|+1)\ge a+|a|+1\ge 1\;,$$

since $|n|>0$ and $a+|a|\ge 0$. This shows that $S$ has at least one positive element, namely, $a-z_0n$. The argument then proceeds by using the well-ordering principle to take the smallest member of $S\cap\Bbb Z^+$, which we can do because we now know that $S\cap\Bbb Z^+$ is a non-empty set of positive integers.

Coming up with $z_0=e(|a|+1)$ in the first place is just a matter of figuring out what sort of $z$ you need in order to be sure that $a-zn>0$. You need $z<\frac{a}n$. Making $z$ a very negative number will certainly do the job, but how negative is ‘very negative’? Clearly $\left|\frac{a}n\right|\le|a|$, since $|n|$ can be no smaller than $1$. Thus, $\frac{a}n\ge-\left|\frac{a}n\right|\ge-|a|$. If $n>0$, we can take $z=-|a|-1$. If $n<0$, however, multiplying by $n$ changes the sign, so we need $z=|a|+1$. The trick with $e$ just avoids having to consider the two cases separately.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.