Hello I am trying to figure this out for another proof, I want to find the number of elements below $p^2$ divisible by $p$

so say I have $p=5$ and $p^2$ $= 25$ then I have $25$ numbers yet $5$ of these are divisible by $5$

Why is that? I can't really think of an explanation other then $p = p^2*k$ i.e. $p$ divides $p^2$ but why does that give me the number of numbers divisible by $5$?

  • 1
    $\begingroup$ The numbers between $0$ and $p^2$ (inclusive) which are divisible by $p$ are given by the set $\{kp : 1 \le k \le p\}$ of which there are $p$. $\endgroup$ – user296602 Feb 7 '18 at 3:04
  • $\begingroup$ @user296602 if you include zero, you should have $k=0$ as an option. $\endgroup$ – Dave Feb 7 '18 at 3:08

You probably have to see things a little clearer. The answer is right in front, and yet we can't get to it.

It's simple : you want the number of multiples of $p^2$ which are divisible by $p$.

Describe the set of (non-zero, by the looks of your question) multiples of $p$ in set builder form : it is $\{k \times p : k \geq 1\}$. So for example, the set of multiples of $5$ are $\{1 \times 5 , 2 \times 5 , ...\} = \{5,10,15,...\}$.

The set of all numbers less than or equal to $p^2$ is given by $\{k : 1 \leq k \leq p^2\}$. Your task is to find the intersection between these sets. The next few claims are in this regard.

Claim : The set $\{k \times p : p \geq k \geq 1\}$ is contained in both sets.

Proof : Suppose $a$ is contained in both sets. Then $a=k \times p$ for some $k \geq 1$, but we also know that $a \leq p^2$. Therefore, $kp \leq p^2 \implies k \leq p$. So, it follows that $a = kp$ for some $p \geq k \geq 1$. Hence, $a$ is in the set given in the claim.

Claim : Any element in the intersection of both the above sets, is also an element of $\{kp : p \geq k \geq 1\}$.

Proof : Suppose $b$ is in the intersection of both the sets. Then, $b = kp$ for some $k \geq 1$, by containment in the set of multiples. But, by containment in the second set, $b \leq p^2$. Therefore, $kp \leq p^2$, so $k \leq p$. Thus $b=kp$ for some $p \geq k \geq 1$, and hence belong in the set.

Result : The intersection of the two sets is precisely $\{kp : p \geq k \geq 1\}$. We'll call this set $S$.

How many elements in $S$? Let $\phi : \{1,...,p\} \to S$ be the map given by $\phi(k) = kp$. Then, $\phi$ is injective : if $\phi(k) = \phi(l)$ then $kp=lp$ so $k=l$. It is also surjective, since for any $b \in S$, $b = kp$ for some $p \geq k \geq 1$, so obviously $\phi(k) = b$.

But then, $\phi$ is a bijection between $S$ and the set of numbers between $1$ and $p$. It follows that $S$ has exactly $p$ elements. Hence, the size of the demanded set, is $p$.

| cite | improve this answer | |

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.