Euclid Division Lemma Proof for J < 0 I am reading George E. Andrews' Number Theory and am at the portion where he proves Euclid's Division Lemma.
The lemma states that
For any integers $k (k>0)$ and $j$, there exist unique integers $q$ and $r$ such that $0≤r<k$ and $j=qk+r.$
I am having difficulty understanding the final part of the proof, where the uniqueness of $q$ and $r$ when $j < 0$ is proven.
By this point it has been established that the lemma is true for $j>1$ because by the basis representation theorem, $j$ has a unique representation to the base $k$
$$j=a_sk^s+a_{s-1}k^{s-1}+...+a_1k+a_0$$
$$=k(a_sk^{s-1}+a_{s-1}k^{s-2}+...+a_1)+a_0$$
$$=kq+r$$
Where $0≤r=a_0<k$.
Supposing a second pair $q'$ and $r'$ exists, there is a representation for $q'$ to the base $k$:
$$q'=b_tk^t+b_{t-1}k^{t-1}+...+b_1k+b_0.$$
Thus,
$$j=kq'+r'$$
$$=b_tk^{t+1}+b_{t-1}k^t+...+b_1k^2+b_0k+r'.$$
But,
$$j=a_sk^s+a_{s-1}k^{s-1}+...+a_1k+a_0.$$
By the uniqueness of the representation of $j$ to base $k$, the following may be gleaned: $r'=r=a_0, \ a_{i+1}=b_i, \ \text{and} \ t=s-1$. Therefore,
$$q'=b_tk^t+...+b_1k+b_0$$
$$=a_sk^{a-s}+...+a_2k+a_1$$
$$=q.$$
Therefore the lemma is true when $j>0$. And if $j=0, \ q=r=0$ is the only possible solution where $0≤r<k$. It is left to prove that the lemma is true when $j<0$.
Here we run into my issue. He writes,
If $j<0$, then $-j>0$, and there exist unique integers $q'' \ \text{and} \ r''$ such that
$$-j=kq''+r''.$$
If $r''=0$, then $j=k(-q'')$; thus we may take $q=-q'' \ \text{and} \ r=0$.
If $r''\neq 0$, then
$$j=-kq''-r''$$
$$=k(-q''-1)+(k-r''),$$
and we may take $q=-q''-1, \ \text{and} \ r=k-r''$.
In either case, $q$ and $r$ satisfy equation $j=kq+r$. Uniqueness for negative $j$ follows from uniqueness for $-j$, which is then positive.
I understand the reason for using the equation $-j=kq''+r''$, since it has already been established that when the equation is greater than $0$, there exists unique integers $q''$ and $r''$. This is useful because it is equivalent to $j=-kq''-r''$, so if there exists unique integers $q''$ and $r''$ for $-j$, they must also exist for $j$, and so we may conclude that the lemma is true when $j<0$, correct? But this raises the question, why doesn't the proof end there? I am missing something.
There is a reason why we treat cases $r'' \neq 0$ and $r''=0$ separately. Why is that?
Furthermore, how is the fact that in the former case $q=-q''$ and $r=r''=0$ relevant to the proof? And in the latter case, how do $q=-q''-1$ and $r=k-r''$ satisfy the equation $j=kq+r$?
Finally, the phrasing of the last sentence is confusing:
Uniqueness for negative $j$ follows from uniqueness for $-j$, which is then positive.
It seems as if "negative $j$" and "$-j$" are different things, otherwise the statement would be begging the question. But what then is "negative $j$?" The "$j$" from the equation $j=kq+r$ multiplied by $-1$? I assume "$-j$" is from the equation $-j=kq''+r''.$
I realize I have asked a great many questions and probably have not been clear enough in stating my confusions. I am very new to number theory and am learning it independently, so I am very prone to misunderstanding the content. This is the only place I can reliably go for clarification. My apologies for the length of this question, I have tried to be as specific as possible to avoid miscommunication.
 A: The approach using base representation is really ridiculous! The mathematics needed to prove the base-representation theorem is much more involved than to prove the division-remainder theorem you asked about, and in fact any proof of the base-representation theorem would essentially need to use the division-remainder theorem! (Not only that, the use of "..." is a sure sign that the cited argument is not rigorous.)
