Home

MPSI/PCSI

Maths

Algèbre

Divisibilité et division euclidienne

Dans cet exercice, on démontre deux résultats arithmétiques. Tout d'abord, pour tout entier n, on montre que 6 divise 5^n + n. En utilisant les congruences, on montre que ce nombre est divisible par 2 et par 3, donc par 6. Ensuite, on démontre que pour tout entier n, 4^(2^n) + 2^(2^n) + 1 est divisible par 7. En examinant les premières valeurs de n, on constate un motif (4, 2, 4, 2...) qui nous permet de généraliser la propriété par récurrence. Finalement, on conclut en affirmant que pour tout entier n, ces deux propriétés sont vérifiées.

Salut ! Dans cet exercice, on va montrer quelques petits résultats arithmétiques. On va montrer que pour toute n appartenant à Z, 6 divise 5 n puissance 3 plus n, et que pour toute n appartenant à N cette fois-ci, 7 divise 4 puissance 2 puissance n, plus 2 puissance 2 puissance n plus 1. C'est parti pour le premier résultat. Pour montrer ça, ce qu'on va montrer, c'est que 5 n puissance 3 plus n est divisible par 2 et par 3. Parce que s'il est divisible par 6, ça veut dire qu'il est divisible par 2 et par 3. Donc on va utiliser les congruences et on va dire qu'il est congru à 0 modulo 2 et congru à 0 modulo 3. Donc on commence par dire que... Donc voilà, c'est ça qu'on va faire, c'est qu'on va montrer que, comme je disais, il est congru à 0 modulo 2 et il est congru à 0 modulo 3. Bon ben, on va faire le premier cas de figure. Il y a deux choix possibles, soit n est paire, soit n est impaire. Il ne peut pas être autre chose que paire ou impaire. Donc on va commencer, si n est paire, alors n est congru à 0 modulo 2, et donc 5 n puissance 3 plus n est congru à 5 fois 0 puissance 3 plus 0, ça fait 0, modulo 2. Et si n est impaire, n est congru à 1 modulo 2, et donc 5 n puissance 3 plus n est congru à 5 fois 1 puissance 3 plus 1, c'est congru à 6 du coup, et donc c'est congru à 0 modulo 2. C'est pratique les congruences pour tout ce qui est divisibilité. Donc finalement, on a bien montré la première propriété, donc ça veut dire qu'il est congru à 0 modulo 2. On va montrer maintenant qu'il est congru à 0 modulo 3. Donc pour ça, on va faire un peu pareil, sauf qu'on ne va pas faire paire et impaire, on va faire tous les cas de figure par rapport à 3. Ça veut dire qu'on va regarder ce qui se passe quand n est congru à 0 modulo 3, à 1 modulo 3 et à 2 modulo 3. C'est les seuls cas de figure qu'on puisse avoir pour un nombre entier, il ne peut être congru qu'à 0, 1 ou 2 modulo 3. Donc on va voir ce qui se passe dans ces trois cas de figure là. Donc si n est congru à 0 modulo 3, même raisonnement que tout à l'heure, 5 fois n puissance 3 plus n, ça fait 0 modulo 3. Si n est congru à 1 modulo 3, alors on retrouve le même résultat que tout à l'heure, mais du coup, on est modulo 3, mais 6, c'est encore congru à 0 modulo 3. Donc finalement, si n est congru à 1 modulo 3, le résultat est congru à 0 modulo 3. Et il reste le cas de figure si n est congru à 2 modulo 3. Donc si n est congru à 2 modulo 3, et bien ici, ça nous fait 5 fois 8, parce que c'est 5 fois 2 puissance 3 plus 2, donc ça fait 5 fois 8 plus 2, ça fait 42. Et bien 42, c'est congru à 0 modulo 3, donc c'est tout bon. Donc finalement, pour toute n, 6 divise 5 fois n puissance 3 plus n. Alors maintenant, on va montrer le deuxième résultat. Donc on va montrer que pour toute n, 4 puissance 2 puissance n plus 2 puissance 2 puissance n plus 1 est congru à 0 modulo 7. Alors ce résultat semble sorti complètement de nulle part. On va voir un peu ce qui se passe, parce qu'a priori, on n'aurait pas trop de pistes à explorer pour le moment, surtout qu'on est modulo 7. Donc on va voir un peu ce qui se passe. On va regarder les premières valeurs de n pour voir est-ce qu'il y a quelque chose qu'on observe, est-ce qu'on aurait une piste par laquelle on peut partir. On va voir un peu ce qui se passe. Donc si on regarde les premières valeurs de n, on va regarder ce que vaut 4 puissance 2 puissance n. Donc 4 puissance 2 puissance 0, ça fait 4 puissance 1, donc ça fait 4, et 4 c'est congru à 4 modulo 7. 4 puissance 2 puissance 1, ça fait 4 puissance 2, et donc ça nous fait 16. 16 c'est congru à 2 modulo 7, parce qu'il y a 14 pas loin, 16 moins 14 ça fait 2. 4 puissance 2 puissance 2, c'est congru à 2 puissance 2, c'est congru à 4 modulo 7. Alors 4 puissance 2 puissance 3, c'est égal à 4 puissance 8 du coup, parce que 2 puissance 3 c'est 8. Ça, 8 on l'écrit comme 2 fois 4, parce que 4 puissance 2, le tout puissance 4, on multiplie les puissances ensemble. Et donc étant donné que 4 puissance 2 c'est congru à 2, ce truc-là est congru à 2 puissance 4, et 2 puissance 4 c'est égal à 16, et 16 c'est congru à 2 modulo 7. On a l'impression, on a une intuition, de voir qu'on a 4, 2, 4, 2, on a l'impression que ça va se répéter, et l'intuition qu'on peut avoir c'est quand le n est paire, ça donne 4, et quand le n est impaire, ça donne 2. Ça c'est une intuition qu'on peut avoir, on va essayer de le montrer, on va essayer de le montrer du goût par récurrence, parce que c'est une propriété qui va dépendre de n, on va montrer ça par récurrence, que du coup, quand k est paire, 4 puissance 2 puissance k est congru à 4 modulo 7, et quand k est impaire, 4 puissance 2 puissance k est congru à 2 modulo 7. On va montrer ça par récurrence. Donc on ne va pas le montrer avec k paire et k impaire, on va généraliser, on va dire que pour tout k positif, la version paire, on l'écrit comme 2k, et la version impaire, on l'écrit comme 2k plus 1. Ça généralise un peu tout ce procédé. Donc récurrence, initialisation pour commencer, si k est égal à 0, donc ici c'est 0, donc on se retrouve avec cette situation-là, et ici ça fait 1, donc on se retrouve avec cette situation-là, on l'a déjà vérifié, du coup l'initialisation est vraie. Ensuite maintenant, le passage de k à k plus 1. Donc là, on va regarder ce qui se passe quand on remplace k par k plus 1. Donc là c'est la version ici, donc 4 puissance 2 puissance 2 fois k plus 1, donc là on développe dans la dernière puissance, ça fait 2k plus 2, on va séparer le 2 qui est ici avec le plus, on va dire que c'est 2 puissance 2k fois 2 puissance 2, et on va séparer maintenant avec le 4, mais vu que c'est une multiplication, ça va être une puissance de puissance. Donc ce morceau-là correspond à ça, et la puissance qui est là correspond à ici avec le fois. Sauf que par hypothèse de récurrence, 4 puissance 2 puissance 2k c'est congru à 4, ça c'est notre hypothèse de récurrence. Donc finalement, 4 puissance 4 c'est 16 puissance 2, donc étant donné que 16 est congru à 2, 16 puissance 2 c'est congru à 2 puissance 2, qui est congru à 4 modulo 7. Et on fait pareil pour le deuxième cas de figure, donc 4 puissance 2 puissance 2 fois k plus 1 plus 1, donc là même principe, le plus 1 qui est ici, on va dire que c'est 2 puissance ce truc-là fois 2, d'accord, ici, donc là le 2 qui est ici est au même rang que celui-ci. Et donc, pareil que tout à l'heure, la multiplication qui est ici, ça va être une puissance de puissance, donc c'est 4 puissance 2 puissance 2k plus 1, le tout au carré, sauf que là on est dans un cas de figure où on a une puissance paire, d'accord, 2 fois k plus 1, c'est une puissance paire, on l'a montré juste ici que c'était vrai, donc ce truc-là on sait qu'il est congru à 4, au carré du coup, et donc congru à 2 modulo 7. Alors de même, on montre très rapidement, donc on peut juste le dire dans ce genre de cas de figure parce que ça va être exactement les mêmes calculs, on montre de même que 2 puissance 2 puissance 2k est congru à 2 modulo 7, et que 2 puissance 2 puissance 2k plus 1 est congru à 4 modulo 7. Donc finalement, si n est paire, donc on reprend les trucs qu'on a fait avec les k et les k plus 1, si n est paire, et bien k puissance 2 puissance n plus 2 puissance 2 puissance n, pardon, plus 1, c'est congru à 4 plus 2 plus 1, d'accord, lui il vaut 4, lui il vaut 2, lui c'est 1, et donc ça, ça fait 7, et si n est impaire, cette fois-ci c'est lui qui est congru à 2, lui qui est congru à 4, lui il vaut toujours 1, et donc ça nous fait 2 plus 4 plus 1, c'est encore congru à 0 modulo 7. Donc finalement on conclut en disant que pour toute n, 4 puissance 2 puissance n plus 2 puissance 2 puissance n plus 1 est congru à 0 modulo 7.

Divisibilité

RELATED

Recommended videos

Carré parfait

Division euclidienne

Nos années

Nos principales matières