Agregext composition de mathematiques generales 2007 maths

6Les quatre premieres parties du probleme sont largement independantes.Partie IDans cette partie I, on etudie une methode de calcul de l’inverse d’un element a d’un groupemultiplicatif G de cardinal ni N ∈N . L’element neutre de G est note 1.«Ecrire un algorithme» signi e le rediger en fran cais, sous une forme rappelant un programmed’un langage tel que Pascal, Maple, Matlab, etc.Le coutˆ d’un algorithme est le nombre de multiplications dans le groupe G que necessite sonexecution. On ne tiendra pas compte des autres operations (en particulier celles dansN).N 11. Justi er le fait que a est inverse de a dans G.2. On ecrit la decomposition en base 2 de N 1 sous la forme :kXiN 1 = x 2 avec k ∈N, x ∈{0,1} pour i∈ [[0,k] et x = 0.i i ki=0On considere les suites nies ( a ) et (b ) de nies par :i 06i6k+1 i 06i6k+1x 2ia = 1, b =a et pour i∈ [[0,k]], a =a b , b =b .0 0 i+1 i i+1i ia) Demontrer que a est l’inverse de a dans G.k+11b) En deduire un algorithme de calcul de a et preciser, en fonction de k, son coutˆdans le pire des cas (c’est- a-dire le nombre maximum de multiplications dans G que1necessite le calcul de a ; on ne tiendra pas compte du coutˆ eventuel du calcul desx , 06i6k). L’algorithme doit prendre comme arguments a et N.i3. Exemple. Dans cette question, G est le groupe des elements inversibles deZ/148Z.On note encore a la classe dansZ/148Z d’un element a deZ.a) Determiner le cardinal N de G.b) Demontrer que 5 ...