It is currently Mon May 21, 2018 5:55 pm


All times are UTC [ DST ]




Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Sun Mar 20, 2016 4:21 am 
Team Member
User avatar

Joined: Mon Nov 09, 2015 1:36 am
Posts: 447
Location: Ioannina, Greece
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


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 11:47 am 

Joined: Tue Nov 24, 2015 7:47 pm
Posts: 13
15 isnt prime but $ (15,\phi(3) \phi(5))=1 $


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 12:04 pm 
Team Member
User avatar

Joined: Mon Nov 09, 2015 1:36 am
Posts: 447
Location: Ioannina, Greece
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


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 12:58 pm 

Joined: Tue Nov 24, 2015 7:47 pm
Posts: 13
21 is free of square because $ 21=3 \times 7 $

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


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 1:05 pm 
Team Member
User avatar

Joined: Mon Nov 09, 2015 1:36 am
Posts: 447
Location: Ioannina, Greece
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


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 1:29 pm 

Joined: Tue Nov 24, 2015 7:47 pm
Posts: 13
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 $


Top
Offline Profile  
Reply with quote  

PostPosted: Sun Mar 20, 2016 4:10 pm 
Team Member
User avatar

Joined: Mon Nov 09, 2015 1:36 am
Posts: 447
Location: Ioannina, Greece
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


Top
Offline Profile  
Reply with quote  

Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC [ DST ]


Mathimatikoi Online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group Color scheme created with Colorize It.
Theme created StylerBB.net