# Question on Euler 𝜑-function

Let $$\varphi$$ be the Euler $$\varphi$$-function. We have for any $$a\in\mathbb{Z}^+$$:

$$\varphi(p^a)=p^a-p^{a-1}$$

It is clear that all the positive number of the form $$np$$ with $$1\le n\le p^{a-1}$$ are not relatively prime to $$p^a$$.

May I ask how to prove that all the rest of the positive number less than $$p^a$$, as the above formula indicates, are indeed relatively prime to $$p^a$$

I've just written a trial proof:

So here I think I'm asking if there exists a positive integer $$y$$ such that

• $$y [given]

• $$y\neq np$$ for any $$1\le n\le p^{a-1}$$ [given]

• $$y$$ is not relatively prime to $$p^a$$ ($$\implies$$ there exists $$q\in\mathbb{Z}^+$$ with $$q>1$$ such that $$q\mid y$$ and $$q\mid p^a$$) [assumed]

If so, then there exists a prime $$\alpha$$ such that $$\alpha\mid q$$. Hence, there exists $$m\in\mathbb{Z}^+$$ such that $$m\alpha =p^a$$. Thus, $$\alpha=p$$ since $$p$$ is the only prime factor of $$p^a$$. Then $$p\mid q$$. Hence, $$p\mid y$$. We must have $$y=np$$ for some $$1\le n\le p^{a-1}$$ because $$y. By contradiction, such $$y$$ doesn't exist.

Could anyone verify my proof please?

• Count the total number of numbers which have common factor with $p^a$ Commented Dec 25, 2020 at 3:39
• $\phi$'s multiplicativity won't help with induction because $p^a$ and $p$ are not relatively prime. Commented Dec 25, 2020 at 3:46
• @Greg Martin Agreed. Commented Dec 25, 2020 at 4:42
• @GregMartin and Infinity_hunter, thank you for your helps! Could you please check if my proof above is appropriate? Commented Dec 25, 2020 at 9:58

Actually because the only prime divisor of $$p^a$$ is $$p$$ the only common prime divisor between $$p^a$$ and a number less than it can be $$p$$ so we just have to count all numbers less than $$p^a$$ which are divisible by $$p$$ and this number is clearly equal to $$p^{a-1}$$ so there are totally $$p^{a-1}$$ numbers less than $$p^a$$ that are not relatively prime to $$p^a$$ and therefore $$p^a-p^{a-1}$$ numbers that are relatively prime to $$p^a$$.

• Thank you for your answer, could you also check if my proof is correct please? Commented Dec 26, 2020 at 1:59
• If I got it right, your proof is wrong because you're just saying that such y doesn't exist but p-1 satisfies both conditions Commented Dec 26, 2020 at 8:45
• May I ask how does $p-1$ satisfy the 3rd condition? Commented Dec 26, 2020 at 9:15
• Oh I thought that's one of your results. Then what's the point to prove such a thing. Anything that's not relatively prime to p is a multiple of it that's trivial. Commented Dec 26, 2020 at 11:22

A number in $$X_a=\{0,1,2,\dots,p^a-1\}$$ is coprime with $$p$$ if and only if it is not divisible by $$p$$.

The map $$X_{a-1}\to X_a$$ defined by $$x\mapsto px$$ is injective and its image consists of the elements divisible by $$p$$.

Therefore the number of elements in $$X_a$$ that don't belong to the image of the map is $$p^a-p^{a-1}$$.

• Thanks, this is clear :) May I also ask if my proof above is valid? Commented Dec 26, 2020 at 9:48
• @J-A-S Sorry, but your argument leads to nothing. Commented Dec 26, 2020 at 10:14
• May I ask why? To me, if that contradiction works, then it should imply that for all positive integer $y$ such that $y$ is not a multiple of $p$ and such that $y<p^a$, $y$ is a relative prime to $p^a$. May I ask where the proof breaks? Commented Dec 26, 2020 at 10:24
• @J-A-S That's correct, but how do you finish? You need to count the multiples of $p$. Commented Dec 26, 2020 at 10:34
• Oh umm, I mean, it should be obvious that there are $p^{a-1}$ numbers of positive multiple of $p$ that is less than or equal to $p^a$ (may I ask if you're saying that we need to explicitly prove this? I think here we are enumerating all the integer multipliers from $1$ to the maximum that allows, so to me it should be self-evident that all multiples are counted). And $p^a - p^{a-1}$ means that we take away all those multiples and my argument then tells us that what remain are forced to be relatively prime to $p^a$. Commented Dec 26, 2020 at 10:53