# The number of elements below $p^2$ divisible by p (p's Prime)

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

• 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$. – user296602 Feb 7 '18 at 3:04
• @user296602 if you include zero, you should have $k=0$ as an option. – 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$.