Functie in doua variabile

[Vlad Matei]

Aratati ca exista o functie unica \( f:\mathbf{N^{*} \times N^{*}}\rightarrow \mathbf{N^{*}} \) cu urmatoarele proprietati:
1)\( f(x,y)=f(y,x) \)
2)\( f(x,x)=x \)
3)\( (y-x) f(x,y)=y f(x,y-x) \) pentru \( y>x \).

Stelele Matematicii 2007

[Marius Mainea]

Aratam ca f(x,y)=[x,y] (cel mai mic multiplu comun).

Inductie dupa n. P(n): "f(n,k)=[n,k], pentru orice k>0.''

1) Verificare. P(1): f(1,k)=k, k>0 (exercitiu) (inductie dupa k)

2) Pasul de inductie. Putem presupune ca n<k (altfel aplicam inductia si f(x,y)=f(y,x))

i) Daca n divide k atunci k=mn si \( f(n,mn)=\frac{mn}{(m-1)n}f(n,(m-1)n)=...=\frac{mn}{n}f(n,n)=mn. \)

ii) Daca k=mn+r, 0<r<n, atunci \( f(n,mn+r)= \) ... \( =\frac{mn+r}{r}f(n,r) \) si din ipoteza de inductie (f(n,r)=f(r,n)=[r,n]=rn(rn)) avem

\( f(n,mn+r)=\frac{mn+r}{r}\cdot n\cdot r\cdot (n,r) =(mn+r)\cdot n\cdo (n,mn+r)=[n,mn+r]=[n,k]. \)