# Are there values $k$ and $\ell$ such that $n$ = $kd$ + $\ell$? Prove.

Suppose that n $\in$ $\mathbb Z$ and d is an odd natural number, where $0 \notin\mathbb N$. Prove that $\exists$ $\mathcal k$ and $\ell$ such that $n =\mathcal kd +\ell$ and $\frac {-d}2 < \ell$ < $\frac d2$.

I know that this is related to Euclidean's Algorithm and that k and $\ell$ are unique. I do not understand where to start proving this (as I don't most problems like these), but I also have a few other questions.

Why is is that d is divided by 2 when it is an odd number? I'm not even sure how $\ell$ being greater than and less than these fractions has anything to do with the rest of the proof. Couldn't $\ell$ be any value greater than or less than $0$?

Since d can never equal $0$, then kd could never equal $0$, so doesn't that leave the only n to possibly equal $0$?

I would appreciate anyone pushing me in the correct direction.

-
What's $k^*$ and $d^*$? –  Patrick Li Nov 3 '12 at 1:18
I screwed up the formatting. It's just $kd$. –  Christina Nov 3 '12 at 1:22
Hint: a set $\,S\,$ of $\,d\,$ consecutive integers contains every possible remainder modulo $d,\:$ hence $\, n\equiv \ell\pmod{d},\:$ for some $\,\ell\in S.\ \$ –  Bill Dubuque Nov 3 '12 at 1:23

We give a quite formal, and unpleasantly lengthy, argument. Then in a remark we say what's really going on. Let $n$ be an integer. First note that there are integers $x$ such that $n-xd\ge 0$. This is obvious if $n\ge 0$. And if $n \lt 0$, we can for example use $x=-n+1$.

Let $S$ be the set of all non-negative integers of the shape $n-xd$. Then $S$ is, as we observed, non-empty. So there is a smallest non-negative integer in $S$. Call this number $r$. (The fact that any non-empty set of non-negative integers has a smallest element is a hugely important fact equivalent to the principle of mathematical induction. It is often called the Least Number Principle.)

Since $r\in S$, we have $r\ge 0$. Moreover, by the definition of $S$ there is an integer $y$ such that $r=n-yd$, or equivalently $n=yd+r$.

Note that $r\lt d$. For suppose to the contrary that $r \ge d$. Then $r-d\ge 0$. But $r-d=r-(y+1)d$, and therefore $r-d$ is an element of $S$, contradicting the fact that $r$ is the smallest element of $r$.

To sum up, we have shown that there is an $r$ such that $0\le r\lt d$ and such that there exists a $y$ such that $r=n-yd$, or equivalently $n=yd+r$.

Case (i): Suppose that $r\lt \dfrac{d}{2}$. Then let $k=y$ and $\ell=r$. We have then $n=kd+\ell$ and $0\le \ell\lt \dfrac{d}{2}$.

Case (ii): Suppose that $r \ge \frac{d}{2}$. Since $d$ is odd, we have $r\gt \dfrac{d}{2}$. We have $$\frac{d}{2}\lt r \lt d.$$ Subtract $d$ from both sides of these inequalities. We obtain $$-\dfrac{d}{2}\lt r-d\lt 0,$$ which shows that $$-\frac{d}{2}\lt n-yd-d\lt 0.$$ Finally, in this case let $k=y+1$ and $\ell=n-kd$. Then $n=kd+\ell$ and $$-\dfrac{d}{2}\lt kd+\ell\lt 0.$$

Remark: There is surprisingly little going on here. We first found the remainder $r$ when $n$ is divided by $d$. But the problem asks for a "remainder" which is not necessarily, like the usual remainder, between $0$ and $d-1$. We want to allow negative "remainders" that are as small in absolute value as possible. The idea is that if the ordinary remainder is between $0$ and $d/2$, we are happy with it, but if the ordinary remainder is between $d/2$ and $d-1$, we increase the "quotient" by $1$, thereby decreasing the remainder by $d$, and putting it in the right range. So for example if $n=68$ and $d=13$, we use $k=5$, and $\ell=3$. If $n=74$ and $d=13$, we have the usual $74=(5)(13)+9$. Increase the quotient to $6$. We get $74=(6)(13)+(-4)$, and use $k=6$, and $\ell=-4$.

We gave a proof in the traditional style, but the argument can be rewritten as an ordinary induction argument on $|n|$. It is a good idea to work separately with non-negative and negative integers $n$. We sketch the argument for non-negative $n$. The result is obvious for $n=0$, with $k_0=\ell_0=0$. Suppose that for a given non-negative $n$ we have $n=k_nd+\ell_n$, where $\ell_n$ obeys the inequalities of the problem, that is, $-d/2\lt \ell_n\lt d/2$. If $\ell_n\le (d-3)/2$, then $n+1=k_{n+1} +\ell_{n+1}$, where $k_{n+1}=k_n$ and $\ell_{n+1}=\ell_n+1$. If $\ell_n=(d-1)/2$, let $k_{n+1}=k_n+1$ and $\ell_{n+1}=-(d-1)/2$. It is not hard to verify that these values of $\ell_{n+1}$ are in the right range.

-