A nice DIVISIBILITY problem //

Since ALINA wished me "Have a good trip ! ... Take care on the road !" as I wished (see the editorial of Friday, July 3rd, evening), I can also focus a little on the other beauty, mathematics.

           From the Exercise Supplement today (page 8).

"S:E26.162.  Let  $a$  and  $b $ be two nonzero natural numbers. Show that the

                          statements :

a)  $a\;\;  divides  \;\;b^2+1\;\;\;and\;\;\;b\;\;divides\;\;a^2+1,$

b)  $ab\;\;divides\;\;a^2+b^2+1.$ 

                         are equivalent. 

{Authors : }  Romanța GHIȚĂ and Ioan GHIȚĂ, Blaj"

ANSWER CiP

An example is  $5\mid 13^2+1\;\;and\;\;13\mid 5^2+1\;\;\;\Leftrightarrow\;\;65\mid 5^2+13^2+1$

                    Solution CiP

                    $\underline{a)\;\Rightarrow\;b)}$

               We have the hypothesis that 

$a\mid b^2+1 \tag{1}$

and

$b\mid a^2+1 \tag{2}$

are both true.

      If  $\fbox{$a=b$}$ , then  $a\mid a^2+1$  is only possible when  $a=1$. Then, obviously

$ab=1\mid 1^2+1^2+1$  therefore  b)  takes place.

      The case  $\fbox{$a\neq b$}$  still remains to be discussed. First, under the given conditions it follows that the greatest common divisor of  $a$  and  $b$  is 1 :

$(a,b)=1 \tag{3}$

If  $d=(a,b)$ , then

$a=da_1\;\;,\;\;b=db_1\;\;\;,\;\;(a_1,b_1)=1 \;\;.\tag{4}$

$(1)\Rightarrow da_1\mid d^2(a_1^2+b_1^2)+1$ , so  $d\mid 1$

and  (3) is true.

       From  (1)  and  (2)  we have, for certain natural numbers  $m\; and\; n$ :

$b^2+1=ma\;\;,\;\;a^2+1=nb \tag{5}$

Hence  

$mab=b^3+b\;\;\;,\;\;\;nab=a^3+a \tag{6}$ 

 and subtracting the two relations

$(n-m)ab=a^3+a-b^3-b=(a^3-b^3)+(a-b)$

therefore  $(n-m)ab=(a-b)(a^2+ab+b^2+1)$ . If  $n-m\neq 0$  then

$ab \mid (a-b)(a^2+ab+b^2+1)$

and because  $gcd(ab,a-b)=1$

 (a prime number $p$ that would divides  $gcd(ab,a-b)$ would satisfy  $p\mid a\;or\;p\mid b\;\;and\;\;p\mid (a-b)$; but then  $p\mid a\;and\;p\mid b$  which is impossible)

we obtain  $ab\mid (a^2+ab+b^2+1)$  so  $ab\mid a^2+b^2+1$.

If  $n-m=0$ then from  (6)

$b^3+b=mab=nab=a^3+a$

hence  $(a^2+ab+b^2+1)(a-b)=0$  so  $a-b=0$  what is not the case.

$\square$

                    $\underline{b)\;\Rightarrow\;a)}$

          Let's assume :

$ab \mid a^2+b^2+1 \tag{7}$

We have 

$(7)\Rightarrow a\mid (a^2+b^2+1)$  and hence  $a\mid b^2+1$.

Then

$(7)\Rightarrow b\mid (a^2+b^2+1$  and hence  $b\mid a^2+1$.

So both  (1)  and  (2)  are true.

$\square\;\;\square$