Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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$.

share|improve this answer
    
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
add comment

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\,$

share|improve this answer
    
This works very nicely as well, thanks for the help –  Math_Illiterate Jan 13 '13 at 1:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.