Home

MPSI/PCSI

Révisions Maths lycée

Arithmétique Maths expertes

Divisibilité et Congruences

Ce cours traite d'un problème d'arithmétique intéressant qui commence avec une fraction, ce qui est inhabituel car on préfère travailler avec des entiers. On définit A_n comme étant une suite. On effectue quelques calculs pour trouver A2 et A3. Ensuite, on cherche à démontrer que A_n+1 peut s'écrire de manière récurrente. On effectue des calculs et constatons que cela est vrai. Ensuite, on démontre que A_n appartient à N (l'ensemble des entiers naturels) en utilisant une récurrence triviale. La question 4 aborde le calcul du PGCD de A_n et A_n+1 et montre qu'il est égal à 1 ou à 3. Enfin, on vérifie que A0 est congru à 1 modulo 3 et on conclut que A_n n'est jamais divisible par 3. On déduit ainsi que le PGCD est égal à 1. Cette approche permet d'obtenir une solution efficace à l'exercice.

Un problème, cette fois-ci, donc quelque chose d'un peu plus long, avec plusieurs questions autour de l'arithmétique, et qui est intéressant parce qu'il commence avec une fraction. Ce qui est un peu bizarre, parce qu'on n'aime pas les fractions d'arithmétique, on veut que des entiers. Assez vite, on va montrer qu'A n est un entier, bien sûr, on le sent venir. On regarde, donc A n est défini comme ce truc-là. Si on regarde, c'est un peu une suite, première remarque, un peu préliminaire, toujours intéressant d'en faire. C'est un petit peu une suite, et donc on se dit, attends, est-ce que ça va être une galère ? En fait, elle est donnée de manière explicite, donc ça c'est plutôt sympa. Calculer A2 et A3. Bon, ok, j'ai A n, alors déjà, premier travail préliminaire encore une fois. Remarque préliminaire dans la question 0, c'est explicite. J'ai fait un travail préliminaire en plus, parce que je n'aime pas les puissances compliquées. J'aime bien s'arrêter sur ça et obtenir juste quelque chose puissance n. C'est un réflexe aussi que j'ai en général de calcul mental, on ne sait jamais. Donc là, je sépare d'abord le 1, je mets le 4 devant, il reste 4 puissance 2 n. Bon, ça fait 4 puissance 2 puissance n, ça me fait 16 puissance n. Est-ce que ce sera utile ou inutile ? L'avenir nous le dira, mais je pense que si vous avez ce genre de réflexe, ça prend, à force d'avoir l'habitude, ça vous prend 30 secondes au début. Et souvent, c'est un bon investissement. Donc faites-le, je vous le conseille. Donc, calculer A2 et A3, on le fait, c'est un peu lourd. Bon, c'est du calcul, là je l'ai fait en mode calcul mental. Honnêtement, prenez la calculette si elle n'est pas interdite. On trouve deux réponses. Très bien. Démontrer qu'on a A n plus 1 qui s'écrit comme ça. Ça, c'est incroyable. C'est-à-dire qu'on a un truc explicite, mais on vous dit non, non, on va trouver plutôt une relation de récurrence. Bon, alors on va essayer de regarder ça. La technique un peu sioux, un peu mec qui ne veut pas s'embêter, c'est de calculer ça et de se rendre compte que ça vaut A n plus 1. On remarque que quoi ? Grâce à ma super intro. Toujours un bon investissement, je vous le dis, dans ce genre de calcul. Pas toujours, mais très souvent. Oh, il y a un 16 ! Le 16, il va bien se goupiller avec ça. C'est parti. Donc, est-ce que ça, c'est vrai ? Bon, je calcule 16 A n moins 3. Ça fait 16 fois mon expression en fonction de 16. Le 16, je le mets là et je le mets là. Je le distribue. Ça fait 4 fois 16 plus A n plus 1 plus 16 moins 15 5e. Le 3, il devient 15 sur 5. Comme par hasard, ça fait 1. C'est A n plus 1. C'est fini. Ça va très vite. Ça peut être beaucoup plus lent. Peut-être que vous l'avez fait en galérant un peu plus. Ça peut aller très vite si vous faites les bons choix au début. Démontrer que A n appartient à N. J'ai envie d'accélérer un peu la vidéo. Vous avez ça, une relation de récurrence. Vous savez que A0, A1, A2, A3, vous avez tout ce qu'il faut pour l'initialisation. Vous avez en gros des entiers. Bien sûr que par une récurrence triviale, je me permets le mot, ça va marcher. En fait, je l'ai quand même faite, mais voilà. Initialisation A0 égale 1, ça appartient à N. Hérédité, est-ce que A n appartient à N ? Si A n appartient à N, est-ce que A n plus 1 aussi ? Oui, parce que A n plus 1 s'écrit comme ça. Donc bon, facile. Comme A n est toujours plus grand que 1, ça c'est bien positif. Donc A n plus 1 est bien dans N, pas dans Z. Et donc c'est bon. On est OK. Ce qui est un peu intéressant, c'est la question 4. Donc là, je ne vais pas vous faire une vidéo qui traîne sur les questions faciles. La question 4. Pour toute aide en note, DN le PGCD de A n et A n plus 1. Montrez qu'il est égal à 1 ou à 3. Là, on se dit, oh, quel enfer ! J'ai une expression qui est moche et tout. Surtout pas ! On a fait la question 2. Question 2, on a une relation de récurrence. On utilise ça tout de suite. Et on écrit. Donc là, il faut être... Je vais parler un peu à l'anglophone. Il faut être aware de l'énoncé, de ce que vous avez fait. Il faut être conscient de ce qui a été fait. Si vous les passez un peu de manière subie, si vous subissez l'exercice plutôt que de comprendre et d'avoir un peu une vision globale de ce qui se passe, vous allez être perdu. Avec la vision globale, c'est-à-dire, je pose les choses au début, j'investis, je simplifie un peu l'expression juste pour mon plaisir. Ça me servira peut-être. Plus le fait de bien comprendre ce qu'on a fait, ce qu'on a démontré jusqu'à là, alors ça va super vite. C'est ça, en fait, qui peut distinguer une très rapide et une copie un peu moins bonne. C'est la lenteur due au manque d'efficacité. Donc, forcément, PGCD de ces deux-là, je remplace tout de suite AN plus 1 par ça, et là, j'utilise les propriétés du PGCD, en fait. De A et B, je peux enlever autant de paquets de A que je veux. Là, j'ai 16 paquets de AN, je les dégage tous. J'ai le droit de faire ça. Donc, DN, c'est le PGCD de AN et moins 3. Donc, forcément, DN, il divise moins 3. Donc, il doit diviser, vu que DN va être positif, vu que AN et AN plus 1 sont des noms positifs, DN doit faire partie des diviseurs positifs de moins 3. Donc, c'est 1 ou 3. Ça va vite. Ça peut aller très lentement, ça peut aller très vite si vous êtes à droit. Petit B, montrer qu'AN plus 1 est toujours congru à AN. Super simple, modulo 3. AN plus 1 est congru à 16 AN moins 3. Là, on va voir votre technicité avec les congruences, c'est ça qui va compter. Vous pouvez virer le 3. C'est un paquet de 3 en moins, il reste 16 AN. 16 AN, là-dedans, il y en a 15. 15, c'est un paquet de 3. Donc, on peut écrire 16 AN comme 15 AN. Bonne astuce à bien retenir. J'ai mis un petit cœur ici parce que, des fois, avec les congruences, je n'ai pas trop osé faire ce genre de truc. Diviser 16 AN en 15 AN plus AN pour avoir 15 AN qui est un paquet de 3. Voilà, c'est utile, ça dégage, il ne reste plus qu'AN. Ça va vite. Petit C, vérifier que A0 est congru à 1 modulo 3. Facile, A0 ça vaut 1, c'est bien congru à 1 modulo 3. En déduire que pour toute N, AN n'est pas divisible par 3. J'ai avec la question B le fait que tous les AN sont congrus entre eux jusqu'à A0. Forcément, tous les AN sont congrus à A0, sont congrus à 1, ils ne sont jamais divisibles par 3. Conclusion, comme 3 ne divise jamais AN, il n'est pas possible que DNPGCD soit égal à 3. Il est donc égal à 1. Et voilà, c'était ma manière de porter un exercice un peu long, un problème en 5 minutes, en vous montrant qu'on avait une efficacité qui peut être appliquée. Il est possible de le faire en 15 minutes en galérant avec la formule explicite. Il faut bien comprendre qu'il y a la question de vous aider et que c'est ça qui vous fait aller vite. Sur ce, je prends vos questions dans les commentaires et je vous dis à la prochaine pour une prochaine vidéo. Bye bye!

Problème : Suite et PGCD !

RELATED

Recommended videos

Division euclidienne

CAPITAL : Reste de 145²⁰²² par 7 ?

Divisibilité et fraction