${\rm{gcd}}(\varphi(n), n)=1$
- Grigorios Kostakos
- Founder
- Posts: 461
- Joined: Mon Nov 09, 2015 1:36 am
- Location: Ioannina, Greece
${\rm{gcd}}(\varphi(n), n)=1$
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.
${\rm{gcd}}(\varphi(n), n)=1$ if and only if $n$ is a prime number, where \(\varphi\) is the Euler totient function.
Grigorios Kostakos
Re: ${\rm{gcd}}(\varphi(n), n)=1$
15 isnt prime but $ (15,\phi(3) \phi(5))=1 $
- Grigorios Kostakos
- Founder
- Posts: 461
- Joined: Mon Nov 09, 2015 1:36 am
- Location: Ioannina, Greece
Re: ${\rm{gcd}}(\varphi(n), n)=1$
Thanks, dr.tasos.dr.tasos wrote:15 isnt prime but $ (15,\phi(3) \phi(5))=1 $
What can we say if we substitute the condition "$n$ prime number" with "$n$ is square free" ?
Grigorios Kostakos
Re: ${\rm{gcd}}(\varphi(n), n)=1$
21 is free of square because $ 21=3 \times 7 $
But $ (21,φ(3) *φ(7))= 3 $
But $ (21,φ(3) *φ(7))= 3 $
- Grigorios Kostakos
- Founder
- Posts: 461
- Joined: Mon Nov 09, 2015 1:36 am
- Location: Ioannina, Greece
Re: ${\rm{gcd}}(\varphi(n), n)=1$
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."
What about the converse? i.e.
"If ${\rm{gcd}}(\varphi(n), n)=1$, then $n$ is square free number."
Grigorios Kostakos
Re: ${\rm{gcd}}(\varphi(n), n)=1$
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 $
$ 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 $
- Grigorios Kostakos
- Founder
- Posts: 461
- Joined: Mon Nov 09, 2015 1:36 am
- Location: Ioannina, Greece
Re: ${\rm{gcd}}(\varphi(n), n)=1$
...and a direct proof:Grigorios Kostakos wrote:"If ${\rm{gcd}}(\varphi(n), n)=1$, then $n$ is square free number."
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*}
Grigorios Kostakos
Create an account or sign in to join the discussion
You need to be a member in order to post a reply
Create an account
Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute
Sign in
Who is online
Users browsing this forum: No registered users and 2 guests