17
$\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$
  • 3
    $\begingroup$ Try $p_1=e_1, p_2=e_2,\ldots, p_k=e_k$. $\endgroup$ – vadim123 Sep 30 '14 at 22:36
  • 2
    $\begingroup$ What's the conjecture? $\endgroup$ – Edward Jiang Oct 2 '14 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$ – Edward Jiang Oct 2 '14 at 3:34
  • $\begingroup$ Should we suppose that some of the prime numbers can be equal ? $\endgroup$ – Tom-Tom Oct 3 '14 at 12:38
  • $\begingroup$ @vadim123 There's also $2^4=4^2$. $\endgroup$ – Tom-Tom Oct 3 '14 at 12:48
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$.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Ewan Delanoy Oct 6 '14 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 '14 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 '14 at 8:04
  • $\begingroup$ If I have the time, I’ll check your new version. $\endgroup$ – Ewan Delanoy Oct 8 '14 at 8:45
  • $\begingroup$ Looks OK now, I changed my downvote to an upvote $\endgroup$ – Ewan Delanoy Oct 8 '14 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.

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\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 '14 at 8:43

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.