gcd(ab+1,bc+1,ca+1)

[jordan]

Siano $a,b,c$ tre interi non negativi e distinti. Dimostrare che $\displaystyle \text{gcd}(ab+1,bc+1,ca+1)\le \frac{a+b+c}{3}$.

[kalu]

Sia $ d=(ab+1, bc+1, ca+1) $. Se $ d=1 $ la tesi è banale, dato che $ a+b+c \geq3 $. Supponiamo ora $ d>1 $.
Dato che $ d \mid ab+1 $ e $ d \mid ca+1 $, $ d \mid (b-c)a $. Ma se $ d \mid ab+1 $ e $ d>1 $, $ d \nmid a $: quindi $ b \equiv c $ (mod $ d $). Ripetendo lo stesso ragionamento possiamo dimostrare che $ a $, $ b $ e $ c $ sono tutti tra loro congrui in modulo $ d $, perciò possiamo porre $ a=xd+\alpha $, $ b=yd+\alpha $ e $ c=zd+\alpha $, con $ x $, $ y $, $ z $ interi non negativi (distinti) e $ 0<\alpha<d $. Quindi $ \displaystyle \frac{a+b+c}{3}=\frac{(x+y+z)d+3\alpha}{3}\geq d+\alpha>d $.

[jordan]

Va bene
Se non ricordo male l'ho letta da una competizione russa, ma non ricordo anno/livello etc..

[Tess]

Tempo fa avevo visto un problema molto simile, perché usava sempre quelle 3 quantità, ma era un po' più difficile, chiedeva:
$ (ab+1)(bc+1)(ca+1) $ quadrato $ \Leftrightarrow $ $ ab+1,bc+1,ca+1 $ tutti e 3 quadrati.

[jordan]

Tempo fa avevo visto un problema molto simile, perché usava sempre quelle 3 quantità, ma era un po' più difficile, chiedeva:
$ (ab+1)(bc+1)(ca+1) $ quadrato $ \Leftrightarrow $ $ ab+1,bc+1,ca+1 $ tutti e 3 quadrati.

Se non ricordo male e' il primo problema del PEN, e ti assicuro che la soluzione fa abbastanza schifo e non c'entra niente con questo

[ma_go]

Ma se $ d \mid ab+1 $ e $ d>1 $, $ d \nmid a $: quindi $ b \equiv c $ (mod $ d $).

questa riga mi piace molto poco.

[kalu]

kalu ha scritto:
Ma se d∣ab+1 e d>1, d∤a: quindi b≡c (mod d).

questa riga mi piace molto poco.

E allora riformulo. $ ab \equiv -1 \not\equiv 0 $ (mod $ d $), da cui $ a \not\equiv 0 $ (mod $ d $). Va bene?

[Sonner]

Più che $d \nmid a$ serve $(a,d)=1$, che però hai implicitamente dimostrato, basta dirlo

[ma_go]

E allora riformulo. $ ab \equiv -1 \not\equiv 0 \pmod d $, da cui $ a \not\equiv 0 \pmod d $. Va bene?

no, non va ancora bene. quindi è un errore, non una svista.

[kalu]

Più che $ d $∤$ a $ serve ($ a, d $)=1

Giustissimo. Ma_go, è questo l'errore di cui parli? Se sì, riformulo ancora.
$ d \mid (b-c)a $. Se un divisore primo di $ d $ dividesse $ a $, non potrebbe dividere $ ab+1 $: assurdo dal momento che $ ab+1 $ è multiplo di $ d $. Quindi $ b \equiv c $ (mod $ d $)
I'm sorry (soprattutto se è ancora sbagliato)

[ma_go]

ma_go, è questo l'errore di cui parli?

sì, è precisamente questo. adesso va bene. però ti lascio un (utile) esercizietto: riformula lo stesso argomento in termini di congruenze.