Arithméttique

[abicah]

Bonjour,

L'exercice:

Trouver toutes les applications f:N*xN* --> N* telles que :

pour tout a et b appartenant à N* :

f(a,a)=a
f(a,b)=f(b,a)
f(a,b)=f(a,a+b)

La solution ;

Montrer : pour tout n de N* ( quelque soit (x,y) appartenant à N*xN*,( x+y=n =>pgcd(x,y)=f(x,y) )) par récurrence forte.

ma solution :

La propriété est vrai au rang n=2 : 1+1=2 =>pgcd(1,1)=1=f(1,1).
Je suppose la propriété vrai pour tout k appartenant à N* inférieur à n
Je n 'arrive pas à démontrer l hérédité :
Soit x,y appartenant à N* tels que x+y =n+1......

Si quelqu'un peut m'aider

Merci

[abicah]

Je pense avoir trouvé (à moins du contraire):

soient x, y appartenant à N* tels que x+y=n+1.

si x=y :
on a pgcd(x,y)=x=f(x,y)

si y>x :

y=x+(y-x)=n+1-x<=n

donc pgcd(x,y)=pgcd(x,y-x)=f(x,y-x)=f(x,(y-x)+x)=f(x,y)

Et on démontre de même le cas x>y

l' hérédité est démontrée


Et la réciproque est triviale :

si f(x,y)=pgcd(x,y)
on a bien pgcd(x,x)=x et pgcd(x,y)=pgcd(y,x)=pgcd(x,x+y)