Coprime Triples

The given conditions are equivalent to $abc|ab+bc+ca-31$ , since $a,b,c$ are pairwise coprime.

$\rightarrow ab+bc+ca=31+(abc)k$ , $k$ is a integer.

Case 1: $k \leq 0$

$\rightarrow 3a^2<ab+bc+ca\leq 31 \rightarrow a\leq 3$

Case 1.1: $a=3$

$\rightarrow 3(b+c)+bc\leq 31 \rightarrow (b+3)^2<(b+3)(c+3)\leq 40 \rightarrow b\leq 3$ contradicts $a<b$

Case 1.2: $a=2$

$\rightarrow 2(b+c)+bc\leq 31 \rightarrow (b+2)^2<(b+2)(c+2)<35 \rightarrow b\leq 3 \rightarrow b=3$

$\rightarrow 5c\leq 25$ and $c|(2)(3)-31 \rightarrow c=4$ or $c=5$ and $c|25 \rightarrow c =5$

$\rightarrow (a,b,c)=(2,3,5)$

Case 1.3: $a=1$

$\rightarrow (b+c)+bc\leq 31 \rightarrow (b+1)^2<(b+1)(c+1)<32 \rightarrow b\leq 4 \rightarrow b=2,3$ or $4$

Case 1.3.1: $b=2$

$\rightarrow 3c\leq 29$ and $c|(1)(2)-31 \rightarrow 3\leq c\leq 9$ and $c|29 \rightarrow$ no solution. Case 1.3.2: $b=3$

$\rightarrow 4c\leq 28$ and $c|(1)(3)-31 \rightarrow 3\leq c\leq 7$ and $c|28 \rightarrow c=4$ or $c=7$

By checking, both sets of solutions of work, so we have $(a,b,c)= (1,3,4)$ and $(1,3,7)$

Case 1.3.3: $b=4$

$\rightarrow 5c\leq 27$ and $c|(1)(4)-31 \rightarrow c=5$ and $c|27 \rightarrow$ no solution.

Case 2: $k\geq 1$

Dividing both sides by $abc$ , we have

$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{31}{abc}+k>1$

$1<\frac{1}{a}+\frac{1}{b}+\frac{1}{c}<\frac{3}{a} \rightarrow a=1$ or $a=2$

Case 2.1: $a=2$

$\rightarrow \frac{1}{2}<\frac{1}{b}+\frac{1}{c}<\frac{2}{b} \rightarrow b=3$

$\rightarrow c|(2)(3)-31 \rightarrow c=5$ or $c=25$

$(2,3,5)$ is already in our list of solution, while $(2,3,25)$ does not satisfy $3|(2)(25)-31 \rightarrow$ no solution.

Case 2.2: $a=1$

$\rightarrow \frac{1}{b}+\frac{1}{c}-\frac{31}{bc}=k-1\geq0$

Case 2.2.1: $k\geq1$

$1<\frac{1}{b}+\frac{1}{c}<\frac{2}{b} \rightarrow$ no solution.

Case 2.2.2: $k-1=0$

$\rightarrow b+c=31$ . We have 14 solutions: $a,b,c)=(1,2,29), (1,3,28),...,(1,15,16)$ .

Hence, the answer is $1+2+14=17$ .

First, we can see that $a | (bc-31)$ and $a | a(b+c)$ so $a | (ab+bc+ca-31)$ . It is similarly with $b, c$ . In the other hand, because $\gcd(a,b) = \gcd(b,c) = \gcd(c,a)=1$ so $abc | (ab+bc+ca-31)$ . (*)

We consider some cases: (1) If $a = 1$ then $b | c-31$ and $c | b-31$ . If $b+c = 31$ then two conditions satisfy and from $a = 1 < b < c$ , we have $2b < 31$ and $2 \le b \le 15$ , so there are 14 values of $b$ and 14 values of $c$ corresponding. And if $b+c \neq 31$ , we have $1 < b < c < 31$ . If not, there are 3 cases: if $b > 31$ then $c > b>b-31 >0$ a contradiction because c|(b-31); if $b = 31$ then $31 | c-31$ leads to $gcd(b,c) >1$ a contradiction; if $b < 31 < c$ then $c > 31-b$ , $-c < b-31$ so $|c| > |b-31|$ a contradiction. Hence, $b+c <31$ , note that $bc | 31 - (b+c)$ . If $b \ge 5$ then $c \ge 6$ , so $bc \ge 30, 31-(b+c) \le 11$ , a contradiction. So $b = 3$ or $b = 4$ . If $b = 3$ then $3 | (c-31)$ and $c | 28$ , it is easy to see that $c = 4, c = 7$ . If $b=4$ then $4 | (c-31)$ and $c | 27$ , leads to $c = 27$ , which is consider in the previous case. Hence, in this case, there are 16 triples $(a,b,c)$ satisfy the condition. (2) If $a = 2$ then $b | 2c -31$ and $c | 2b -31$ , we also have $bc | (2b+2c-31)$ . With similar argument, we have $b = 3, c = 5$ . (3) If $a \ge 3$ , then $abc \ge 3bc > ab+bc+ca > |ab+bc+ca-31| \ge |abc|$ which a contradiction. Therefore, in total, we have 17 triples of $(a,b,c)$ .

