# Total number of integers relatively prime to $p^2$

I am reading my number theory textbook and it states without proof that the total number of elements relatively prime to $p^2$ for some prime $p$ is $p(p-1)$. Why is this so? I know that the number of relatively prime elements to $p$ is always $p-1$.

All positive integers not relatively prime to $p^2$ less than or equal to $p^2$ are of the form $pv$, where $v\leq p$. There are $p$ options for $v$; $v=1,2,3...p$, so of the $p^2$ positive integers less than or equal to $p^2$, $p$ are not relatively prime to it. Then there are $p^2-p$ numbers less than or equal to $p^2$ and relatively prime to $p^2$.

EDIT: In general, $\phi(p^n)=p^n-p^{n-1}$ with similar reasoning.

Let's say $p$ is an odd prime.

You already know this but let's review: from $1$ to $p$, the only number $n$ such that $\gcd(n, p) > 1$ is $n = p$; this is because $p$ is prime and not divisible by any number from $2$ to $p - 1$. From $p + 1$ to $2p$, the only number $n$ such that $\gcd(n, p) > 1$ is $n = 2p$. And so on and so forth to $(p - 1)p + 1$ to $p^2$.

What we've done here is take $p$ sets of $p$ consecutive integers and we've found that in each of these sets only one integer $n$ satisfies $\gcd(n, p) > 1$, meaning that $p - 1$ integers in the set of consecutive integers are coprime to $p$. Since there are $p$ sets of $p$ consecutive integers, that means $(p - 1)p$ integers out of the integers from $1$ to $p^2$ are coprime to $p$ and to $p^2$, just as your book asserted.

Hint:-

The number of primes less than and relatively prime to a number $x$ is represented by Euler Phi function-$\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$ where $p_1,p_2,...,p_n$ are the prime factors (distinct) of $x$.

Now what will be this if $x$ is a prime as in your question?

Every number, n can be written as $n = mp + k$ where $0 \le k < p$. $n$ is relatively prime to $p$ if and only if $k \ne 0$. There are $p-1$ options. For numbers less than $p^2$ (not stated in the OP but clearly intended by the book-- otherwise there are infinitely many numbers relatively prime to any number), $0 \le m < p$. So there are $p$ choices for $m$.

Thus there are $p(p-1)$ options for relatively prime to $p$.

The book probably assumed it was clear that only the $p, 2p, \ldots, (p - 1)p$ weren't relatively prime, and as there are p of those there are $p^2 - p = p(p-1)$ that are relatively prime.

Or maybe the book assumed it'd be clear that those that aren't can simply be listed as:

$$1,2,\ldots,p-1$$

$$p+1,p+2,\ldots,2p - 1$$

$$2p+1, 2p+2,\ldots,3p - 1$$

...

$$(p-1)p+1, (p-1)p + 2,\ldots,p^2 - 1$$

Of which there are clearly $p$ sequences of $p-1$ elements.

Or maybe the book had stated there are $p-1$ less than $p (1 \ldots(p-1))$. $2(p-1)(1\ldots(p-1)$ and $p + 1 \ldots p + (p-1))$ less than $2p$. And $m(p-1)$ less than $mp (1 \ldots p-1, p+1 \ldots p + (p-1), 2p + 1 \ldots 2p + (p-1)$, etc. up to $(m-1)p + 1 \ldots (m-1)p + (p-1))$.

$\frac{1}{p}$ of the numbers from 1 to $p^n$ are divisible by p, so $p^n-\frac{p^n}{p}$ are not divisible by p.