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.

  • $\begingroup$ What's $k^*$ and $d^*$? $\endgroup$ – Patrick Li Nov 3 '12 at 1:18
  • $\begingroup$ I screwed up the formatting. It's just $kd$. $\endgroup$ – Christina Nov 3 '12 at 1:22
  • 1
    $\begingroup$ 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.\ \ $ $\endgroup$ – 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.


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.