Observe that (bc - 31)(ab - 31)(ac-31) is a multiple of abc since a,b,c are coprime. Expanding, we get abc = 31 (impossible) or bc + ca + ab - 31 is a multiple of abc. Let bc + ca + ab - 31 = kabc

If k = 0, bc + ca + ab = 31 checking a = 1, we have (b,c) = bc + c + b = 31. Simple checking shows only (1,3,7) as the only solution. checking a = 2 it is clear 2,3,5 is the only solution.

If k >= 1, bc + ca + ab >= 31 + abc bc + ca + ab > abc 1/a + 1/b + 1/c > 1 The only possible solutions are (1,b,c), (2,3,4), (2,3,5). We have already checked and rejected (2,3,4), and accepted (2,3,5) as a solution. Considering bc + c + b = 31 + bc, we get (a,b,c) = (1,b,31-b) of which there are 14 solutions.

The last case, where k is negative:

ab + bc + ca - 31 < 0 ab + bc + ca < 31 Checking this condition: (1,2,3) (1,2,5) (1,2,7) (1,2,9), (2,3,4) are the only possibilities. We can easily check and reject all of them

Thus there are 17 possibilities: (2,3,5), (1,3,7), (1,3,4) and (1,b,31-b) for b from 2 to 15.

From the problem, it's already obvious that a|ab+bc+ac-31,b|ab+bc+ac-31, and c|ab+bc+ac-31. As a, b, and c are coprime, it's easy to prove that abc|ab+bc+ac-31 however, the only way to make ab+bc+ac-31 divisible by abc is to have it larger or equal abc, equal 0, or less or equal -abc, because abc obviously can't divide anything between 0 and abc or between 0 and -abc.

If ab+bc+ac-31 <= -abc ab+ac+bc+abc <=31 we know that the smallest combination of three coprime positive numbers are (1,2,3),(1,2,5),(1,3,5), and (2,3,5). Even among them, only (1,2,5) and (1,3,5) can result in ab+bc+ac+abc less or equal 31. Larger combination will have larger result as well. However, neither of those two combination works for the original problem. This option doesn't have suitable number.

If ab+bc+ac-31 = 0 again, we pick the number from the smallest coprime numbers combinations possible. The only combination fitting is (2,3,5) and it does fit the original problem after checking. If ab+bc+ac-31>=abc note that ab+bc+ac <3bc , so abc<3bc the only possible a are 1 and 2 if a=1 abc|ab+bc+ac-31 bc|b+c-31 again, b+c-31 may be 0, >=bc or <=-bc we can easily check that all combination of (1,b,31-b) works for the problem. If b+c-31>=bc while b+c-31<2c 2c>bc b<2 is a contradiction. If b+c-31<=-bc b+c+bc<=31 we can see by listing the possibilities that the largest b fulfilling this criteria is 4. As the range is already narrowed down, the remaining is trial and error. From here, we get working combinations of (1,3,4) and (1,3,7) if a=2 abc|ab+bc+ac-31 bc|2b+2c-31 again, we try all three possibilities 2b+2c-31=0 is already imposible. If 2b+2c-31>=bc while 2b+2c-31<4c b<4 the only b possible is 3, and the equation becomes abc|ab+bc+ac-31 6c |5c-25 it's impossible to have 5c-25>=6c or <=-6c as c is obviously >3. The only way to make this divisibility work is to have 5c-25=0 again, we get the combination of (2,3,5) If 2b+2c-31<=-2bc 2b+2c+2bc<=31 b+c+bc<=15 it's easy to see that any b larger than 2 and c larger than b will not work for this inequality.

Thus, the only answers are (1,3,4),(1,3,7),(1,b,31-b), and (2,3,5) while there are 14 solutions in the form of (1,b,31-b)

