How can I understand the proof of integer divisibility?

109 Views Asked by At

The context is the book, An Introduction to The Theory of Numbers, by Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery.

Theorem 1.2 says

The division algorithm. Given any integers $a$ and $b$, with $a>0$, there exist unique integers $q$ and $r$ such that $b=qa+r$, $0\leq r<a$. If $a\nmid b$, then $r$ satisfies the stronger inequalities $0<r<a$.

Theorem 1.1 part 5 says

$a \mid b$, $a>0$, $b>0$, imply $a\leq b$

Understanding the Proof

To prove the uniqueness of $q$ and $r$, suppose there is another pair $q_1$ and $r_1$ satisfying the same conditions. First we prove that $r_1 = r$. For if not, we may presume that $r<r_1$ so that $0<r_1-r<a$, and we see that $r_1 -r=a(q-q_1)$, and so $a|(r_1-r)$, a contradiction to Theorem 1.1, part 5. Hence $r=r_1$, and also $q=q_1$.

First of all, I do not see anything. Am I an idiot for not seeing this? Help me to see what "we" all see according to Ivan'n'Herbert'n'Hugh using a more verbose explanation (I am a person of words). This recognition seems essential to understanding the proof, but the book brushes over quickly and moves on to the next theorem.

1

There are 1 best solutions below

9
On BEST ANSWER

Since $b=qa+r$ and $b=q_1a+r_1$, you have\begin{align}r_1-r&=(b-q_1a)-(b-qa)\\&=(q-q_1)a\end{align}and therefore $a\mid r_1-r$.