Division algorithm: What is the meaning of the propositions? I face trouble with understanding certain propositions in the division algorithm. For example, 

Let $a,b \in \Bbb Z, b>0$. 
Let $S = \{a - qb: q \in \Bbb Z, a - qb \geq 0\}$. 
To prove $S$ is nonempty, if $a \geq 0$, let $q = 0$. 
Then $a - 0b = a \geq 0$. 
Thus $a \in S$.

For this prop, I don't know why $a$ can be called "the remainder". For example, $a = 7$ and $b = 4$ yields $7 = 4q + r$. If we set $q = 0$ (we are allowed to do this), the result is $r = 7$ when clearly the result should be $3$ when $q$ is $1$. I am confused here.


If $a < 0$, let $q = a$. Then 
  $$
a - qb = a - ab = a(1-b) \geq 0
$$ since $a \leq 0 < b$.

I don't understand why they let $q = a$. It is rather unclear why. Did they choose $q = a$ because q is already negative? Can there be $q < a$ or $q > a$?
 A: I think $S$ is being defined as the set of all $a-qb$ for which $q$ is an integer and $a-qb\ge 0$
In particular, for example, according to your definition $q$ could be negative - it is just any integer from the first statement $q\in \mathbb Z$.
The proof looks as though it is aiming at proving that there is a unique choice of $q$ which gives a remainder $0\leq r \lt b$. The set $S$ contains all the "potential remainders", and we want to make sure we can find a potential remainder which is the "real" remainder.
We still haven't specified $q$, so it can be any integer, so it can be put equal to zero in the first part. If $a \ge 0$ this gives us a potential remainder which is a non-negative integer
In the second, $b$ is clearly supposed to be a positive integer, and $a$ is a negative integer. We want to find at least one non-negative potential remainder. The value $q=a\lt 0$ can be chosen (we noted $q$ could be negative above). This value works.
In the cases $a$ positive, zero or negative (so, for any $a$ whatsoever) these choices show that there is at least one non-negative potential remainder: they are simple special choices which have done their job when this is established. 
The next step is to show that there is a least non-negative potential remainder - so that the "real" values of $q$ and $r$ can be identified.
So the proof has two parts - first show that there is a non-negative potential remainder, then show that there is a least non-negative potential remainder.
A: I will write out how the proof should go. It is very likely that the actual proof you are reading goes along the same lines, with only minor differences of detail.
We are given two integers $a$ and $b$, with $b\gt 0$. 
Let $S$ be the set of all non-negative integers of the form $a-qb$, where $q$ ranges over the integers. 
The set $S$ is non-empty. This is obvious if $a\ge 0$, for we can take $q=0$. If $a$ is negative, we can take $q=-|a|$. If $a$ is negative, let $a=-c$ and let  $q=a=-c$. Then $a-qb=cb-c=c(b-1)\ge 0$.
Since $S$ is a non-empty set of positive integers, $S$ has a smallest element. Call that smallest element of $S$ by the name $r$. Then $r=a-qb$ for some $q$. Let us call a $q$ such that $a-qb=r$ by the name $q^\ast$ (your book may call it $q$.) We then have 
$$r=a-q^\ast b.$$
This $r$ is indeed the remainder when we divide $a$ by $b$. 
In your concrete example where $a=7$ and $b=4$, the set $S$ consists of all non-negative numbers which can be expressed in the form $a-qb$. Let us name some elements of $S$. There is $7$, obtained by setting $q=0$. There is $3$, obtained by setting $q=1$. There is $47$, obtained by putting $q=-10$. And there are infiniely many others.
But the smallest non-negative element of $S$ is $3$. It is the smallest non-negative element of $S$ that turns out to be the remainder. 
As to your question about the proof that $S$ is non-empty, as we saw this is obvious if $a\ge 0$. So let us take $a$ negative, like $-17$, and let $b=4$. The claim is that if we pick $q=a$, then $a-qb$ is non-negative. Let's check what happens with our numbers. Here $a-qb=(-17)-(-17)(4)=(17)(4)-17\ge 0$. 