This one was a lot of fun, took me a few hours to get it right.

coprimetriples.c

#include <stdio.h>
#define LIMIT 10000

int gcd(int a, int b) {
  int c;
  while (a!=0) {
    c=a; 
    a=b%a;  
    b=c;
  }
  return b;
}

int coprime3(int a, int b, int c) {
    return gcd(a,b) == 1 && gcd(a,c) == 1 && gcd(b,c) == 1;
}

int main(int count, char** args) {

    int a,b,c = 0;
    int results = 0;

    for (a=1; a<LIMIT; a++) {
        for (b=1; b<LIMIT; b++) {
            for (c=1; c<LIMIT; c++) {
                if (a < b && b < c &&
                    ((b*c - 31) % a == 0) &&
                    ((c*a - 31) % b == 0) &&
                    ((a*b - 31) % c == 0) &&
                    coprime3(a,b,c)==1) {
                            results++;
                            printf("(%d,%d,%d) found:%d\n\n",
                                a,
                                b,
                                c,
                                results);
                }
            }
        }
    }

    return 0;
}

Output

(1,2,29) found:1

(1,3,4) found:2

(1,3,7) found:3

(1,3,28) found:4

(1,4,27) found:5

(1,5,26) found:6

(1,6,25) found:7

(1,7,24) found:8

(1,8,23) found:9

(1,9,22) found:10

(1,10,21) found:11

(1,11,20) found:12

(1,12,19) found:13

(1,13,18) found:14

(1,14,17) found:15

(1,15,16) found:16

(2,3,5) found:17

Let us write $bk = ac - 31$ and $cl = ab - 31.$ Multiplying the first equation by $l$ we get $bkl = a(ab-31) - 31 l$ so that $b (a^2 - kl) = 31 (a+l).$

$31$ can't divide $b$ because that would also imply that $31$ divides $ac$ in contradiction with coprimalilty assumption. Therefore $31$ divides $a^2 - kl$ and we can write $a^2 - kl = 31 n$ to obtain $bn = (a + l).$

Now, let us return to the very first two equations. Subtracting them, we get $bk - cl = a(c-b)$ and adding $0=bl - bl$ we get $b(k-l) - l(c-b) = a(c-b)$ $b(k-l) = (a+l) (c-b)$ so that, using $bn = a+l$ we derived previously, $k-l = n(c-b).$ Using the very first equations again to express $k$ and $l$ and multiplying the last equation by $bc$ we get $c(ac -31) - b(ab - 31) = nbc (c-b).$ Finally, dividing by $c - b)$ we obtain the key formula $a(b+c) - 31 = nbc.$ Now, because $a < b < c$ we get that $a(b+c) / bc < 2$ . Suppose now that $bc > 31$ . Then the only possible values of $n$ are $0$ and $1$ . For $n = 0$ we have $a (b+c) = 31$ which is non-sense. When $n = 1$ we have $a | 31 + bc$ which, combined with the fact that $a | bc - 31$ implies that $a = 1$ .

So, we are left with two possibilities, $a = 1$ or $bc < 31$ . Since this answer is already too long, I'll be brief, but with bit more work we can show that for $a = 1$ $2 \leq b \leq 15$ , $b+c = 31$ are all solutions (e.g., $1, 4, 27$ is one of them). All of these have $n=1$ . For $n= -1$ we get $(1, 3, 7)$ and $(2, 3, 5)$ and for $n=-2$ we have $(1, 3, 4$ ). No other $n$ can work (proof left for the reader), so this gives us all of the $\bf 17$ solutions.

a,b,c all divide ab+ac+bc−31, so since they are pairwise coprime, abc∣(ab+ac+bc−31) Note that the above is equivalent to the given conditions. Consider 3 cases, where ab+ac+bc−31 is =0,<0,>0.

Case 1: ab+ac+bc−31=0, then 31=ab+ac+bc≥a(a+1)+a(a+2)+(a+1)(a+2)=3a2+6a+2, so a≤2.

If a=1, then c>b>1, and (b+1)(c+1)=32. We have 3≤b+1<32−−√ so b+1=4,c+1=8 and (a,b,c)=(1,3,7).

If a=2, then c>b>2 and (b+2)(c+2)=35. We have 5≤b+2<35−−√ so b+2=5,c+2=7 and (a,b,c)=(2,3,5).

Case 2: ab+ac+bc−31<0, then abc≤|ab+ac+bc−31|=31−ab−ac−bc.

