7
$\begingroup$

Let $\varphi(\cdot)$ denote the Euler totient function. We know that if $n = p_1^{k_1}\cdot p_2^{k_2} \cdots p_l^{k_l}$ is the unique (up to ordering) representation of a positive integer in terms of primes, then $$\varphi(n) = p_1^{k_1-1}\cdot p_2^{k_2-1} \cdots p_l^{k_l-1} \cdot (p_1-1) \cdot (p_2-1)\cdots(p_l-1).$$ Using this formula, or otherwise, can we say anything about the cases when $m \neq n$ but $\varphi(m) = \varphi(n)$ (for instance, $\varphi(6) = \varphi(3) = 2$)? Can we characterise all the pairs of integers for which this will happen?

An easy case is if $q$ is an odd prime, then $\varphi(q) = \varphi(2q)$. Therefore, if we have two odd integers $m$ and $n$, both of which are not divisible by $q$, and $\varphi(m) = \varphi(n)$, then $\varphi(qm) = \varphi(qn) = \varphi(2qm) = \varphi(2qn)$ since the totient function is multiplicative.

$\endgroup$
8
  • 4
    $\begingroup$ In Wikipedia's Euler's totient function article, the "Ford's Theorem" and, in particular, "Carmichael's conjecture" sections are related to what you're asking. This implies there's no general characterization of what you're asking, but there are certainly special cases, such as what your updated question text states. $\endgroup$ Nov 6, 2019 at 8:00
  • 1
    $\begingroup$ By elementary means, $\varphi$ is finite-to-one. That is $\{n: \varphi(n)=m\}$ is finite for every $m.$ $\endgroup$ Nov 6, 2019 at 10:30
  • 1
    $\begingroup$ twice a number is always the same due to $\phi(2)=1$ there are only so many compositions of a given number $n$ is the main part of the proof of finiteness. $\endgroup$
    – user645636
    Nov 6, 2019 at 14:18
  • 1
    $\begingroup$ @JohnOmielan . If $\varphi(n)=m$ then (I) No prime divisor of $n$ can exceed $m+1$...(II) If $p$ is prime and $k\in \Bbb N$ and $p^k|n$ then $p^{k-1}(p-1)\le m.$ Thus there is an upper bound on $n$... I dk what the "multiplicity of $m$" is. It's a long article. $\endgroup$ Nov 6, 2019 at 21:18
  • 1
    $\begingroup$ @DanielWainfleet Sorry about that. I was confused between there being no upper bound on the possible multiplicity & the multiplicity of any particular $\varphi$ value being finite. You're right that, for any individual $m$, there's a finite # of possible $n$ for which $\varphi(n) = m$. I've deleted my comment because it's not correct. $\endgroup$ Nov 6, 2019 at 21:35

1 Answer 1

2
$\begingroup$

(A.) Correcting an incorrect previous statement

In the answer comment by user645636, Nov 6, 2019, is the claim "[totient of] twice a number is always the same due to $\varphi (2) = 1$". This claim is only sometimes, not always, true. The claim can generally be true if (among other requirements) that number (call it $n$) is not divisible by $2$ (because much of what's implicated here, such as Euler's Theorem ((the one in number theory)), Fermat's Little Theorem, and division within modular-arithmetic congruencies, would require co-primality). (Although the claim might be true even if 2 | n on rare occasion? Nope. Thanks Greg Martin.) Not true f.e. $\varphi (12) = 4$, but $\varphi (2 \times 12) = \varphi (24) = 8$, roughly "because" $2 | 12$. True f.e. $\varphi (5) = \varphi (2 \times 5) = \varphi (10) = 4$.

(B.) I am attacking the original inquiry (what integers have the same totients and why?) by investigating:

  • which sorts of numbers (with which sorts of prime factors) can be multiplied by which further numbers to give products with equal totients?

I call two numbers with the same totient value "totient siblings", hence $\varphi (sib_x) = \varphi (sib_y)$. (We can't use the word "co-totients", that's already used for another purpose.) For example, $\varphi (4 \times 10) = \varphi (6 \times 10) = 16$, same as $\varphi(40) = \varphi(60) = 16$. Here, the $4$ and the $6$ are of interest, they being totient siblings i.e. $\varphi (4) = \varphi (6) = 2$; and their products with $10$ also being of interest, they being two new totient siblings i.e. $\varphi (40) = \varphi (60) = 16$.

This is not a foolproof formula. The sibling assertion $\varphi (sib_a \times n) = \varphi (sib_b \times n)$ is based on the multiplicative property of Euler's totient function. But it requires a certain degree of repeated factors. Although $3, 4, 6$ are all totient siblings with $\varphi = 2$, only $4, 6$ work in this example. $\varphi (3 \times 10) = 8 \neq \varphi (4 \times 10) = \varphi (6 \times 10) = 16$. This is "because" (in a certain way of thinking about it) $3$ lacks a common factor with $10$. The common factor of $2$ that is shared among $4, 6$ and $10$ gets "canceled out" the right number of times to cause the two products $40, 60$ to be totient siblings.

(And note, lest you confuse yourself, that $\varphi (4 \times 10) \neq \varphi (4) \times \varphi (10)$, roughly "because" $2 | 10$ and $2 | 4$, a problem addressed in part (A.) of this answer, above.)

Sad to report, this multiplicative procedure does not catch all integers with that totient. It misses $\varphi (17) = \varphi (32) = 16$. Those two are addressed in part (C.) below. In total we have now four totient siblings, $17, 32, 40$, and $60$, all with $\varphi = 16$, but only two of which are caught by multiplying up on the basis of the multiplicativity of Euler's totient function, while the other two of which are not caught thereby. And this still leaves out two more options, $34, 48$, giving a grand total of six totient siblings $17, 32, 34, 40, 48, 60$ for all of which $\varphi = 16$.

I would have loved to have figured out another procedure to catch the whole lot, and also what the generalized totient value would be as stated in terms of that new procedure. But I don't think any novel such statement exists, since the generation of the totients of the siblings is "different" in three ways (a. one less than a prime; b. half a power of two; c. multiplicativity) but the "same" in one way (Euler's definition of the totient function, stated in the original question, and how it can be calculated by prime powers), yet that one way is a way which we already know.

