Salut !

Pour le critere de divisbilte par 3, c'est assez rapide, il suffit de dire que tt nombre s'ecrit en base 10, ss la forme an*10^n+an-1*10^n-1+...a0 et on a que pour tt n, 10^n congru a 1 modulo 3
dc par propriete des congruences, an*10^n+an-1*10^n-1+...a0 congru a an+an-1+...+a0 modulo 3

Pour l'algo d'Euclide, on ecrit la suite des divisions euclidiennes, a = bq0+r0, b= r0q1+r1....il se termine car la suite (rn) de reste successifs est une suite strictement decroissante minoree par 0 dc elle converge. Et ensuite, il faut itiliser que PGCD'=(a,b)=PGCD(b,r0)=....= PGCD (rn, 0)=rn dc le PGCD est le dernier reste non nul

Pour le division euclidienne tu devrais trouver la demon sur le site de megamaths en lecon d'oral du capes...

a plus

division euclidienne dans N :
tu poses A = {k € N , bk <= a }

tu montres que le q de a = bq + r c'est le max de A voila qui assure l'unicité du couple b,r en cas d'existence et ensuite reciproquement tu poses q = max A et r = a-bq et tu montres que les propriétés sont bien vérifiées  voilà qui en assure l'existence

(du couple q,r dsl !)