If a≥2, then b≥3,c≥4, so 31≥abc+ab+ac+bc≥2(3)(4)+2(3)+2(4)+3(4)>31, a contradiction. Thus a=1, so c>b>1 and 2bc+b+c≤31.

If b≥3, then c≥4, so 31≥2bc+b+c≥2(3)(4)+(3)+(4)=31, so equality holds and we have (a,b,c)=(1,3,4). Checking, this works.

Otherwise b=2, so 5c≤29, giving c=3,4,5. However we also have c∣ab−31=−29, so this gives no solution.

Case 3: ab+ac+bc−31>0, then abc≤ab+ac+bc−31.

If a≥3, then abc≥3bc≥ab+ac+bc>ab+ac+bc−31≥abc, a contradiction.

Thus a=1,2. If a=2, then c>b>2 and 2bc≤2b+2c+bc−31, so bc+31≤2b+2c, so (b−2)(c−2)+27≤0, a contradiction.

Thus a=1, so bc≤b+c+bc−31, so b+c≥31. Also bc∣(b+c+bc−31), so bc∣(b+c−31). If b+c=31, we have (a,b,c)=(1,2,29),(1,3,28),…,(1,15,16). Otherwise bc≤b+c−31, so (b−1)(c−1)+30≤0, a contradiction.

To conclude, the solutions are (1,3,7),(2,3,5),(1,3,4),(1,2,29),(1,3,28),…,(1,15,16) i.e. number of solutions are 3+14=17

a,b,c all divide ab+ac+bc−31, so since they are pairwise coprime, abc∣(ab+ac+bc−31)

Note that the above is equivalent to the given conditions. Consider 3 cases, where ab+ac+bc−31 is =0,<0,>0.

Case 1: ab+ac+bc−31=0, then 31=ab+ac+bc≥a(a+1)+a(a+2)+(a+1)(a+2)=3a2+6a+2, so a≤2.

If a=1, then c>b>1, and (b+1)(c+1)=32. We have 3≤b+1<32−−√ so b+1=4,c+1=8 and (a,b,c)=(1,3,7).

If a=2, then c>b>2 and (b+2)(c+2)=35. We have 5≤b+2<35−−√ so b+2=5,c+2=7 and (a,b,c)=(2,3,5).

Case 2: ab+ac+bc−31<0, then abc≤|ab+ac+bc−31|=31−ab−ac−bc.

If a≥2, then b≥3,c≥4, so 31≥abc+ab+ac+bc≥2(3)(4)+2(3)+2(4)+3(4)>31, a contradiction. Thus a=1, so c>b>1 and 2bc+b+c≤31.

If b≥3, then c≥4, so 31≥2bc+b+c≥2(3)(4)+(3)+(4)=31, so equality holds and we have (a,b,c)=(1,3,4). Checking, this works.

Otherwise b=2, so 5c≤29, giving c=3,4,5. However we also have c∣ab−31=−29, so this gives no solution.

Case 3: ab+ac+bc−31>0, then abc≤ab+ac+bc−31.

If a≥3, then abc≥3bc≥ab+ac+bc>ab+ac+bc−31≥abc, a contradiction.

Thus a=1,2. If a=2, then c>b>2 and 2bc≤2b+2c+bc−31, so bc+31≤2b+2c, so (b−2)(c−2)+27≤0, a contradiction.

Thus a=1, so bc≤b+c+bc−31, so b+c≥31. Also bc∣(b+c+bc−31), so bc∣(b+c−31). If b+c=31, we have (a,b,c)=(1,2,29),(1,3,28),…,(1,15,16). Otherwise bc≤b+c−31, so (b−1)(c−1)+30≤0, a contradiction.

To conclude, the solutions are (1,3,7),(2,3,5),(1,3,4),(1,2,29),(1,3,28),…,(1,15,16)

hence solutions is 17

a,b,c all divide ab+ac+bc−31 , so since they are pairwise coprime, abc∣(ab+ac+bc−31)

Note that the question can be split into 3 cases where ab+ac+bc−31 is =0,<0,>0.

Case 1: ab+ac+bc−31=0, then 31=ab+ac+bc≥a(a+1)+a(a+2)+(a+1)(a+2)=3a^2+6a+2, so a≤2. If a=1, then c>b>1, and (b+1)(c+1)=32. We have 3≤b+1< √32 so b+1=4,c+1=8 and (a,b,c)=(1,3,7).

If a=2, then c>b>2 and (b+2)(c+2)=35. We have 5≤b+2<√35 so b+2=5,c+2=7 and (a,b,c)=(2,3,5).

