# Number Theory Proof involving Reals

I’m working on a number theory proof that has been giving me some trouble for a while. I will explain the problem and the attempts I’ve made.

Let $x\in \mathbb{R}$ and $d \in \mathbb{Z}$ where both $x, d > 0$ (i.e. positive values). Prove that the number of integers, say k, that are $\leq$ $x$ and divisible by $d$ is $[\frac{x}{d}]$ (given that [x] is the greatest integer function).

So I’ve decided to try using a proof by contradiction, but I don’t think I’m doing it correctly, but I will list the steps I’ve taken below.

Suppose not, that is suppose that the number of integers divisible by $d$ and less than $x$ does not equal [$\frac{x}{d}$].

$k \neq$ [$\frac{x}{d}$]

This would imply that $k >$ [$\frac{x}{d}$] or $k <$ [$\frac{x}{d}$], but both of this cases lead to contradictions.

If $k >$ [$\frac{x}{d}$] then that implies that [$\frac{x}{d}$] does not produce the greatest integer because if it did, each of the integers in k could be covered by a factor of [$\frac{x}{d}$]

If $k <$ [$\frac{x}{d}$]then that implies that not all values in k are less than $x$ and divisible by $d$, but this is the definition of values in $k$

Therefore both these are false and $k =$ [$\frac{x}{d}$]

Now I’m having a feeling this is incorrect, but I’m not sure where to go from here and if my solution Is correct or not. Any help would be appreciated.

-
What's the contradiction or the bottom line in the case $\,x>\left[\frac{x}{d}\right]\,$ ? Besides this you seem to have messed up with $\,q\,$ and $\,d\,$ ....fix this. –  DonAntonio Jan 13 '13 at 0:49
What's $d$ and what happened to $q$? –  Git Gud Jan 13 '13 at 0:50
Sorry q was supposed to be d, I changed it. –  Math_Illiterate Jan 13 '13 at 0:53

It’s easier to argue directly. Let $n=\left\lfloor\frac{x}d\right\rfloor$, where I’m using the standard modern notation for the greatest integer function. Then by definition

$$n\le\frac{x}d<n+1\;,$$

so $dn\le x<d(n+1)$. The positive multiples of $d$ that are at most $x$ are therefore $d,2d,3d,\dots,nd$, and there are clearly $n$ of them.

I really don’t understand the argument that you give. For instance, what do you mean by

each of the integers in $k$ could be covered by a factor of $\left\lfloor\frac{x}d\right\rfloor$?

I can guess that by ‘the integers in $k$’ you mean either ‘the $k$ multiples of $d$ that are at most $x$’ or ‘the positive integers $i$ such that $id\le x$’, but we don’t know anything at all about factors of the integer $\left\lfloor\frac{x}d\right\rfloor$.

-
I guess when I said covered I was trying to think about it graphical and the multiples that hit the appropriate values. Thanks again for the help, this way of solving the problem was a lot easier than I thought it would be which means I need to practice more. –  Math_Illiterate Jan 13 '13 at 1:04
@Ockham: You’re welcome, as always. Besides practice, which always helps, you might also want to try to pay extra attention to the terminology that you use: in my experience one of the things that many students find hardest about learning to write mathematics is using terminology carefully and correctly. –  Brian M. Scott Jan 13 '13 at 1:07
Alright I will definitely work more on that –  Math_Illiterate Jan 13 '13 at 1:10

I'd do as follows. Suppose there are $\,k\,$ positive multiples of $\,d\,$ in $\,[d,x]\,$ say:

$$d\,,\,2d\,,\,...,kd\leq x\Longrightarrow x= kd+h\,,\,0\leq h<d\Longrightarrow$$

$$\left[\frac{x}{d}\right]=\left[\frac{kd+h}{d}\right]=\left[k+\frac{h}{d}\right]=k$$

since $\,0\leq h/d <1\,$

-
This works very nicely as well, thanks for the help –  Math_Illiterate Jan 13 '13 at 1:19