5
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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))$.

$\endgroup$
1
$\begingroup$

$\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.

$\endgroup$

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.