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

Number theory
Post Reply
User avatar
Grigorios Kostakos
Founder
Founder
Posts: 461
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

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

#1

Post 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.
Grigorios Kostakos
dr.tasos
Posts: 13
Joined: Tue Nov 24, 2015 7:47 pm

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

#2

Post by dr.tasos »

15 isnt prime but $ (15,\phi(3) \phi(5))=1 $
User avatar
Grigorios Kostakos
Founder
Founder
Posts: 461
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

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

#3

Post 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" ?
Grigorios Kostakos
dr.tasos
Posts: 13
Joined: Tue Nov 24, 2015 7:47 pm

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

#4

Post by dr.tasos »

21 is free of square because $ 21=3 \times 7 $

But $ (21,φ(3) *φ(7))= 3 $
User avatar
Grigorios Kostakos
Founder
Founder
Posts: 461
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

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

#5

Post 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."
Grigorios Kostakos
dr.tasos
Posts: 13
Joined: Tue Nov 24, 2015 7:47 pm

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

#6

Post 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 $
User avatar
Grigorios Kostakos
Founder
Founder
Posts: 461
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

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

#7

Post 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*}
Grigorios Kostakos
Post Reply

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

Register

Sign in

Who is online

Users browsing this forum: No registered users and 7 guests