Page 1 of 1

${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 4:21 am
by Grigorios Kostakos
Prove (or disprove) that following proposition holds:
${\rm{gcd}}(\varphi(n), n)=1$ if and only if $n$ is a prime number, where \(\varphi\) is the Euler totient function.

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 11:47 am
by dr.tasos
15 isnt prime but $ (15,\phi(3) \phi(5))=1 $

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 12:04 pm
by Grigorios Kostakos
dr.tasos wrote:15 isnt prime but $ (15,\phi(3) \phi(5))=1 $
Thanks, dr.tasos.

What can we say if we substitute the condition "$n$ prime number" with "$n$ is square free" ?

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 12:58 pm
by dr.tasos
21 is free of square because $ 21=3 \times 7 $

But $ (21,φ(3) *φ(7))= 3 $

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 1:05 pm
by Grigorios Kostakos
So, $n$ is square free, does not imply that ${\rm{gcd}}(\varphi(n), n)=1$.
What about the converse? i.e.

"If ${\rm{gcd}}(\varphi(n), n)=1$, then $n$ is square free number."

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 1:29 pm
by dr.tasos
If

$ n=p_{1}^{k_{1}}...p_{n}^{k_{n}} $
isnt square free then

$ \exists \quad 1 \leq i \leq n $

Such that $ k_{i}\geq 2 $
$ \phi(n)=(p_{1}-1)p_{1}^{k_{1}-1}... (p_{i}-1)p_{i}^{k_{i}-1}..(p_{n}-1)p_{n}^{k_{n}-1} $

So $ p_{i} | n \quad \wedge \quad p_{i} | \phi(n) $

Contradiction to $ (n,\phi(n))=1 $

Re: ${\rm{gcd}}(\varphi(n), n)=1$

Posted: Sun Mar 20, 2016 4:10 pm
by Grigorios Kostakos
Grigorios Kostakos wrote:"If ${\rm{gcd}}(\varphi(n), n)=1$, then $n$ is square free number."
...and a direct proof:

Let $n=p_1^{r_1}p_2^{r_2}\ldots p_k^{r_k}$ is the decomposition into primes of $n$. Then $\varphi(n)=p_1^{r_1-1}p_2^{r_2-1}\ldots p_k^{r_k-1}(p_1-1)(p_2-1)\ldots(p_k-1)$. Because ${\rm{gcd}}(\varphi(n), n)=1$, by Bezout's lemma we have that there exist integers $a, \,b$ such that \begin{align*}
a\,\varphi(n)+b\,n=1&\quad\Rightarrow \\
a\,p_1^{r_1-1}p_2^{r_2-1}\ldots p_k^{r_k-1}(p_1-1)(p_2-1)\ldots(p_k-1)+b\,p_1^{r_1}p_2^{r_2}\ldots p_k^{r_k}=1&\quad\Rightarrow \\
(\forall\, i\in\{1,2,\ldots k\})\quad{\rm{gcd}}(p_i^{r_i-1},p_i^{r_i})=1&\quad\Rightarrow \\
(\forall\, i\in\{1,2,\ldots k\})\quad p_i^{r_i-1}\cancelto{1}{{\rm{gcd}}(1,p_i)}=1&\quad\Rightarrow \\
(\forall\, i\in\{1,2,\ldots k\})\quad p_i^{r_i-1}=1&\quad\Rightarrow \\
(\forall\, i\in\{1,2,\ldots k\})\quad r_i=1&\quad\Rightarrow \\
n=p_1p_2\ldots p_k\,.&
\end{align*}