# euler fhi function and power of a prime

• Nov 29th 2011, 04:42 AM
seventhson
euler fhi function and power of a prime
if (n-1) is divisible by φ(n) then there is no prime p such that p^2|m.

Thanks...
• Nov 29th 2011, 10:54 AM
PaulRS
Re: euler fhi function and power of a prime
I suppose you meant to say $\displaystyle p^2 | n$ .

Let's proceed by contradiction, suppose on the contrary that there were a prime $\displaystyle p$ such that $\displaystyle p^2 | n$. Clearly $\displaystyle p\not | (n-1)$ since $\displaystyle n$ and $\displaystyle (n-1)$ are coprime, however $\displaystyle p^2 | n$ implies $\displaystyle p | \varphi ( n)$ $\displaystyle (*)$, and since $\displaystyle \varphi(n) | (n-1)$ we have that $\displaystyle p | (n-1)$ which is a contradiction. $\displaystyle \square$

$\displaystyle (*)$ Check this by using the formula $\displaystyle \phi(n) = n \cdot \prod_{p|n} \left( 1 - \frac{1}{p} \right)$ , where the products runs over all primes dividing $\displaystyle n$.
• Dec 1st 2011, 12:09 PM
seventhson
Re: euler fhi function and power of a prime
Thank you Paul for your nice proof...