Let $n\in\mathbb{N}$, $p$ a prime number.

Show that for each $h\in\mathbb{N}$, the number of integers $m$, with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$, where $\left[\theta\right]$ denotes integer part of $\theta$.

I can see how this works for simple examples of $n$ and $p$. I have no real idea as to how to begin proving this.

Any help or hints would be greatly appreciated.

  • 1
    $\begingroup$ I've edited the answer some days ago, It's now more clear? $\endgroup$ – Sabino Di Trani Feb 13 '15 at 23:35

Hint: How many integers $k \in \mathbb{N}$ are such that the product $p^hk$ is smaller than $n$?

Let's $X$ be the set of this integer.

Let's $Y$ be the set of integers $m$ such that $m < n$ and $p^h | m$

Now We have to make some observation:

  1. If $m$ is in $Y$ , you can write $m$ as the product $kp^h$ in a unique form, where $k$ is an integer contained in $X$.

  2. If $k$ is in $X$, the product $m=kp^h$ is an integer smaller than $n$ and such that $p^h|m$, so contained in $Y$.

You can see how to conclude? (The claim is that there exist a bijection between $X$ and $Y$)


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.