# Number TheoryEuler's Totient function

#### mathworker

##### Active member
if $$\displaystyle \varphi(a)=x$$ and $\varphi(b)=y$ are two numbers such that $$\displaystyle \text{gcd}(x,y)=1$$ can we find $a$,$b$ such that $$\displaystyle \text{gcd}(a,b)=1$$.
Where $\varphi()$ is Euler's totient function

Last edited:

#### Bacterius

##### Well-known member
MHB Math Helper
[JUSTIFY]Such $x$ and $y$ do not exist. Totients - except the trivial case of $\varphi{(2)}$ - are even. Hence $\gcd{(x, y)} \geq 2$. So, logically, the answer is, vacuously, "yes", but is probably not what you are looking for. Remember - falsity implies anything PS: I assume you meant $\varphi{(b)} = y$.[/JUSTIFY]

Last edited:

#### mathworker

##### Active member
Yeah,it seams to be correct,but why are they always even?

#### Bacterius

##### Well-known member
MHB Math Helper
Yeah,it seams to be correct,but why are they always even?
Dismiss the trivial case $\varphi{(2)} = 1$. Now consider two cases:

1. $n > 2$ is a power of two - what does its totient look like?

2. $n > 2$ is not a power of two (and hence, has at least one odd prime factor). The totient function is multiplicative - what does this imply?

Hint for the second part: if $p$ is an odd prime, then $\varphi{(p)} = p - 1$ which is even.

#### mathworker

##### Active member
Got it!! Thank you #### PaulRS

##### Member
Dismiss the trivial case $\varphi{(2)} = 1$. Now consider two cases:

1. $n > 2$ is a power of two - what does its totient look like?

2. $n > 2$ is not a power of two (and hence, has at least one odd prime factor). The totient function is multiplicative - what does this imply?

Hint for the second part: if $p$ is an odd prime, then $\varphi{(p)} = p - 1$ which is even.
Another approach:

If $n>2$ , then the elements in $\{1,\ldots,n\}$ which are coprime to $n$ come in pairs of distincts elements $\{x,n-x\}$ where $x \leq n / 2$ and $x$ is coprime to $n$. This follows from the fact that $x$ is coprime to $n$ if and only if so is $n-x$.

Note that $x \leq n-x$ and so we don't repeat pairs. The case $x=n-x$ (in which the supposed pair would have only one element) can't happen since else $2x = n$ and so $x=1$ since $x$ was coprime to $n$, implying $n=2$, which we know is not the case.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Such $x$ and $y$ do not exist.
Erm... either x or y must be 1, so they do exist?
Both leading to a unambiguous "yes" as you explained?

#### Bacterius

##### Well-known member
MHB Math Helper
Erm... either x or y must be 1, so they do exist?
Both leading to a unambiguous "yes" as you explained?
[JUSTIFY]Sorry, your reply notification must have fallen between the cracks.. I am ignoring the trivial case of $x = 1$ or $y = 1$ here. It is not particularly interesting since the conclusion that $\gcd{(a, b)} = 1$ (or $2$) trivially follows.

What I meant is that because the initial assumption that there exists such a (non-trivial) $(a, b)$ pair is incorrect, then the implication that $\gcd{(a, b)} = 1$ is logically true (but not in a useful way). This is the same as saying "if I am a girl, then I have a million dollars" is tautologically true, because I am not a girl, yet it doesn't say anything useful about how much money I have, since the statement does not apply.

See the implication truth table:

$$\begin{array}{|c|c|c|} \hline \\ P & Q & P \implies Q \\ \hline \\ T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \hline \end{array}$$

And so $\neg P \implies (P \implies Q)$. In other words, the following is actually true:

$$\exists a > 2, b > 2 ~ \text{st} ~ \gcd{(\varphi{(a)}, \varphi{(b)})} = 1 ~ ~ \implies ~ ~ \gcd{(a, b)} = 1$$

It wasn't really meant to be taken seriously. For all intents and purposes the real answer is "it doesn't matter because the statement can never apply except in the trivial case that $x = 1$ or $y = 1$."[/JUSTIFY]

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Sorry for being difficult about this, but it seems to me that you're not supposed to choose to ignore a solution, just because you consider it a trivial one.

Anyway, how do you know you're not a girl? Do you have proof? 