Case 2: ab+ac+bc−31<0, then abc≤|ab+ac+bc−31|=31−ab−ac−bc. If a≥2, then b≥3,c≥4, so 31≥abc+ab+ac+bc≥2(3)(4)+2(3)+2(4)+3(4)>31, a contradiction.

Thus a=1, so c>b>1and 2bc+b+c≤31.

If b≥3, then c≥4, so 31≥2bc+b+c≥2(3)(4)+(3)+(4)=31, so equality holds and we have (a,b,c)=(1,3,4).

Otherwise b=2, so 5c≤29, giving c=3,4,5. However we also have c∣ab−31=−29, so this gives no solution.

Case 3: ab+ac+bc−31>0 , then abc≤ab+ac+bc−31. If a≥3, then abc≥3bc≥ab+ac+bc>ab+ac+bc−31≥abc, a contradiction. Thus a=1,2.

If a=2, then c>b>2 and 2bc≤2b+2c+bc−31, so bc+31≤2b+2c, so (b−2)(c−2)+27≤0, a contradiction.

Thus a=1 , so bc≤b+c+bc−31 , so b+c≥31. Also bc∣(b+c+bc−31), so bc∣(b+c−31). If b+c=31, we have (a,b,c)=(1,2,29),(1,3,28),…,(1,15,16) .

Otherwise bc≤b+c−31 , so (b−1)(c−1)+30≤0, a contradiction.

To conclude, the solutions are (1,3,7),(2,3,5),(1,3,4),(1,2,29),(1,3,28),…,(1,15,16). There are a total of 17 solutions.

a|bc−31 means a divide bc-31 , also a divide ac and ab. therefor a divide ab+bc+ca-31 i.e. a|(ab+bc+ca-31) also b|(ab+bc+ca-31) and c|(ab+bc+ca-31)

now since a,b,c are coprime positive integers

we have (a b c)|(ab+bc+ca-31)

therefor abc<=|(ab+bc+ca-31)| where || is mode function

case 1) let ab+ac+bc−31>0 then abc≤ab+ac+bc−31

If a≥3, then abc≥3bc≥ab+ac+bc>ab+ac+bc−31≥abc, a contradiction.

Thus a=1,2. If a=2, then c>b>2 and 2bc≤2b+2c+bc−31, so bc+31≤2b+2c, so (b−2)(c−2)+27≤0, a contradiction.

Thus a=1, so bc≤b+c+bc−31, so b+c≥31. Also bc∣(b+c+bc−31), so bc∣(b+c−31).

If b+c=31, we have (a,b,c)=(1,2,29),(1,3,28),(1,4,27),(1,5,26),(1,6,25),(1,7,24),(1,8,23),(1,9,22),(1,10,21),(1,11,20),(1,12,19),(1,13,18),(1,14,17),(1,15,16)

Otherwise bc≤b+c−31, so (b−1)(c−1)+30≤0, a contradiction.

Case 2) ab+ac+bc−31=0, then 31=ab+ac+bc≥a(a+1)+a(a+2)+(a+1)(a+2)=3a2+6a+2, so a≤2.

If a=1, then c>b>1, and (b+1)(c+1)=32. We have 3≤b+1<√32 so b+1=4,c+1=8 and (a,b,c)=(1,3,7).

If a=2, then c>b>2 and (b+2)(c+2)=35. We have 5≤b+2<√35 so b+2=5,c+2=7 and (a,b,c)=(2,3,5).

Case 3) ab+ac+bc−31<0, then abc≤|ab+ac+bc−31|=31−ab−ac−bc.

If a≥2, then b≥3,c≥4, so 31≥abc+ab+ac+bc≥2(3)(4)+2(3)+2(4)+3(4)>31, a contradiction. Thus a=1, so c>b>1 and 2bc+b+c≤31.

If b≥3, then c≥4, so 31≥2bc+b+c≥2(3)(4)+(3)+(4)=31, so equality holds and we have (a,b,c)=(1,3,4). Checking, this works.

Otherwise b=2, so 5c≤29, giving c=3,4,5. However we also have c∣ab−31=−29, so this gives no solution.

the solutions are (1,3,7),(2,3,5),(1,3,4),(1,2,29),(1,3,28),(1,4,27),(1,5,26),(1,6,25),(1,7,24),(1,8,23),(1,9,22),(1,10,21),(1,11,20),(1,12,19),(1,13,18),(1,14,17),(1,15,16)