Division euclidienne

lettres de l'alphabet). En voici le codage : Soit Nc le numéro du caractère choisi (compris entre 1 et 26) et X celui du caractère codé. On a alors 2 cas possibles : Si Nc13 alors X=Nc+13-26 La fonction qui à Nc associe Nc', le reste de la division euclidienne de Nc+12 par 26 est appelée Modulo. En langage informatique on note ici cette fonction modulo : X=(Nc+12)%26+1 Le fait que le même algorithme soit appliqué aux données pour le chiffrement et le déchiffrement, et sa simplicité (relative), nous

est divisible par (X − a)k et pas par (X − a)k+1 ). a est racine de P d’ordre au moins k si et seulement si il existe un polynôme Q tel que P = (X − a)k Q (si et seulement si P est divisible par (X − a)k ). k−1 Théorème. Le reste de la division euclidienne de P par (X − a)k est i=0 P(i) (a) (X − a)i . i! Théorème (caractérisation de l’ordre de multiplicité). a est racine de P d’ordre k si et seulement si P(a) = P ′ (a) = . . . = P(k−1) (a) = 0 et P(k) (a) = 0. a est racine de P d’ordre

que Im ⊆ [−3, 2] ; 5. Existe-il m tel que Im ∩ [−3, 2] = ∅. Exercice 5 : [ 6 points] Soit le polynˆme : o P (x) = x5 − x4 − 9x3 + 13x2 + 8x − 12. 1. Calculer P (−1) et P (1), puis conclure ; 2. D´terminer Q(x) le quotient de la division Euclidienne de P (x) par (x2 − 1) ; e e e e e 3. V´rifier que 2 est racine de Q(x), puis factoriser Q(x) via la m´thode des coefficients ind´termin´s ; 4. En d´duire une factorisation en ´l´ments simples de P (x). e ee Bonne Chance 

est, alors, le dernier résultat non nul.  ExempleDéterminer le PGCD des nombres 12 et 2828 – 12 = 1616 – 12 = 412 – 4 = 88 – 4 = 44 – 4 = 0Le dernier résultat, non, nul est 4, donc PGCD(12 ; 28) = 4  Algorithme d'Euclide   On effectue la division euclidienne du plus grand nombre par le plus petit et on recommence avec le diviseur et le reste, jusqu'à ce que le reste soit nul. Le PGCD, est, alors, le dernier diviseur.  ExempleDéterminer le PGCD de 360 et 128Le dernier diviseur, non nul, est 8,

un multiple de 5.  On a   . Cette dernière expression montre que la relation est vraie au rang .  Le principe de récurrence permet de conclure.      2ème méthode : les congruences  On étudie les valeurs possibles pour le reste dans la division euclidienne de  par 5.  Si   Si  donc   Si  donc   Si  donc   Si  donc   La conclusion est immédiate.      3ème méthode : factorisation de     Si  alors   Si  alors  alors   Si  alors  alors   Si  alors  alors   La conclusion en découle

Déclaration d’une variable du type entier : Var noteCtrl :entier Affectation de la variable noteCtrl : noteCtrl15 noteCtrl6 Opérations permises sur les entiers : Addition + Soustraction – Multiplication * Division euclidienne / partie entière : div et reste de la division appelé modulo : mod Exemple : Var x,y,z :entier x11div2 ; //x vaut 5 x11mod2 ; //x vaut 1 y3/10 ; //Attention y vaut 0 12.Le type Réel Déclaration du type réel : Var noteCtrl,pi :réel Affectation

communs puis de déterminer lequel est le plus grand. Cette méthode n’est pas viable pour les nombres complexes. 2ème méthode C’est l’algorithme d’Euclide. Il faut que a > b On fait la division euclidienne de a par b. On obtient le reste r si r = 0 alors le PGCD est b si r ≠ 0 alors on fait la division de b par r On continue de même jusqu’à obtenir un reste nul. Le PGCD est alors le dernier reste non nul Pour trouver le PGCD de 759 et 552 : III. NOMBRES PREMIERS ENTRE EUX Définition

diviseurs communs puis de déterminer lequel est le plus grand. Cette méthode n’est pas viable pour les nombres complexes. 2ème méthode C’est l’algorithme d’Euclide. Il faut que a > b On fait la division euclidienne de a par b. On obtient le reste r si r = 0 alors le PGCD est b si r ≠ 0 alors on fait la division de b par r On continue de même jusqu’à obtenir un reste nul. Le PGCD est alors le dernier reste non nul Pour trouver le PGCD de 759 et 552 : III. NOMBRES PREMIERS ENTRE EUX Définition Deux

ou « n'est pas divisible » a) 5428720147256 ………………………………………….par 3 b) 9012582568748 ……………………………………….par 8 c) 5851472024601……………………………………… .par 25 d) 8521404125417 ………………………………… …par 11 2°/ L’égalité a = bq + r avec 0 ≤ r  b désigne la division euclidienne de a par b, compléter le tableau suivant : a 327 294 180 b 23 150 18 q 6 r 48 3 PGCD(a,b) 3°/ Déterminer les chiffres x et y pour que la condition indiquée soit vérifiée. a) 3871x25 soit divisible par 9

[X ] factor(expr) factor(expr, Touches b32 var) Touches b3A2 Factorisation dans le corps cFactor(expr) des complexes ou cFactor(expr, var) PGCD de deux polynômes polyGcd(poly1, poly2) Touches b363 Quotient et reste dans la division euclidienne de deux polynômes polyQuotient(poly1, poly2) poly2) Touches b362 Touches b361 polyRemainder(poly1, © T³ France 2008 / Photocopie autorisée 8 Journées d’Été 2008 Racines d'un polynôme Racines dans le corps des complexes