1
$\begingroup$

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<p^a$ [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<p^a$. By contradiction, such $y$ doesn't exist.

Could anyone verify my proof please?

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

2 Answers 2

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you for your answer, could you also check if my proof is correct please? $\endgroup$
    – J-A-S
    Commented Dec 26, 2020 at 1:59
  • $\begingroup$ 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 $\endgroup$
    – Aryan
    Commented Dec 26, 2020 at 8:45
  • $\begingroup$ May I ask how does $p-1$ satisfy the 3rd condition? $\endgroup$
    – J-A-S
    Commented Dec 26, 2020 at 9:15
  • $\begingroup$ 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. $\endgroup$
    – Aryan
    Commented Dec 26, 2020 at 11:22
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Thanks, this is clear :) May I also ask if my proof above is valid? $\endgroup$
    – J-A-S
    Commented Dec 26, 2020 at 9:48
  • $\begingroup$ @J-A-S Sorry, but your argument leads to nothing. $\endgroup$
    – egreg
    Commented Dec 26, 2020 at 10:14
  • $\begingroup$ 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? $\endgroup$
    – J-A-S
    Commented Dec 26, 2020 at 10:24
  • $\begingroup$ @J-A-S That's correct, but how do you finish? You need to count the multiples of $p$. $\endgroup$
    – egreg
    Commented Dec 26, 2020 at 10:34
  • $\begingroup$ 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$. $\endgroup$
    – J-A-S
    Commented Dec 26, 2020 at 10:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .