0

I'm looking for a way to prove that this system of equations has no solution for $A, B, C, a, b, c$ positive integers with $a, b, c$ distinct.

$$2^A * a = 3 * c + 1$$

$$2^B * b = 3 * a + 1$$

$$2^C * c = 3 * b + 1$$

If zero can be accepted, then there are solutions, for example: $A=0$, $B=3$, $C=2$, $a=13$, $b=5$, $c=4$.

I've checked solutions using a computer program, but I don't know how to start a mathematical proof.

Can someone help me?

Ian
  • 101,645
CuriousAboutNumbers
  • 13
  • You might want to clarify your question. I'm assuming $a,b,c,A,B,C$ are positive integers, and that you mean $a,b,c$ are distinct (the notation you've used is unclear). The first thing you might want to look at is adding the equations up and collecting terms in $a,b,c$. That quickly gives you a very restricted set of possible values for $A,B,C$. – Chris Lewis Jul 18 '23 at 14:24
  • (just to explain my point about notation, it's true that "$1 \neq 2 \neq 1$", but I suspect you would want to exclude that) – Chris Lewis Jul 18 '23 at 14:25
  • I changed the text to make it clear. And, yes, I need all a, b, and c to be distinct. – CuriousAboutNumbers Jul 18 '23 at 14:34
  • The solution as a column vector $\begin{bmatrix} a \ b \ c \end{bmatrix}$ is the sum of the columns of the inverse of $\begin{bmatrix} 2^A & 0 & -3 \ -3 & 2^B & 0 \ 0 & -3 & 2^C \end{bmatrix}$. This reveals that you will need $A+B+C \geq 5$ to have a positive solution; after that the question is just whether you can get $2^{B+C} + 3 \cdot 2^B$, $3 \cdot 2^C + 2^{A+C}$ and $3 \cdot 2^A + 2^{A+B}$ to be different numbers. That last bit seems to be the hard part. – Ian Jul 18 '23 at 14:39
  • Sorry, now I see that $a,b,c$ must also be integers. I'll slightly edit the OP to make it easier to not get confused in this way. – Ian Jul 18 '23 at 14:52
  • Redone my solution now. @Ian, thanks for pointing out the mistake! I'm curious, though, you said above that you found $A+B+C\ge 5$; I found that $A+B+C\le 5$. Is there a mistake somewhere? Or is it just that $A+B+C=5$? – Chris Lewis Jul 18 '23 at 15:39
  • @ChrisLewis The entries of the inverse have the same sign as $2^{A+B+C}-27$, so for $(a,b,c)$ to be positive, you must have $A+B+C>\log_2(27)$, the smallest such positive integer is $5$. – Ian Jul 18 '23 at 16:46
  • @ian ah, I see what you mean, that's awesome. So $A+B+C$ is exactly $5$. – Chris Lewis Jul 18 '23 at 18:55

1 Answers1

1

Multiplying the equations together, $$abc 2^{A+B+C} = (3a+1)(3b+1)(3c+1)$$

so $$2^{A+B+C} = \left(3+\frac{1}{a}\right)\left(3+\frac{1}{b}\right)\left(3+\frac{1}{c}\right)$$

Since $a,b,c$ are distinct positive integers, the quantity on the right hand side is at most $$\left(3+\frac{1}{1}\right)\left(3+\frac{1}{2}\right)\left(3+\frac{1}{3}\right)=\frac{140}{3}$$

so $A+B+C \le 5$. Since $A,B,C$ are positive, there aren't many possibilities and it's easy to show these don't have integer solutions.

Chris Lewis
  • 1,941
  • Why is it true that $2a=2$? – Ian Jul 18 '23 at 14:54
  • Chris, why "at least one of A,B,C must be less than 2"? I don't get it. – CuriousAboutNumbers Jul 18 '23 at 14:59
  • 1
    @CuriousAboutNumbers That part is a pretty painless proof by contradiction; if they're all $\geq 2$ then the LHS $\geq a+b+c$ but $a+b+c \geq 6$ since they're distinct positive integers. Right after that is where I get confused. – Ian Jul 18 '23 at 15:01
  • @Ian "Why is it true that $2a=2$?" Because I'm an idiot and misread my own calculation! (I mixed up $a$ and $A$) Editing now... – Chris Lewis Jul 18 '23 at 15:07
  • Had to redo that!! Multiplying the equations was the trick I needed, not adding. – Chris Lewis Jul 18 '23 at 15:33
  • Bravo, very interesting your solution!! And more equations can be included in the system with this approach. Do you think it is possible to figure out how to check algebraically that 140/3 is never equal to 2^(A+B+C) and, likewise, Is 175/3 never equal to $2^(A+B+C+D)? – CuriousAboutNumbers Jul 18 '23 at 16:51
  • Thanks! Glad I sorted out the mistake. Not sure what you're asking about here, though - $2$ to the power of a non-negative integer is always an integer, and the numbers you asked about are not. – Chris Lewis Jul 18 '23 at 19:00
  • @CuriousAboutNumbers You are missing the point of this argument a little bit; the point is that $2^{A+B+C} \leq 140/3$ (not equal). $140/3>46$, so the largest power of $2$ with that property is $32$, so $A+B+C$ can't be any bigger than 5. Then you just brute force through the four remaining possibilities: $(A,B,C)=(1,1,1),(1,1,2),(1,1,3),(1,2,2)$. – Ian Jul 18 '23 at 19:06
  • @Ian If I can prove that the right-hand side (140/3, 91/2, 175/3, etc.) will never be a power of 2 then there is no solution – CuriousAboutNumbers Jul 19 '23 at 14:31
  • @CuriousAboutNumbers No, you can't, because the relationship is an inequality, not an equality. All that this argument is doing is giving an upper bound on $2^{A+B+C}$ and thus an upper bound on $A+B+C$. For values below the ensuing bound, this argument alone makes no promises that there are no solutions. For example in the context of the original problem, you still have to do brute force to analyze $(A,B,C)=(1,1,1),(1,1,2),(1,1,3),(1,2,2)$. – Ian Jul 19 '23 at 14:32
  • @Ian, I'm trying to avoid brute force. (A,B,C)=(1,1,1),(1,1,2),(1,1,3),(1,2,2) because $2^(A+B+C)<46$, that is, $2^(A+B+C)$ can be $2^3$, $2^4$ and $2^5$ (respectively 8, 16 and 32). So the right hand side would have to be equal to one of these 3 values for the system of equations to have a solution. However, and I still need to prove this, (3+1/a)(3+1/b)(3+1/c) will never be $2^n$. Thus, it would be proved, without brute force. Am I right? – CuriousAboutNumbers Jul 20 '23 at 15:59
  • @CuriousAboutNumbers If you can do that, then that would be a no-brute-force argument, but it is not what Chris Lewis is suggesting. – Ian Jul 20 '23 at 16:05
  • Yes, but his trick of multiplying the equations opened up more possibilities. I'll think about it and I'll ask a new question on the stackexchange to validate the solution. Thank you very much... – CuriousAboutNumbers Jul 20 '23 at 16:11