0
$\begingroup$

Find all positive integers such that $n\phi(m)=m\phi(n)$ where $\phi$ is the Euler totient function.

I think that $n\phi(m)=m\phi(n)$ implies $n=m$ and that I should use prime factorization of n and m to show the $n=m$. So after writing n and m in their prime factorization I have: $n\phi(m)=m\phi(n) \Longleftrightarrow nm(\prod \limits_{i=1}^{k}(1-1/p_i)=mn(\prod\limits_{i=1}^{l}(1-1/q_i) \Longleftrightarrow\prod \limits_{i=1}^{k}(1-1/p_i) =\prod\limits_{i=1}^{l}(1-1/q_i)$

$\endgroup$
  • 1
    $\begingroup$ Note that this is equivalent to $\phi(n)/n = \phi(m)/m$. Look at the values of $\phi(n)/n$ for some range of $n$. It shouldn't take you very long to notice that there are repeated values.... $\endgroup$ – mjqxxxx May 6 '18 at 17:55
  • 2
    $\begingroup$ More specifically, the fact that $\phi(n)/n = \prod_{p | n} (1-1/p)$ makes it obvious that the value only depends on which primes divide $n$... not their multiplicities. $\endgroup$ – mjqxxxx May 6 '18 at 17:58
1
$\begingroup$

Consider the equality $$\prod \limits_{i=1}^{k}\frac{p_i-1}{p_i} =\prod\limits_{i=1}^{l}\frac{q_i-1}{q_i}$$ with $p_1<\ldots <p_k$. Since $p_k$ is in the denominator of the LHS, it must equal to one of the $q_i$. Divide on both sides by $\frac{p_k-1}{p_k}$ and repeat. We get that $k=l$ and $p_i$, $q_i$ are equal in some order. Therefore $\frac{\phi(m)}{m}=\frac{\phi(n)}{n}$ if and only if $m$, $n$ have the same factors

$\endgroup$
  • $\begingroup$ thank you so much! $\endgroup$ – tommy_m May 6 '18 at 18:52
0
$\begingroup$

Your claim is false, but I can't quite tell if my modified version of it is always true:

$$m\phi(n) = n\phi(m) \iff {\rm rad}(m) = {\rm rad}(n)$$

where ${\rm rad}(k)$ is the radical of the integer, the square-free number that is divisible by every prime that divides $k$.

As a simple counterexample to the original claim, take $n=3, m=9$.

$\endgroup$
0
$\begingroup$
Sun May  6 12:29:02 PDT 2018
 m : 2 Phi(m) 1           n : 4 Phi(n) 2
 m : 2 Phi(m) 1           n : 8 Phi(n) 4
 m : 4 Phi(m) 2           n : 8 Phi(n) 4
 m : 3 Phi(m) 2           n : 9 Phi(n) 6
 m : 6 Phi(m) 2           n : 12 Phi(n) 4
 m : 2 Phi(m) 1           n : 16 Phi(n) 8
 m : 4 Phi(m) 2           n : 16 Phi(n) 8
 m : 8 Phi(m) 4           n : 16 Phi(n) 8
 m : 6 Phi(m) 2           n : 18 Phi(n) 6
 m : 12 Phi(m) 4           n : 18 Phi(n) 6
 m : 10 Phi(m) 4           n : 20 Phi(n) 8
 m : 6 Phi(m) 2           n : 24 Phi(n) 8
 m : 12 Phi(m) 4           n : 24 Phi(n) 8
 m : 18 Phi(m) 6           n : 24 Phi(n) 8
 m : 5 Phi(m) 4           n : 25 Phi(n) 20
 m : 3 Phi(m) 2           n : 27 Phi(n) 18
 m : 9 Phi(m) 6           n : 27 Phi(n) 18
 m : 14 Phi(m) 6           n : 28 Phi(n) 12
 m : 2 Phi(m) 1           n : 32 Phi(n) 16
 m : 4 Phi(m) 2           n : 32 Phi(n) 16
 m : 8 Phi(m) 4           n : 32 Phi(n) 16
 m : 16 Phi(m) 8           n : 32 Phi(n) 16
 m : 6 Phi(m) 2           n : 36 Phi(n) 12
 m : 12 Phi(m) 4           n : 36 Phi(n) 12
 m : 18 Phi(m) 6           n : 36 Phi(n) 12
 m : 24 Phi(m) 8           n : 36 Phi(n) 12
 m : 10 Phi(m) 4           n : 40 Phi(n) 16
 m : 20 Phi(m) 8           n : 40 Phi(n) 16
 m : 22 Phi(m) 10           n : 44 Phi(n) 20
 m : 15 Phi(m) 8           n : 45 Phi(n) 24
 m : 6 Phi(m) 2           n : 48 Phi(n) 16
 m : 12 Phi(m) 4           n : 48 Phi(n) 16
 m : 18 Phi(m) 6           n : 48 Phi(n) 16
 m : 24 Phi(m) 8           n : 48 Phi(n) 16
 m : 36 Phi(m) 12           n : 48 Phi(n) 16
 m : 7 Phi(m) 6           n : 49 Phi(n) 42
 m : 10 Phi(m) 4           n : 50 Phi(n) 20
 m : 20 Phi(m) 8           n : 50 Phi(n) 20
 m : 40 Phi(m) 16           n : 50 Phi(n) 20
 m : 26 Phi(m) 12           n : 52 Phi(n) 24
 m : 6 Phi(m) 2           n : 54 Phi(n) 18
 m : 12 Phi(m) 4           n : 54 Phi(n) 18
 m : 18 Phi(m) 6           n : 54 Phi(n) 18
 m : 24 Phi(m) 8           n : 54 Phi(n) 18
 m : 36 Phi(m) 12           n : 54 Phi(n) 18
 m : 48 Phi(m) 16           n : 54 Phi(n) 18
 m : 14 Phi(m) 6           n : 56 Phi(n) 24
 m : 28 Phi(m) 12           n : 56 Phi(n) 24
 m : 30 Phi(m) 8           n : 60 Phi(n) 16
 m : 21 Phi(m) 12           n : 63 Phi(n) 36
 m : 2 Phi(m) 1           n : 64 Phi(n) 32
 m : 4 Phi(m) 2           n : 64 Phi(n) 32
 m : 8 Phi(m) 4           n : 64 Phi(n) 32
 m : 16 Phi(m) 8           n : 64 Phi(n) 32
 m : 32 Phi(m) 16           n : 64 Phi(n) 32
 m : 34 Phi(m) 16           n : 68 Phi(n) 32
 m : 6 Phi(m) 2           n : 72 Phi(n) 24
 m : 12 Phi(m) 4           n : 72 Phi(n) 24
 m : 18 Phi(m) 6           n : 72 Phi(n) 24
 m : 24 Phi(m) 8           n : 72 Phi(n) 24
 m : 36 Phi(m) 12           n : 72 Phi(n) 24
 m : 48 Phi(m) 16           n : 72 Phi(n) 24
 m : 54 Phi(m) 18           n : 72 Phi(n) 24
 m : 15 Phi(m) 8           n : 75 Phi(n) 40
 m : 45 Phi(m) 24           n : 75 Phi(n) 40
 m : 38 Phi(m) 18           n : 76 Phi(n) 36
 m : 10 Phi(m) 4           n : 80 Phi(n) 32
 m : 20 Phi(m) 8           n : 80 Phi(n) 32
 m : 40 Phi(m) 16           n : 80 Phi(n) 32
 m : 50 Phi(m) 20           n : 80 Phi(n) 32
 m : 3 Phi(m) 2           n : 81 Phi(n) 54
 m : 9 Phi(m) 6           n : 81 Phi(n) 54
 m : 27 Phi(m) 18           n : 81 Phi(n) 54
 m : 42 Phi(m) 12           n : 84 Phi(n) 24
 m : 22 Phi(m) 10           n : 88 Phi(n) 40
 m : 44 Phi(m) 20           n : 88 Phi(n) 40
 m : 30 Phi(m) 8           n : 90 Phi(n) 24
 m : 60 Phi(m) 16           n : 90 Phi(n) 24
 m : 46 Phi(m) 22           n : 92 Phi(n) 44
 m : 6 Phi(m) 2           n : 96 Phi(n) 32
 m : 12 Phi(m) 4           n : 96 Phi(n) 32
 m : 18 Phi(m) 6           n : 96 Phi(n) 32
 m : 24 Phi(m) 8           n : 96 Phi(n) 32
 m : 36 Phi(m) 12           n : 96 Phi(n) 32
 m : 48 Phi(m) 16           n : 96 Phi(n) 32
 m : 54 Phi(m) 18           n : 96 Phi(n) 32
 m : 72 Phi(m) 24           n : 96 Phi(n) 32
 m : 14 Phi(m) 6           n : 98 Phi(n) 42
 m : 28 Phi(m) 12           n : 98 Phi(n) 42
 m : 56 Phi(m) 24           n : 98 Phi(n) 42
 m : 33 Phi(m) 20           n : 99 Phi(n) 60
 m : 10 Phi(m) 4           n : 100 Phi(n) 40
 m : 20 Phi(m) 8           n : 100 Phi(n) 40
 m : 40 Phi(m) 16           n : 100 Phi(n) 40
 m : 50 Phi(m) 20           n : 100 Phi(n) 40
 m : 80 Phi(m) 32           n : 100 Phi(n) 40
Sun May  6 12:29:02 PDT 2018

=============================================================================

Sun May  6 12:23:56 PDT 2018
 m : 2 =  2           n : 4 =  2^2
 m : 2 =  2           n : 8 =  2^3
 m : 4 =  2^2           n : 8 =  2^3
 m : 3 =  3           n : 9 =  3^2
 m : 6 =  2 3           n : 12 =  2^2 3
 m : 2 =  2           n : 16 =  2^4
 m : 4 =  2^2           n : 16 =  2^4
 m : 8 =  2^3           n : 16 =  2^4
 m : 6 =  2 3           n : 18 =  2 3^2
 m : 12 =  2^2 3           n : 18 =  2 3^2
 m : 10 =  2 5           n : 20 =  2^2 5
 m : 6 =  2 3           n : 24 =  2^3 3
 m : 12 =  2^2 3           n : 24 =  2^3 3
 m : 18 =  2 3^2           n : 24 =  2^3 3
 m : 5 =  5           n : 25 =  5^2
 m : 3 =  3           n : 27 =  3^3
 m : 9 =  3^2           n : 27 =  3^3
 m : 14 =  2 7           n : 28 =  2^2 7
 m : 2 =  2           n : 32 =  2^5
 m : 4 =  2^2           n : 32 =  2^5
 m : 8 =  2^3           n : 32 =  2^5
 m : 16 =  2^4           n : 32 =  2^5
 m : 6 =  2 3           n : 36 =  2^2 3^2
 m : 12 =  2^2 3           n : 36 =  2^2 3^2
 m : 18 =  2 3^2           n : 36 =  2^2 3^2
 m : 24 =  2^3 3           n : 36 =  2^2 3^2
 m : 10 =  2 5           n : 40 =  2^3 5
 m : 20 =  2^2 5           n : 40 =  2^3 5
 m : 22 =  2 11           n : 44 =  2^2 11
 m : 15 =  3 5           n : 45 =  3^2 5
 m : 6 =  2 3           n : 48 =  2^4 3
 m : 12 =  2^2 3           n : 48 =  2^4 3
 m : 18 =  2 3^2           n : 48 =  2^4 3
 m : 24 =  2^3 3           n : 48 =  2^4 3
 m : 36 =  2^2 3^2           n : 48 =  2^4 3
 m : 7 =  7           n : 49 =  7^2
 m : 10 =  2 5           n : 50 =  2 5^2
 m : 20 =  2^2 5           n : 50 =  2 5^2
 m : 40 =  2^3 5           n : 50 =  2 5^2
 m : 26 =  2 13           n : 52 =  2^2 13
 m : 6 =  2 3           n : 54 =  2 3^3
 m : 12 =  2^2 3           n : 54 =  2 3^3
 m : 18 =  2 3^2           n : 54 =  2 3^3
 m : 24 =  2^3 3           n : 54 =  2 3^3
 m : 36 =  2^2 3^2           n : 54 =  2 3^3
 m : 48 =  2^4 3           n : 54 =  2 3^3
 m : 14 =  2 7           n : 56 =  2^3 7
 m : 28 =  2^2 7           n : 56 =  2^3 7
 m : 30 =  2 3 5           n : 60 =  2^2 3 5
 m : 21 =  3 7           n : 63 =  3^2 7
 m : 2 =  2           n : 64 =  2^6
 m : 4 =  2^2           n : 64 =  2^6
 m : 8 =  2^3           n : 64 =  2^6
 m : 16 =  2^4           n : 64 =  2^6
 m : 32 =  2^5           n : 64 =  2^6
 m : 34 =  2 17           n : 68 =  2^2 17
 m : 6 =  2 3           n : 72 =  2^3 3^2
 m : 12 =  2^2 3           n : 72 =  2^3 3^2
 m : 18 =  2 3^2           n : 72 =  2^3 3^2
 m : 24 =  2^3 3           n : 72 =  2^3 3^2
 m : 36 =  2^2 3^2           n : 72 =  2^3 3^2
 m : 48 =  2^4 3           n : 72 =  2^3 3^2
 m : 54 =  2 3^3           n : 72 =  2^3 3^2
 m : 15 =  3 5           n : 75 =  3 5^2
 m : 45 =  3^2 5           n : 75 =  3 5^2
 m : 38 =  2 19           n : 76 =  2^2 19
 m : 10 =  2 5           n : 80 =  2^4 5
 m : 20 =  2^2 5           n : 80 =  2^4 5
 m : 40 =  2^3 5           n : 80 =  2^4 5
 m : 50 =  2 5^2           n : 80 =  2^4 5
 m : 3 =  3           n : 81 =  3^4
 m : 9 =  3^2           n : 81 =  3^4
 m : 27 =  3^3           n : 81 =  3^4
 m : 42 =  2 3 7           n : 84 =  2^2 3 7
 m : 22 =  2 11           n : 88 =  2^3 11
 m : 44 =  2^2 11           n : 88 =  2^3 11
 m : 30 =  2 3 5           n : 90 =  2 3^2 5
 m : 60 =  2^2 3 5           n : 90 =  2 3^2 5
 m : 46 =  2 23           n : 92 =  2^2 23
 m : 6 =  2 3           n : 96 =  2^5 3
 m : 12 =  2^2 3           n : 96 =  2^5 3
 m : 18 =  2 3^2           n : 96 =  2^5 3
 m : 24 =  2^3 3           n : 96 =  2^5 3
 m : 36 =  2^2 3^2           n : 96 =  2^5 3
 m : 48 =  2^4 3           n : 96 =  2^5 3
 m : 54 =  2 3^3           n : 96 =  2^5 3
 m : 72 =  2^3 3^2           n : 96 =  2^5 3
 m : 14 =  2 7           n : 98 =  2 7^2
 m : 28 =  2^2 7           n : 98 =  2 7^2
 m : 56 =  2^3 7           n : 98 =  2 7^2
 m : 33 =  3 11           n : 99 =  3^2 11
 m : 10 =  2 5           n : 100 =  2^2 5^2
 m : 20 =  2^2 5           n : 100 =  2^2 5^2
 m : 40 =  2^3 5           n : 100 =  2^2 5^2
 m : 50 =  2 5^2           n : 100 =  2^2 5^2
 m : 80 =  2^4 5           n : 100 =  2^2 5^2
Sun May  6 12:23:56 PDT 2018
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.