Here is the proof that you ought to learn of the theorem you want. First deal with the non-negative case, namely $j ≥ 0$. Since $j-j$ is a multiple of $k$, by the well-ordering principle for $ℕ$ let $r∈ℕ$ be the minimum such that $j-r$ is a multiple of $k$. Then $r < k$ otherwise $j-(r-k)$ is a multiple of $k$ contradicting minimality of $r$. So we are done. Next deal with the negative case, namely $j < 0$. Since $-j ≥ 0$, using the first case let $q,r∈ℤ$ such that $-j = q·k+r$ and $0 ≤ r < k$. If $r = 0$ then $j = (-q)·k+0$ so we are done. If $r > 0$ then $j = (-q)·k-r = (-q-1)·k+(k-r)$ and $0 ≤ k-r < k$ so we are also done.
A: Consider this.  If $j < 0$ then $|j| > 0$.
So there is a $q, r$ so that $|j| = qk + r$ where $0 \le r < k$.  But that means
$j = -qk -r$.  we can't use $-r$ because obviously we do not have $0 \le -r < k$.
What we do have is $-k < -r \le 0$.  Which is not what we need.
If if $r = 0$ we are okay because $-r= r = 0$ and we do have $j = (-q)k + 0$ as an expression.  That's just fine.
But if $-k < -r < 0$ we have to do something... what can we do?
Well just add $k$.  $0 < k -r < k$
And we have $j = -qk -r=$
$-qk +(k-r) -k =$
$(-q-1)k + (k-r)$.
....
This is basically a "fence post" indexing issue about worrying "well where exactly is our starting point"
====
Consider this:  $qk + 0$ through $qk + (k-r)$ will go from $qk$ to $(q+1)k -1$ inclusively.  this is true for all $q$ positive or negative.
But if $q$ is negative this...."looks weird" we expect, if $q$ is negative for $(q+1)k - 1$ to be $(-|q|+1)k -1$ the same as $(-|q+1|)k -1$ and .... it isn't; $(-|q|+1)k -1 = (-|q-1|)k -1$
but let's look  closely:
If $q = 2$ we go from $2k$ through $3k -1$ with a typical item being $2k + r$.
If $q= 1$ we go from $k$ through $2k -1$ with a typical item being $k + r$.
If $q=0$ we go from $0$ to $k-1$ with a typical item being $ r$.
If $q=-1$ we go from $-k$ to $-1$ with a typical item being $-k +r = -(r-k)$
If $q=-2$ we go from $-2k$ to $-k-1$ with a typical item being $-2k +r=-3k- (k-r)$.
Switching the signs, but not changing the fact that we still count up and we don't switch to counting down really does a number on our intuition, doesn't it.
...
Further illustration if $k = 7$ (just for the sake of illustrion:
$q= 2:  [14+0=14,14 + 1=15; 14+2=16;14+3=17;14+4=18;14+5=19; 14+6=20]$
$q=1: [7+0=7,7 + 1=8; 7+2=9;7+3=10;7+4=11;7+5=12; 7+6=13]$
$q=0: [0+0=0,0 + 1=1; 0+2=2;0+3=3;0+4=4;0+5=5; 0+6=6]$
$q=-1: [-7 + 0=-7;-7+1=-6; -7+2=-5;-7+3=-4;-7+4=-3;-7+5 = -2;-7+6 = -1]$.
$q=-2: [-14 + 0=-14;-14+1=-13; -14+2=-12;-14+3=-11;-14+4=-10;-14+5 = -9;-14+6 = -8]$.
Are you seeing it?
A: E.g. in radix $\,k = 10\,$ we convert a $\rm\color{#c00}{negative}$ integer to sought form $\,q\cdot 10 +r\,$ with $\,\color{#0a0}{0\le r < 10}\,$ by simply $ $ borrowing $\,1\,$ from $\,q,\,$ which adds $10$ to the units digit $\,r\,$ to get it $\ge 0,\,$ e.g.
$$\begin{align} -2(10)\overbrace{\color{#c00}{-1}}^{\textstyle\color{#c00}{< 0}} &\,= -3(10)\!\!\!\!\!\!\!\!\!\overbrace{+\color{#0a0}9}^{\textstyle\color{#0a0}{0\le 9 < 10}}\\[.2em]
      {\rm i.e.} \ -\!(21) &\,= -\!3,9\end{align}\qquad\qquad$$
The same idea works in any radix to force the units digits (remainder) to be $\ge 0$, which is exactly what is done in the proof to reduce the case of negative dividends to positive dividends.
Remark $ $ Allowing negative digits (as $\,-\!3,9 := -3(10)+9\,$ above) often proves handy, e.g. see here for their use in simplifying divisibility test calculations.
