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$.
-
1$\begingroup$ The general result. $\endgroup$ – André 3000 Apr 26 '16 at 16:39
-
$\begingroup$ See "Totient function". $\endgroup$ – DanielWainfleet Apr 29 '16 at 22:26
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.