It is currently Tue Jun 18, 2019 10:04 pm

 All times are UTC [ DST ]

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: ${\rm{gcd}}(\varphi(n), n)=1$Posted: Sun Mar 20, 2016 4:21 am
 Team Member

Joined: Mon Nov 09, 2015 1:36 am
Posts: 460
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

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: 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

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: Sun Mar 20, 2016 12:04 pm
 Team Member

Joined: Mon Nov 09, 2015 1:36 am
Posts: 460
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

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: 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

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: Sun Mar 20, 2016 1:05 pm
 Team Member

Joined: Mon Nov 09, 2015 1:36 am
Posts: 460
Location: Ioannina, Greece
So, $n$ is square free, does not imply that ${\rm{gcd}}(\varphi(n), n)=1$.

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

_________________
Grigorios Kostakos

Top

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: 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

 Post subject: Re: ${\rm{gcd}}(\varphi(n), n)=1$Posted: Sun Mar 20, 2016 4:10 pm
 Team Member

Joined: Mon Nov 09, 2015 1:36 am
Posts: 460
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*}
n=p_1p_2\ldots p_k\,.&
\end{align*}

_________________
Grigorios Kostakos

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC [ DST ]

#### Mathimatikoi Online

Users browsing this forum: No registered users and 0 guests

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

Search for:
 Jump to:  Select a forum ------------------ Algebra    Linear Algebra    Algebraic Structures    Homological Algebra Analysis    Real Analysis    Complex Analysis    Calculus    Multivariate Calculus    Functional Analysis    Measure and Integration Theory Geometry    Euclidean Geometry    Analytic Geometry    Projective Geometry, Solid Geometry    Differential Geometry Topology    General Topology    Algebraic Topology Category theory Algebraic Geometry Number theory Differential Equations    ODE    PDE Probability & Statistics Combinatorics General Mathematics Foundation Competitions Archives LaTeX    LaTeX & Mathjax    LaTeX code testings Meta