Tutte le funzioni con gcd(f(a),f(b))=gcd(a,b)

[jordan]

Trovare tutte le funzioni $ f(\cdot):\mathbb{N}_0 \to \mathbb{N}_0 $ tali che per ogni $ (a,b) \in \mathbb{N}_0^2 $ vale $ \gcd(f(a),f(b))=\gcd(a,b) $

[dario2994]

Mi sa che non quadra qualcosa... pongo a=b... si ricava f(a)=a :|

[jordan]

Si, scuse me, avevo dimenticato "per ogni a diverso da b".

[dario2994]

Ritento...
Fisso a=0... si ottiene facilmente che qualsiasi numero divide f(0) quindi f(0)=0.
Fisso b=2a (con b diverso da 0)... si ottiene a|f(a) da cui f(a)=ma per qualche m intero non negativo.
Assumo m diverso da 0,1 per qualche a, pongo b=f(a) da cui si ottiene:
$ $a=ma $
Che ovviamente rivela l'assurdo dato che si era posto m diverso da 1.
Nel caso m=0 pongo b=0:
$ a=gcd(0,0) $
che ovviamente... non è plausibile (l'ovviamente serve per non far capire che non so quanto valga RHS xD... ma che è abbastanza chiaro che non vale proprio a).
Quindi m=1 per ogni a diverso da 0, da cui si ottiene che f(x)=x per ogni intero non negativo... sostituendo viene ovviamente che questo soddisfa.

[fph]

$ a=\gcd(0,0) $
che ovviamente... non è plausibile (l'ovviamente serve per non far capire che non so quanto valga RHS xD...

Al solito puoi definirlo come ti pare, ma il modo più sensato (leggi "che preserva più proprietà") è porlo uguale a 0. Il punto è che quando fai il gcd il "massimo" non andrebbe inteso come massimo in-senso-stretto ma come massimo rispetto all'ordinamento (parziale) definito da "$ a\leq b $ se e solo se a|b", per cui 0 è l'elemento più grande di $ \mathbb N $.

Comunque nota che Jordan, da vecchio volpone, ha posto il problema su $ \mathbb N_0 $, che dovrebbe essere $ \mathbb N $ senza lo 0.

[jordan]

Comunque nota che Jordan, da vecchio volpone, ha posto il problema su $ \mathbb N_0 $, che dovrebbe essere $ \mathbb N $ senza lo 0.

LOL, cmq sci, senza lo 0

[dario2994]

Ma allora sono pirla... io avevo inteso quello 0 al pedice come dire "con lo 0" non il contrario xD
Infatti poi avevo pensato che era più pulito come esercizio senza lo 0...

[fph]

...infatti sarebbe stato meglio se Jordan avesse definito $ \mathbb N_0 $, oppure, come (da vecchi volponi) fanno quelli che scrivono i testi delle gare, scrivere "una funzione dagli interi POSITIVI agli interi POSITIVI".