3
$\begingroup$

Here $m,n\in\mathbb{N}\backslash \{0\}$ and $\phi$ is the Euler Totient function. I have been trying to prove that this statement is true but I'm stuck. I started with applying the product formula for $\phi$ to get that the fraction becomes $\prod_{p\mid n} (1-\frac{1}{p})=\prod_{q\mid m} (1-\frac{1}{q})$, where $p$ and $q$ are primes. I then did some cross multiplication to obtain that: $$\left(\prod_{q\mid m} (q-1)\right)\cdot\left(\prod_{p\mid n} p\right)=\left(\prod_{p\mid n} (p-1)\right)\cdot\left(\prod_{q\mid m} q\right)$$ Now we know that the largest of the $p_{i}=p_{l}$ terms do not divide any of the $p-1$ terms so therefore there is a $q_{k}=q_{r}$ that it divides instead, and since both numbers are prime $p_{l}=q_{r}$. If we continue this process we find that each $p_{i}$ is equal to some $q_{k}$. Now over here is where I got stuck because even though each $p_{i}$ is equal to some $q_{k}$ there may be more $q_{k}$ left over and, so $m$ and $n$ may not have all of the same prime factors. I feel I may be missing something or have done something incorrectly, so any advice would be helpful (thank you in advance).

$\endgroup$
1
$\begingroup$

You are there, you just have to explain your solution better.

Let $p_1<p_2<...<p_k$ be the distinct primes dividing $n$ and $q_1<q_2<...<q_j$ be the distinct primes dividing $m$.

You used $$\prod_{i=1}^k \left(1-\frac{1}{p_i} \right)=\prod_{i=1}^j \left(1-\frac{1}{q_i} \right) (*)$$ to conclude that $p_k=q_j$. Now, forget about $m,n$.

Using $p_k=q_j$ in $(*)$ you get: $$\prod_{i=1}^{k-1} \left(1-\frac{1}{p_i} \right)=\prod_{i=1}^{j-1} \left(1-\frac{1}{q_i} \right) $$

And repeat the process.

To make it a formal proof, prove by induction on $k$ the following Lemma:

Lemma If $p_1<p_2<...<p_k$ and $q_1<q_2<...<q_j$ are prime numbers such that
$$\prod_{i=1}^k \left(1-\frac{1}{p_i} \right)=\prod_{i=1}^j \left(1-\frac{1}{q_i} \right) $$ then $k=j$ and $$p_1=q_1; p_2=q_2;...;p_k=q_k \,.$$

$\endgroup$
2
$\begingroup$

Dividing out the common factors, we have $$ \prod_{p \in A} \frac{p-1}{p} = \prod_{p \in B} \frac{p-1}{p} $$ where $A$ is the set of primes dividing $m$ but not $n$, and $B$ the set of primes dividing $n$ but not $m$. Suppose these sets are not both empty. Then there is a largest prime in $A \cup B$. The denominator of one side is divisible by it, but the denominator of the other side is not.

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