(C.) Primes of the form $2 ^ k + 1$

Any such prime generates a pair of totient siblings thus:

  • $\varphi (2 ^k + 1) = \varphi (2 ^ {k +1}) = 2 ^ k \iff 2 ^ k + 1$ is prime.

This statement is roughly redundant to the last paragraph of the original question. In my example in part (B.) above, $k = 4$, $2 ^k + 1 = 17$, and $2 ^ { k + 1} = 32$. The siblings $17, 32$ have $\varphi (17) = \varphi (32) = 16 = 2 ^ 4$. Primes of the form $2 ^ k + 1$ include the Fermat Primes, all of which are Fermat Numbers, numbers which are of the form $2 ^ { 2 ^ x } + 1 $.

Further question (answered in comment by perroquet): are there numbers that are prime and are of the form $2 ^ k + 1$ but NOT of the form $2 ^ { 2 ^ x } + 1 $? How do they (if they exist at all) influence this generator method of part (C.)? I haven't strenuously investigated. The next prime $2 ^ k + 1$ is $257$ but its $k = 8$ and $8 = 2 ^ x$ where $x = 3$ so $257$ fits both categories. I stopped there.

Another further question: which other integers would have that same $\varphi = 2 ^ k$ (as $34, 40, 48, 60$ in part (B.)) to match our quasi-Fermat Prime's $\varphi$? Here we are asking what is tantamount to the original question for the special case of $\varphi (p)$ where $p$ is prime.

(D.) Inverse of the Totient Function

Addendum (I'm surprised it wasn't mentioned earlier, might have saved some time): other discussions germane to this question can be found by searching on the terms "inverse totient" thus https://math.stackexchange.com/search?q=inverse+totient .

$\endgroup$
5
  • 1
    $\begingroup$ If $n$ is even then $\phi(2n)$ is never equal to $\phi(n)$—indeed it's always exactly twice as large. This is because $\phi$ is a multiplicative function, and $\phi(2^{k+1})=\phi(2^k)$ is only true when $k=0$. $\endgroup$ Nov 19, 2021 at 16:34
  • $\begingroup$ True Greg Martin, thanks for the pointer! I've edited my statement with a strike-through to indicate as much. $\endgroup$
    – CKP
    Nov 19, 2021 at 19:23
  • $\begingroup$ If $2^k+1$ is prime, then $k=2^x$ (this is an answer to your "further question"). $\endgroup$
    – perroquet
    Nov 19, 2021 at 23:40
  • $\begingroup$ @perroquet -- (I understand your comment to be addressing the first of my "further question"s). I believe that you are asserting (correct me if I'm wrong) that if (a) it's prime and (b) it's of the form $2^k+1$ then (a + b = c) it's also inevitably of the form $2^{2^x}+1$, meaning for any prime $2^k + 1$ we have $k = 2^x$ always? I guess I can buy that assertion, but what's the authority for it? Why must $2^{16}+1$ be (possibly) prime but $2^{11}+1$ be (never) prime (with the ((obvious)) understanding that $16=2^x$ while $11 \neq 2^x$)? Or perhaps I nested towered powers incorrectly? Sorry... $\endgroup$
    – CKP
    Nov 21, 2021 at 3:10
  • $\begingroup$ @perroquet followup ... whoops! I just found this at Wikipedia en.wikipedia.org/wiki/… , which includes the proof of $k = 2^n$ for our situation. Thanks for sending me in the right direction! Will study up over there! :) $\endgroup$
    – CKP
    Nov 21, 2021 at 3:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .