Criterio di divisibilità

[ficus2002]

Sia $b_1, b_2$ due numeri naturali e sia $d$ il loro massimo comun divisore. Sia $a$ un numero naturale e siano $q_1,q_2$ naturali tali che $a=b_1 q_1+b_2 q_2$. Allora $b_1+b_2|a$ se e solo se $(b_1+b_2)/d|(q_2-q_1)$.

[TomSawyer1]

Forse la faccio troppo semplice. Consideriamo i due numeri coprimi $b_1/d,b_2/d$. Allora esistono $r_1,r_2$ tali che $1=b_1/d r_1 + b_2/d r_2$. Moltiplicando tutto per $a$, si ha $a=b_1 a/d r_1+b_2 a/d r_2$. Avendo trovato una soluzione specifica, ora tutte le altre soluzioni di $a=b_1q_1+b_2q_2$ sono $(a/d r_1 +tb_2/d,a/d r_2 -tb_1/d)$. Quindi $q_2-q_1=(a(r_2-r_1)-t(b_1+b_2))/d$, con $t$ intero. E la tesi sarebbe immediata.

[ficus2002]

"TomSawyer":Forse la faccio troppo semplice. Consideriamo i due numeri coprimi $b_1/d,b_2/d$. Allora esistono $r_1,r_2$ tali che $1=b_1/d r_1 + b_2/d r_2$. Moltiplicando tutto per $a$, si ha $a=b_1 a/d r_1+b_2 a/d r_2$. Avendo trovato una soluzione specifica, ora tutte le altre soluzioni di $a=b_1q_1+b_2q_2$ sono $(a/d r_1 +tb_2/d,a/d r_2 -tb_1/d)$. Quindi $q_2-q_1=(a(r_2-r_1)-t(b_1+b_2))/d$, con $t$ intero. E la tesi sarebbe immediata.

Ok. E' ancora più semplice se osservi che tutte e sole le combinazioni lineari interi di $b_1$ e $b_2$ che danno $a$ sono del tipo $a=b_1 (q_1 + b_2/d t) + b_2 (q_2 - b_1/d t)$. Così, $b_1 + b_2|a$ se e solo se $q_1 + b_2/d t = q_2 - b_1/d t$ per qualche $t \in ZZ$.