0
$\begingroup$

(a) Find $3$ different natural numbers, relatively prime in pairs, such that the sum of any two is divisible by the third.
(b) Find $3$ different natural numbers such that the product of any two leaves a remainder of $1$ upon division by the third.

(a) If try to do by algebraic reasoning, then unable to find the representation of the different naturals that are relatively prime in pairs. Any way to represent $3$ relatively prime pairs seems impossible. Then what is left is a finding of all such pairs for naturals in increasing order.

(b) Again need a proper approach that is not guess-work.


Note In face of answers and other sources, have edited my answer as below:

(a) First, need to represent using the Bezout's lemma the pairwise relatively prime pairs. Say,
$\exists l,m,n,o,p,q,r,s,t, \in \mathbb{Z}$ s.t.
(i)$la+mb=1,$
(ii) $ob+pc=1,$
(iii)$ ra+sb=1$.

To show divisibility for the sum of any two by the third natural, requires following algebraic reasoning:
$\exists x,y,z \in \mathbb{N}$, s.t.
(iv)$a+b = xc \implies c = \frac{(a+b)}{x}$,
(v)$ b+c = ya\implies a = \frac{(c+b)}{y}$,
(vi)$a+c=zb\implies b = \frac{(a+c)}{z}$.

It seems that it is not easy to combine such two different algebraic representations.

$\endgroup$
  • $\begingroup$ I do not want a find the number approach, I request an algebraic reasoning. $\endgroup$ – jitender Feb 4 '18 at 1:43
  • $\begingroup$ Why? You are dealing with numbers, after all, so a "number approach" seems quite fitting here. $\endgroup$ – Matthew Conroy Feb 4 '18 at 1:44
  • $\begingroup$ But, it troubles me too much not to have logic involved. The way it goes by number finding, it enters more into the realm of algorithms, and then it is concerned how to get the different values of the $3$ variables. $\endgroup$ – jitender Feb 4 '18 at 1:48
2
$\begingroup$

Question (a): Hint: the following triples $(a,b,c)$ are solutions: $$ a=1, \qquad b=1, \qquad c=1; $$ $$ a=1, \qquad b=1, \qquad c=2; $$ $$ a=1, \qquad b=2, \qquad c=3. $$ (Every permutation of each of the above is a solution as well. The requirement that $a,b,c$ should be different leaves only the latter triple, i.e. any permutation of $1,2,3$.)

Now let us prove that there are no other solutions. (See also the last page of this problem set.)

Proof. Let $a<b<c$. Then $a+b<2c$. But $c$ must divide $a+b$, therefore $c=a+b$.

So we have $b\ | \ (a+c)$; that is $b\ | \ (2a+b)$. Therefore $b\ | \ (2a)$. But $2b>2a$, so in order for $b\ | \ (2a)$ we must have $b=2a$. We have thus found that $$ b=2a, \qquad c=a+b=3a. $$ Therefore any triple $(a,2a,3a), \ a\in{\mathbb N},$ is a solution (not necessarily coprime!) -- and no other triple would work. The positive integers $(a,2a,3a)$ have a common divisor $a$; these integers are coprime if and only if $a=1$. We have thus proved that the only coprime solution is $(a,2a,3a)$ with $a=1$, that is, $(1,2,3)$.

$\endgroup$
  • 1
    $\begingroup$ For a full solution to a very similar problem, see the last page of this problem set. $\endgroup$ – Alex Feb 4 '18 at 3:24
  • 1
    $\begingroup$ The linked solution begins like this: Let $a<b<c$. Then $a+b<2c$ - but $c$ must divide $a+b$, therefore $c=a+b$. Is it clear up to this point? $\endgroup$ – Alex Feb 4 '18 at 3:43
  • 1
    $\begingroup$ The linked solution proves that $(a,b,c)=(k,2k,3k), \ k\in{\mathbb N}$. Now it remains to prove that the positive integers $k,2k,3k$ are coprime if and only if $k=1$. Indeed if we had $k>1$, then the numbers $k,2k,3k$ would have a common divisor $k$, so they would not be coprime. Thus we must have $k=1$. $\endgroup$ – Alex Feb 4 '18 at 17:48
  • 1
    $\begingroup$ You already have the (linked) proof that no solution other than $(k,2k,3k)$ would work. Then you have my previous comment that you must have $k=1$ in order to have a coprime triple $(k,2k,3k)$. That's it. (Your OP does not give a solution.) $\endgroup$ – Alex Feb 4 '18 at 18:44
  • 1
    $\begingroup$ I only stated that the edited OP does not give a full solution. It is simply a restatement of the problem. $\endgroup$ – Alex Feb 4 '18 at 18:50
1
$\begingroup$

For part (b), suppose $a < b < c$. Then for some integers $l, m$, $ab = lc + 1$ and $ac = mb + 1$. Actually

$$ lm = \frac{ab-1}{c}\frac{ac-1}{b} = a^2 - \frac ac - \frac ab + \frac{1}{bc} $$

So $lm \equiv -1\pmod a$. Observer that $lmbc \equiv 1 \pmod a$, and this implies $a = 2$. The only solution is $a = 2$, $b = 3$, $c = 5$.

$\endgroup$
  • $\begingroup$ $\exists l, m,n \in \mathbb{Z}$, s.t. (i) $ ab = lc+1$, (ii)$ ac = mb+1$,(iii)$ bc = na+1$. Can take 3 pairs, as the one pair taken by you above. $\endgroup$ – jitender Feb 4 '18 at 17:32
  • $\begingroup$ Sorry, the other answer was for far more complex question. Should have posted separately. $\endgroup$ – jitender Feb 4 '18 at 18:04

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.