Can Two Numbers with Co-Prime Totients Always Be Found?

[mathworker]

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

 

[Nono713]

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$.​

 

[mathworker]

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

 

[Nono713]

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]

Got it! Thank you

 

[PaulRS]

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.

 

[I like Serena]

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?

 

[Nono713]

Erm... either x or y must be 1, so they do exist?
Both leading to a unambiguous "yes" as you explained?

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$."​

 

[I like Serena]

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? ;)