Terminale Maths Expertes-Arithmétique et congruence-COURS- la définition

Bonjour à tous ! Alors aujourd'hui, cours sur les congruences à destination de ceux par exemple qui ont été absents ce jour-là, ou qui veulent un petit peu plus de précision. Donc on est sur le début, c'est vraiment la définition et les propriétés immédiates, et on en fera d'autres évidemment pour compléter ce cours, donc qu'est-ce que c'est que la congruence ? Alors tout d'abord la définition, quand est-ce qu'on dit qu'un entier congrue à un autre entier ? Alors déjà vous avez entendu, c'est le mot entier. On est donc ici, on va travailler tout ça dans Z, donc Z c'est l'ensemble des entiers relatifs. Donc vous avez 0, 1, (-1), 2, (-2), et vous avez compris, ça veut dire que Z contient tous les entiers naturels et tous les entiers négatifs. Donc ici, on prend un entier n naturel, donc non nul, donc on ne prend pas 0. On dit que deux entiers relatifs, donc des entiers relatifs, c'est des éléments de Z. Il faut bien comprendre, ça c'est important, donc Z c'est les relatifs. Donc on prend deux entiers relatifs A et B, et on va dire qu'ils sont congrus modulo n, quand ils ont le même reste dans la division Euclidean par n. Et on va écrire A est congrue à B modulo n, ou encore d'autres notations A congrue à B modulo n. Et le congru, on va l'écrire avec une sorte d'égale mais avec trois barres, c'est important, ici il y a trois barres. Ce n'est pas le symbole égal, c'est le symbole de la congruence, donc à chaque fois on met trois barres. Et pour indiquer par quoi on fait la division Euclidean, on écrit soit mod n entre parenthèses, soit len entre crochets, soit len entre parenthèses. Et on lit A est congrue à B modulo n. Il vaut mieux des exemples qu'un non-discours, donc prenons un antinatural non-nu, je vais prendre par exemple n égale à 6. Alors en termes de nom, 6 s'appelle le mode, donc n dans la définition, quand on dit modulo n, n est le mode. Donc il faut toujours un mode non-nu. Maintenant je dois prendre un couple AB, donc je vais prendre A par exemple 23, je vais calculer son reste par division par 6, donc 23 c'est 6 x 3, 18 plus 5, je rappelle que le reste quand on divise 5 doit être positif et doit être strictement plus petit que le diviseur, donc 6. Donc là j'en reste par 5, je dois donc prendre un autre nombre, je dois trouver un autre nombre, par exemple 47. 47 donc 6 x 6, 6 x 7, donc 6 x 7, 42 plus 5, vous voyez que 23 et 47 ont le même reste, donc on peut écrire que 23 est congrue à 47 modulo, alors on va l'écrire d'abord comme ceci. Si on se fatigue, on écrira plutôt comme ceci. On peut aussi l'écrire entre parenthèses, il n'y a pas du tout d'ambiguïté, donc il faut bien mettre ici les trois traits pour bien montrer qu'on est dans des congruences, surtout si vous notez avec des parenthèses parce que là ça pourrait être comme ici un facteur 6. La première remarque qu'on peut faire c'est que c'est symétrique tout ça, parce que si 23 est congrue à 47, c'est qu'ils ont le même reste, donc 47 dans l'autre sens, on peut écrire aussi que 47 est congrue à 23 modulo 6, vous voyez qu'on peut comme ça inverser, ça s'appelle propriété, ça s'appelle la symétrie. C'est donc la première propriété. Si A est congrue à B modulo N, ça équivaut à dire que B est congrue à A modulo N. Alors il n'y a pas que deux nombres qui sont égaux, un congrue modulo 6, ici il y en a d'autres, même 23, 47, on peut en trouver, il suffit ici de prendre un autre, 17 si je prends 17. 17 c'est 2 x 6, 12, donc 6 x 12, plus 5, ça veut dire qu'on a encore le même reste, vous voyez. Tous les nombres qui en restent 5 sont congrues modulo 6, donc 17 est congrue à 47 modulo 6. Alors on évite de mettre comme ça plein de chaînes de congruence, on écrira plutôt à côté 17 est aussi congrue à 23 modulo 6. Alors parfois, quand on rédige, on s'autorisera, mais vraiment, rarement à faire ce genre de choses, quand on a comme ça plein de petits calculs successifs et simples, condition qu'il n'y ait pas d'ambiguïté toujours. Mais en étant rigoureux, on doit toujours avoir deux nombres, comme une équation en fait, avec ici à droite le mod toujours nous. Donc des nombres qui sont congrues à 23 modulo 6, mais il y en a plein, vous avez 23, si vous rajoutez 6, vous aurez 29, vous aurez 35, vous aurez 41, vous aurez 47, tous ces nombres, comme je rajoute 6, ont toujours le même reste, 5. Et donc, ça va nous amener à une autre propriété qui est vraiment fondamentale, que je citerai après, mais tout d'abord, on va regarder un petit peu les cas très particuliers. Par exemple, est-ce que A est congrue à lui-même ? Eh bien oui, 23 et 23 ont bien le même reste, donc une propriété, c'est que A est congrue à A modulo N. Un nombre est toujours congrue à lui-même, quel que soit le mod d'ailleurs, le mod devient toujours non-nul. Il faut savoir qu'en maths, on aime bien donner des noms aux propriétés. Eh bien ça, ça s'appelle la réflexivité. Et ça, ça s'appelle la symétrie. Pour l'instant, vous connaissez d'autres opérations, entre les nombres, en tout cas de relations entre les nombres plutôt, qui ont ces mêmes propriétés. L'égalité, par exemple, A égale B, eh bien ça équivaut à dire que B égale A. On a toujours A égale A, un nombre est toujours égal à lui-même. Voyez, l'égalité, elle est elle-même symétrique et réflexive. Alors attention, tout n'est pas réflexif. Par exemple, si vous prenez strictement, A n'est pas strictement plus petit que les mêmes, ça veut dire que la relation d'ordre ici, stricte, n'est pas réflexive. Elle n'est d'ailleurs pas symétrique non plus, puisque si j'ai ça, alors je n'ai pas ça. C'est pas possible d'avoir à la fois A plus petit strictement que B, et B plus petit strictement que A. Donc vous voyez que les relations entre les nombres, elles sont de nature diverse. On est là dans le cadre de ce qu'on appelle les relations d'équivalence. Et pour vraiment avoir une relation d'équivalence, il faut une troisième propriété, qui est la suivante, celle que j'ai donnée. 23 est congruent à 47, qui lui-même est congruent, par exemple, à 17, et donc 23 est congruent à 17. Donc ça se dit comme ceci. Si j'ai A qui est congruent à B modulo N, et que B est congruent à C modulo N, alors A est congruent à C modulo N. On a comme ça une chaîne, et ça, c'est la transitivité. Et l'égalité est transitive, parce que si vous avez A égale B, B égale C, alors on a bien A égale C. Un exemple géométrique, le parallélisme par exemple, c'est aussi ce qu'on appelle une relation d'équivalence. Si on a D1 qui est parallèle à D2, alors D2 est parallèle à D1, vous voyez, symétrique. Une droite est toujours parallèle à elle-même, réflexivité et transitivité. Si D1 est parallèle à D2, et que D2 est parallèle à D3, alors D1 est parallèle à D3. Vous voyez, ça fait que le parallélisme c'est aussi une relation d'équivalence, au même titre que les congruences. Et pour être vraiment précis, on est dans ce qu'on appelle les relations binaires, donc les relations entre deux objets. Ici, on est sur une relation binaire en Z, on prend deux éléments de Z, et on a comme ça ces trois propriétés, et ça donc c'est, on est dans la congruence. Alors il y a d'autres petites propriétés toutes simples. Le mode ne peut pas être égal à 0. Mais si, donc le cas le plus simple, le cas n égale 1. Prenons un mode égal à 1. La division Euclidienne par 1, si on fait 23, par exemple, divisé par 1, 23, c'est une fois 23, plus 0. Le reste est toujours, quand on divise par 1, le reste est toujours égal à 0. Donc en fait, tous les nombres ont le même reste modulo 1. Si on divise par 1, tous les nombres ont le même reste, donc ça veut dire que, quel que soit appartenant à Z, eh bien A est congru à 0 modulo 1. C'est pour ça que la relation modulo 1 n'est pas très intéressante, puisqu'en fait il n'y a qu'un seul ensemble de nombres, ils sont tous égaux. Et on ne dira pas égaux, on dira qu'ils sont tous congrus à 0. Donc finalement, tous les nombres sont renvoyés sur ce même nombre 0, et donc ça perd un petit peu d'intérêt. Si on prend le cas L égale 2, il y a deux restes possibles. Pour tout A appartenant à Z, eh bien A est congru à 0 modulo 2, ou A est congru à 1 modulo 2. Donc modulo 2, on est dans un monde qui ne prend que deux valeurs, 0 ou 1 modulo 2. Si on prend les nombres pairs, donc les éléments de 2Z, eh bien A est congru à 0 modulo 2. Si on prend A appartenant au nombre impair, donc un entier n'appartenant pas au pair, eh bien A sera congru à 1. Donc c'est comme ça qu'on peut reconnaître qu'un nombre est pair ou impair. Si on prend sa valeur modulo 2, eh bien si on trouve 0 c'est un nombre impair, si on trouve 1 c'est un nombre impair. Et donc vous avez compris que modulo n, en fait il n'y a que n, valeur modulo n, il n'y a que n valeurs possibles, qui sont tout simplement les n restes par la division par n. Donc si on est sur un mode 8, eh bien un nombre sera congru à 0, à 1, à 2, à 3, à 4, à 5, à 6, jusqu'à 7. Et si vous répondez 8, eh bien en fait 8 sera congru à 0. Donc on peut toujours répondre pour chaque nombre, qu'un nombre est congru à l'un de ces 8 ici, modulo 8. Je prends par exemple 77, eh bien 77, si je fais sa division par 8, donc on a 8 fois 9, donc 72, 72 plus 5, eh bien en fait ça, pour l'instant c'est une égalité, et si je passe en modulo 8, donc ici on passe en modulo 8, donc 77 sera congru à 5, puisque ici il reste 5, modulo 8, et vous voyez bien que j'ai trouvé un nombre entre 0 et 7, c'est normal parce que si je divise par 8, j'ai ici un reste qui est entre 0 et 7. Maintenant, prenons deux nombres, 156 et 207, et regardons les modulo 17. Est-ce qu'ils sont égaux ou pas ? Pour l'instant, en l'état de nos connaissances, eh bien il va falloir faire division 256, donc 156, je vous le dis, c'est 17 fois 9, qui fait 153 plus 3, ça veut dire que 156 est congru à 3, modulo 17. J'utilise les crochets plutôt. Ensuite, 207, c'est 17 fois 12, qui fait 204, plus 3, donc 207 est congru à 3, aussi modulo 17. Conclusion, les deux nombres ont le même reste, modulo 3, on avait donc 156, qui est congru à 207, modulo 3, modulo 17, pardon, ou alors 207 est congru à 156, modulo 17, on a vu la symétrie. Vous voyez que je suis obligé de faire deux divisions, donc il y a une propriété qui permet d'éviter ça, repérer si les nombres sont égaux, modulo 17. Et c'est la propriété suivante, j'ai mis capital au masculin, c'est vraiment quelque chose pour moi qui est capital, c'est pas forcément la propriété qui est capitale, mais ça c'est capital de le savoir, c'est que si on prend un identité naturellement nulle, pour tout anti-relatif a et b, a congru à b modulo n, ça équivaut à avoir n divise la différence a moins b. Regardons ça avec nos 156 et 207, je vais faire 156 moins 207, ça donne combien ? Vous voyez qu'ici, on a 51, 51 qui est 17 fois 3, donc effectivement 17 divise 156 moins 207, donc on aurait pu avec ça dire que 156 et 17 étaient bien congru modulo 17. Par contre, on n'a pas trouvé le reste par la division, mais on a réussi à déterminer qu'ils étaient congru modulo 17. Alors on va quand même démontrer cette propriété. Vous remarquez que cette propriété c'est un équivalent, donc on va démontrer de gauche à droite, puis de droite à gauche. On va partir de gauche à droite, donc supposons que A est congru à B, donc modulo n. Ça veut dire déjà que A et B ont le même reste par division par n, donc il existe un couple QR de dentier relatif tel que A s'écrit, je divise donc par n, n fois Q plus R, et il existe une autre quotient Q' appartenant à Z tel que B s'écrit n fois Q' plus R, oui j'ai mis le même reste. Et ce reste, je rappelle, est entre 0 et strictement plus petit que n. Alors, je vais faire la différence, donc dans ce cas-là, A moins B s'écrit nQ plus R moins nQ' plus R, et on va se simplifier, il me reste nQ moins nQ', il me reste n fois je factorise Q moins Q', Q moins Q' c'est un dentier relatif, donc A moins B c'est n fois un entier, donc effectivement n divise A moins B, donc on a bien été de gauche à droite. Supposons maintenant que n divise A moins B, ça veut dire qu'il existe un entier relatif K tel que A moins B s'écrit n fois K. Je vais mettre le B de l'autre côté, donc ça veut dire que A peut s'écrire n fois K plus B. Alors ça ressemble un petit peu à une division euclidienne, mais attention, ici B n'est pas forcément entre 0 et strictement plus petit que n, donc on n'a pas encore une division euclidienne, donc il faut faire attention. Maintenant je vais faire la division de A par n, donc il existe un couple QR dentier relatif, donc dans Z2 tel que A s'écrit n fois Q plus R, mais cette fois-ci R il est super grain, il est strictement plus petit que n, ça c'est la division euclidienne de A par n. Si je mixe ces deux choses là, je trouve que nQ plus R est donc égal à nK plus B. Et c'est là qu'il y a une très jolie astuce. Alors j'aurais du l'écrire dans l'autre sens, je vais mettre le nQ plus R ici, regardez, je vais mettre nK de l'autre côté, et je vais factoriser, donc ça veut dire que je viens de montrer que B c'est nQ plus R moins nK, et je vais factoriser, vous voyez ici, il y a deux termes avec des n, je fais n fois Q moins K plus R. Alors ça c'est très important B égale n fois Q moins K plus R. Pourquoi c'est très important ? Parce que déjà ici on a un dentier ici relatif avec ici un nombre R qui est positif et strictement plus petit que n. Donc ça c'est une division euclidienne, c'est la division de B par n, exactement les conditions qu'il faut, un dentier relatif un nombre ici entre 0 et n strictement. Donc ça veut dire que le reste, donc si je divise B par n, le reste de la division de B par n est donc R. Or, R c'est déjà et le reste de la division de A par n. Donc en conclusion, on vient de montrer que R c'est le reste de division donc A et B ont même reste par la division par n. Et donc on appelle la définition A est congrue à B modulo n. Donc vous voyez c'est une très jolie démonstration si vous voulez la faire. Maintenant on va finir par un petit exemple et on s'arrêtera. Montrons par exemple que 2024 est congrue à 2277 modulo 23. Eh bien il faut que je fasse 2277 moins 2024. Je calcule, je trouve 253 je divise 253 par 23. Il se trouve que 5 c'est 2 plus 3, donc là on reconnait bien sûr un équilibre de 11, donc c'est 23 fois 11. Donc effectivement 2277 moins 2024 est donc divisé par 23 23 divise la différence donc les deux noms sont congrues. Dans un sens ou dans l'autre, puisqu'on a vu la symétrie modulo 17. Voilà pour cette première partie du cours, on est vraiment sur le début. J'espère que j'ai été clair, que ça vous a plu. A très bientôt pour cette suite passionnante sur les congrès.