18
$\begingroup$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$

Is this impossible? I've been trying to find solutions for at least a week. I've made a conjecture but I wish to suppress it for the time being (I don't think it will be of use to anyone attempting this).

Thanks for any help.

$\endgroup$
9
  • 3
    $\begingroup$ Try $p_1=e_1, p_2=e_2,\ldots, p_k=e_k$. $\endgroup$
    – vadim123
    Sep 30, 2014 at 22:36
  • 2
    $\begingroup$ What's the conjecture? $\endgroup$ Oct 2, 2014 at 3:20
  • $\begingroup$ Here's the PARI script for finding these numbers if anyone's interested: isok(n)=prod(k=1,omega(n),(factorint(n)[k,2])^(factorint(n)[k,1]))==n $\endgroup$ Oct 2, 2014 at 3:34
  • $\begingroup$ Should we suppose that some of the prime numbers can be equal ? $\endgroup$
    – Tom-Tom
    Oct 3, 2014 at 12:38
  • $\begingroup$ @vadim123 There's also $2^4=4^2$. $\endgroup$
    – Tom-Tom
    Oct 3, 2014 at 12:48

3 Answers 3

12
+100
$\begingroup$

EDIT I have edited the lemma's demonstration to make it directly applicable to the problem and corrected some typos in the formulas.

Lemma For any $k$ integers $(\alpha_i)_{1\leq i\leq k}$ and distinct $(n_i)_{1\leq i\leq k}$ such that for all $i$, $\alpha_i\geq0$ and $n_i\geq2$, we have $$ \prod_{i=1}^k n_i^{\alpha_i}\geq\sum_{i=1}^k\alpha_i n_i\tag 1$$ with equality if and only if exactly one of the $\alpha_i$ is nonzero and $\alpha_i=1$ or $n_i=\alpha_i=2$.

Proof:

We first prove that for $n\geq2$ and $\alpha\geq0$, $\alpha n\leq n^\alpha$ and give the equality cases.

  • The case $\alpha=0$ is a strict inequality $0<1$.
  • The case $\alpha=1$ is an equality case.
  • In the case $\alpha=2$, with $n=2$ we have another equality case $2^2=2\times2$.
  • For $\alpha=3$ and $n=2$, we have the strict inequality $n^3=8>6=3n$. For $n\geq3$, $n^2\geq3n>2n$ so we have the strict inequality for $\alpha=2$. Suppose now that for $n\geq2$ we have for some $\alpha\geq2$ the inequality $n^\alpha>\alpha n$. We have therefore $n^\alpha+n>\alpha n+n$ or $$n\times\left(n^{\alpha-1}+1\right)>(\alpha+1)n.$$ Clearly $n^\alpha\geq n^{\alpha-1}+1$ because $\alpha-1\geq 1$. We conclude that $n^{\alpha+1}>(\alpha+1)n$ which proves the required result by recurrence on $\alpha$.

In the next step, we consider $k$ distinct integers larger than $2$. Then the sum of the integers is equal to their product if and only if $k=1$. For two integers $x\geq2$ and $y\geq2$ we have indeed $xy\geq2\max\{x,\,y\}>x+y.$

Consider now the numbers $n_i^{\alpha_i}$ with $\alpha_i>0$. We can apply the product inequality and get $$\prod_{\substack{i\\\alpha_i\neq0}}n_i^{\alpha_i}\geq \sum_{\substack{i\\\alpha_i\neq0}}n_i^{\alpha_i}\geq\sum_{\substack{i\\\alpha_i\neq0}}\alpha_in_i.$$ The first inequality is an equality if and only if only one $\alpha_i\neq0$. The second inequality is an equality if and only if this $\alpha_i=1$ or $\alpha_i=n_i=2$. We can remove the statement $\alpha_i\neq0$ to get the final inequality (1) because factors with $\alpha_i=0$ in the left-hand side product are equal to $1$ and terms with $\alpha_i=$ in the right-hand side sum are equal to $0$.

Proof of the main result

Consider an equality as written by the OP. We can write the number $e_i$ as $$ e_i=p_1^{\alpha_{i,1}}\dots\,p_k^{\alpha_{i,k}}$$ with $\alpha_{i,j}\geq0$ because no other prime factor is possible for $e_i$'s than the $p_i$'s. Let us replace in the equality. We get $$ p_1^{p_1^{\alpha_{1,1}}\dots\,p_k^{\alpha_1,k}}\dots\, p_k^{p_k^{\alpha_{k,1}}\dots\,p_k^{\alpha_k,k}} =p_1^{\alpha_{1,1}p_1+\cdots+\alpha_{k,1}p_k}\dots\, p_k^{\alpha_{1,k}p_1+\cdots+\alpha_{k,k}p_k}.$$ Let us identify the exponents of $p_i$ on both sides. We get $$ e_i=\prod_{j=1}^kp_j^{\alpha_{i,j}}=\sum_{j=1}^k\alpha_{j,i}p_j.$$

Using the lemma lemma with the left-hand side product we get the inequality $$e_i=\prod_{j=1}^kp_j^{\alpha_{i,j}}\geq\sum_{j=1}^k\alpha_{i,j}p_j\tag{2}$$ and we conclude that for all $i$ $$ d_i=\sum_{j=1}^k\left(\alpha_{i,j}-\alpha_{j,i}\right)p_j\geq0.$$

Let us compute the sum $$S=\sum_{i=1}^kp_id_i=\sum_{1\leq i,j\leq k}\left(\alpha_{i,j}-\alpha_{j,i}\right)p_ip_j\geq0,$$ we can swap the indices in the sum and get $$S=\sum_{1\leq i,j\leq k}\left(\alpha_{j,i}-\alpha_{i,j}\right)p_jp_i=-S.$$ As a conclusion, we have $S=0$. Since $d_i\geq0$, we must have $d_i=0$ for all $i$ and consequently $\alpha_{i,j}=\alpha_{j,i}$ for all $i,j$.

Therefore the inequality in (2) is in the equality case. We conclude from the lemma that for any given $i$, there is a unique $j$ such that $e_i=p_j^{\alpha_{i,j}}=\alpha_{i,j}p_j$ and that $\alpha_{i,j}=1$ (then $e_i=p_j$) or $\alpha_{i,j}=2$ (then $e_i=4$, $p_j=2$). The latter case implies $p_j=2$ so, as the $p_i$'s are distinct, there can be only one $\alpha_{i,j}$ equal to $2$, so $i=j$.

Excluding such a pair ($p_i=2$, $e_i=4$), we obtain that there is a permutation $\sigma$ of $\{1,\dots\,k\}$ satisfying $e_i=p_{\sigma(i)}$ for all other $i$. Moreover, the identity $\alpha_{i,j}=\alpha_{j,i}$ implies that $\sigma^2$ is the identity, that is $\sigma$ has no cycle longer than $2$.

As a conclusion, all solutions are given by a set of $k$ prime numbers and one the following

  • a permutation $\sigma$ of $\{1,\,\dots,\,k\}$ with no cycle longer than $2$. Then $e_i=p_{\sigma(i)}$ is a solution.

  • if $2$ is among the primes, say $p_1=2$, a solution with the $k-1$ other prime numbers for $e_2,\,\dots e_k$ and $e_1=4$.

$\endgroup$
6
  • $\begingroup$ Your formula (1) is false because you mixed up the $i/j$ indices. What one really obtains is $\sum_{i=1}^k p_i\alpha_{ij}=\prod_{i=1}^k p_i^{\alpha_{ji}}$. Note that we have $\alpha_{ij}$ on the LHS and $\alpha_{ji}$ on the RHS, and that those two are not the same. $\endgroup$ Oct 6, 2014 at 15:28
  • $\begingroup$ @EwanDelanoy. You are right. I have edited my answer and added a proof that $\alpha_{i,j}=\alpha_{j,i}$. $\endgroup$
    – Tom-Tom
    Oct 7, 2014 at 8:44
  • $\begingroup$ @EwanDelanoy. There were several typos in yesterday's answer. I have corrected all that I found and I think that the proof in now correct. $\endgroup$
    – Tom-Tom
    Oct 8, 2014 at 8:04
  • $\begingroup$ If I have the time, I’ll check your new version. $\endgroup$ Oct 8, 2014 at 8:45
  • $\begingroup$ Looks OK now, I changed my downvote to an upvote $\endgroup$ Oct 8, 2014 at 14:00
4
$\begingroup$

I am only answering this to draw attention to the correct solution set to this problem; I am not intending to accept my own answer.

  1. If the $e_i$ are primes then the only solutions are of the form $e_i=p_{\sigma(i)}$ for any permutation of the set $\{1,2,...,k\}$ with the property that it contains only cycles of length 1 and/or 2.

  2. If not all the $e_i$ are primes, then exactly $k-1$ of them are prime (of the form in (1)) and the remaining $p_m^{e_m}$, $e_m^{p_m}$ pair satisfies $(p_m,e_m)=(2,4)$.

If anyone can prove this, they are a genius.

$\endgroup$
1
$\begingroup$

(Again, I am not intending to accept my own answer)

The case where $k=2$ has been solved, albeit in an ad-hoc way. I was hoping if someone could maybe see how to generalize this approach, or find one that is completely different but generalizes to higher values of $k$.

Problem: If $p,q$ are distinct primes and $a,b$ positive integers, solve $p^a q^b=a^p b^q$.

Solution 1

Clearly we must have $a=p^{f_1} q^{f_2}$ and $b=p^{g_1} q^{g_2}$. Plugging in and equating exponents we get $p^{f_1} q^{f_2} = pf_1+qg_1$ and $p^{g_1} q^{g_2} = pf_1+qg_2$. Let's just get it over and done with.

Case 1: $\boxed{\bf g_1=0}$ Then $p^{f_1} q^{f_2} = pf_1$ and $q^{g_2} = pf_2+qg_2$.

Case 1.1: $\boxed{\bf f_1=0}$ Then $q^{f_2} = 0$: absurd.

Case 1.2: $\boxed{\bf f_1=1}$ Then $pq^{f_2} = p\Leftrightarrow f_2=0$ and $q^{g_2} = qg_2$.

Case 1.21: $\boxed{\bf g_2=0}$ Then $1=0$: absurd.

Case 1.22: $\boxed{\bf g_2=1}$ Then $q=q$, so this subcase is valid.

Case 1.23: $\boxed{\bf g_2=2}$ Then $q^2=2q\Leftrightarrow q=2$, which is valid.

Case 1.3: $\boxed{\bf f_1=2}$ Then $p^2 q^{f_2} = 2p\Leftrightarrow pq^{f_2}=2\Leftrightarrow p=2,f_2=0$ and $q^{g_2}=qg_2$.

Case 1.31: $\boxed{\bf g_2=1}$ Then $q=q$, which is valid.

Case 1.32: $\boxed{\bf g_2=2}$ Then $q=2$, which is valid. Thus, solutions for Case 1 are $\boxed{\boxed{(a,b)=(p,q)}}$, $\boxed{\boxed{a=p,b=4,q=2}}$ and $\boxed{\boxed{a=4,b=q,p=2}}$.

Case 2: $\boxed{\bf f_2=0}$ Observe that this is just Case 1 with $q\mapsto p$, $g_2\mapsto f_2$, $p\mapsto q$, $f_1\mapsto g_1$ and $f_2\mapsto g_2$.

Case 3: $\boxed{\bf f_1=0}$ Then $q^{f_2}=qg_1$ and $p^{g_1} q^{g_2} = pf_2+qg_2$.

Case 3.1: $\boxed{\bf f_2=1}$ Then $q=qg_1\Leftrightarrow g_1=1$ and $pq^{g_2}=p+qg_2$ $\Leftrightarrow g_2=0$, giving $p=p$ which is valid.

Case 3.2: $\boxed{\mathbf{f_2\ne 1}\ (\text{i.e.}\ \mathbf{f_2\ge 2})}$ Then $q^{f_2-1}=g_1$, thus $p^{q^{f_2-1}} q^{g_2} = pf_2+qg_2$.

Case 3.21: $\boxed{\bf g_2=0}$ Then $p^{q^{f_2-1}}=pf_2$ and $g_1=q^{f_2-1}$.

Case 3.211: $\boxed{\bf f_2=2}$ Then $p^q=2p\Leftrightarrow p^{q-1}=2\Leftrightarrow p=q=2$: absurd.

Case 3.22: $\boxed{\bf g_2\ne 0}$ Then $g_1=q^{f_2-1}$ and $p^{q^{f_2-1}} q^{g_2}=pf_2+qg_2$. However, $p^{q^{f_2-1}} q^{g_2} > p^{q^{f_2-1}}+ q^{g_2}$; and moreover $p^{q^{f_2-1}}>pf_2$ for $f_2\ge 1$, since for $f_2\ge 1$ we have $p^{q^{f_2-1}}>2^{2^{f_2-1}}>f_2$. So $f_2=0$, leading to $g_1=q^{-1}=1/q$: absurd. Therefore, the solution for this case is $\boxed{\boxed{(a,b)=(q,p)}}$.

Case 4: $\boxed{\bf g_2=0}$ This is just Case 3 with $q\mapsto p$, $f_2\mapsto g_1$, $p\mapsto q$, $g_2\mapsto f_1$ and $g_1\mapsto f_2$.

$\endgroup$
1
  • $\begingroup$ Using the same method as in my proof you get $pf_1+qg_1=p^{f_1}q^{f_2}\geq pf_1+qf_2$ and $pf_2+qg_2=p^{g_1}q^{g_2}\geq pg_1+qg_2$. Combine them as in $S$ (see my answer): $p^2f_1+pqg_1+pqf_2+q^2g_2\geq p^2f_1+pqf_2+pqg_1+q^2g_2$. We have equality ! Use the two equalities given by the lemma $pf_1+qg_1=pf_1+qf_2$ and $pf_2+qg_2=pg_1+qg_2$, this gives $f_2=g_1$ and that one of $f_1$ or $f_2$ is zero (same for $g$'s). If $f_1=1$ then $f_2=g_1=0$ and $g_2=1$ or $g_2=2$. This gives the solutions $a=p$, $b=q$ and $a=p$, $b=4$ and $q=2$. If $f_1=0$ then $f_2=g_1=1$ gives the solution $a=q$, $b=p$. $\endgroup$
    – Tom-Tom
    Oct 8, 2014 at 8:43

You must log in to answer this question.

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