[Spé Maths] - Congruences et Divisibilité 2

Voici l'autre exo de spé :

Citation :

Démontrez que pour tout entier naturel n≥2 :
5⁵ⁿ⁺² + 3^5n-1 - 7 ≡ 0 (mod 11)

Pour cette exercice, il s'agit de bien observer l'expression et de faire le calcul tout simplement. Ne pas avoir peur de calculer en quelque sorte.

Lorsqu'on a une somme de plusieurs termes, il faut commencer par regarder chaque terme modulo 11 ici en espérant que cela se décante bien à la fin. D'autre technique sont utilisable tel que le raisonnement par l'absurde ou encore la récurrence mais ici le calcul directe marche très bien.

Donc que vaut le 5⁵ⁿ⁺² modulo 11 et même question pour 3^5n-1.

Bon courage!

5⁵ = 3125
or 3124 est divisible par 11

donc 5⁵ ≡ 1 [11]

soit 5⁵ⁿ ≡ 1 [11]

donc 5^{5n + 2} ≡ 25 [11] donc 5^{5n + 2} ≡ 3 [11]

de même : 3⁵ ≡ 1 [11]

donc 3⁵ⁿ ≡ 1 [11] donc 3⁵ⁿ ≡ 12 [11] et en multipliant par 1/3 chacun des deux membres :

3^{5n - 1} ≡ 4 [11]

Donc par somme : 5^{5n + 2} + 3^{5n - 1} ≡ 7 [11]

d'où : 5^{5n + 2} + 3^{5n - 1} - 7 ≡ 0 [11]

Et voilà !

Mais deux problèmes se posent :

- comment justifier que ce soit pour tout entier naturel n≥2 ?
- au bout d'un moment j'ai multiplié par 1/3 et je crois que je n'ai pas le droit car ce n'est pas un entier...

Alors ne effet, il y a bien deux question à ce poser mais l'idée est totalemetn dans tout ce qui est écrit.

Alors le soucis c'est la division par 3 ou la multiplication par 1/3 qui n'est pas faisable sur des entier en effet. Mais là, il faut dépasser se cadre là et regarder à quoi correspond 1/3 dans R par exemple.

Dans R, 1/3 c'est tout simplement l'inverse de 3 et cela a été défini de cette façon là:

a est l'inverse de b dans R si et seulement si a*b=1 c'est à dire a=1/b=b^-1 dans R

Mais en fait, lorsqu'on a un autre ensemble sur les entiers, la définition reste là même sauf qu'on écrit plus de fraction mais seulement une puissance -1 pour désigner des inverses.

Par exemple lorsqu'on considère 3 est linverse de 2 lorsqu'on considère des congruence modulo 5. En effet, 2*3≡1 [5]. Pour appeler un chat un chat en fait lorsqu'on fait des congruence modulo 5, on dit qu'on travail dans un corps (tout comme R) qui s'appelle Z/5Z (c'est à dire qu'il s'agit des entier relatif dans Z qui sont quotienté par l'ensemble des multiples de 5 dans Z ce qui revient à dire que cet ensemble est constitué des reste de la division euclidienne d'un entier relatif par 5 tout simplement).

Donc ici, il existe belle et bien un inverse pour 3 lorsqu'on considère les entiers relatif modulo 11. Et tu l'as même explicité vu que 3⁵≡1 [11] donc 3*(3⁴)≡1 [11] Donc 3⁴ est l'inverse de 3 pour la congruence modulo 11. Mais 3⁴≡4[11]. Donc 3^-1≡4[11].

Est-ce que tu comprends la démarche? (Je ne parle pas de la définition de Z/11Z car nous sommes en dehors du programme et de très loin mais je voulais évoquer ces corps d'entier qui sont totalement sous-jacent à la notion de congruence mais si tu ne comprends pas tout ce n'est pas forcément très grave, tu reverras cela si tu poursuis dans des études de mathématiques).

Et enfin, ta remarque sur la valeur que peut prendre n est tout à fait pertinente et je ne sais pas en effet pourquoi, il y a un problème pour eux lorsque n=0 ou 1 vu que cela marche sans aucun problème. A moins qu'il y a un problème d'énoncer et au lieu de considéré 5⁵ⁿ⁺², il faut considérer 5^5n-2 mais dans notre cas comme tu le constates, il n'y a pas de soucis en 0 et en 1, on peut même effectuer le calcul à la main d'ailleurs.

Est-ce plus clair dans l'ensemble?

Mais dans les congruences là on ne travaille qu'avec des entiers alors comment peux-tu écrire : 3^-1 ≡ 4[11] ?? et alors comment faire dans mes calculs, au moment où je veux multiplier par 1/3 ?

Et tu as raison, pour n=1 ça marche, mais par contre ça ne marche pas pour n=0 .....
Et alors comment faire pour justifier que c'est pour tout n≥1 ?

n=0 marche très bien, 5²+3^-1-7≡3+4-7[11]≡0[11]

En fait, 3^-1 est une notation qui n'a rien à voire avec 1/3 vu qu'on n'a pas accès à la fraction ici. 3^-1 lorsqu'on prend une congruence modulo 11 signifie comme je te l'ai écrit qu'il s'agit del 'inverse de 3 lorsqu'on prend une congruence modulo 11 c'est à dire que 3*3^-1≡1[11] et la seule valeur qui face cela lorsqu'on est en congruence modulo 11 c'est 4. En effet, 3*4≡11[11]=≡1[11] donc 4 est bien l'inverse de 3 lorsqu'on prend des congruences modulo 11.

Est-ce que tu comprends la démarche ou l'idée tout du moins?

Pour trouver l'inverse de 3 lorsqu'on considère une congruence modulo 11, on cherche un entier a tel que 3*a≡1[11] tout simplement. Or on a vu que 3⁵≡1[11] donc 3⁴ est bien l'inverse de 3 modulo 11 car 3*3⁴≡1[11].

Baaah je comprends ta démarche mais 3^-1 n'étant pas un entier, cela me gêne...

3^-1 est tout ce qu'il y a de plus entier lorsque nous sommes dans les congruences modulo 11. Vu que 3^-1≡4[11] tout simplement.

Si c'est la notation qui te gêne oublie là si tu veux quoique cela serait une mauvaise idée car tu ne comprendrais plus pourquoi pour n=0 l'égalité reste vraie. En fait, il faut voir 3^-1 comme la valeur de a qui est tel que la division euclidienne de 3*a par 11 donne un reste égale à 1.

Cela serait tellement plus simple si je t'expliquais la notion d'anneau Z/nZ ou de corps Z/pZ avec p un nombre premier et n un entier quelconque. Mais hélas, la théorie n'est pas simple à mettre en place rigoureusement et cela poserait donc quelques soucis si je ne faisais pas cela rigoureusement. Donc hélas pour moi, je suis obligé de dire que 3^-1 est une notation lorsqu'on considère des congruences modulo 11 alors qu'il y a bel et bien une signification propre et est tout à fait juste.

Il faut savoir en fait qu'il y a des cas où 3^-1 n'a pas de sens dans le sens où il n'existe pas d'inverse à 3 dans la congruence qu'on considère. Mais en l'ocurrence ici, nous avons explicité concrètement que 3*3⁴≡1[11] et par conséquent que 3⁴ était l'inverse de 3 pour la congruence modulo 11.

En fait, je suis contraint pas un problème de programme de ne pas pouvoir aller plus loin dans l'explication par manque de possibilité de construction concrète d'un ensemble qui serait tellement plus adéquat (ce qui m'énerve un peu d'ailleurs car c'est tellement plus simple lorsque tout est construit mais bon je fais avec lol).

Par contre si ce n'est toujours pas clair que dans notre cas concret 3^-1 est bel et bien un entier (3^-1 n'est pas du tout égale à 1/3 dans notre cas attention à ne pas marquer cela !!!! En effet, ici il vaut 4 vu que nous sommes modulo 11), j'essaierai de changer le cadre en te donnant d'autres exemples. La seule chose qu'il faut comprendre c'est la définition-propriété suivante:

Définition-Propriété de l'inverse d'un entier modulo un nombre premier p a écrit:

Pour tout entier a, et nombre premier p,
Il existe un entier b tel que a*b≡1[p]
On note cet entier a^-1 (c'est à dire que a^-1≡b[p])

Bon courage!

Raaaah merci pour toutes ces explications. Bonne nuit

Bonsoir Natty,

Je ne sais pas si tu as compris concrètement cette histoire d'inverse et de notation dans ce qui ressemble à un ensemble mais n'en est pas un. En gros c'est plutôt complexe alors que ça devrait être simple car les mathématiques sont un langage qui a vocation à formaliser et à simplifier les choses, donc tout ceci est ironique. Et ta curiosité en fait t'empêche de croire bêtement que tout est simple alors qu'en effet, on te cache des choses concrète cari l y a du travail à faire derrière. Et bien, je considère que la curiosité en générale et de surcroît en mathématiques ne devrait pas t'empêcher de comprendre ou d'avancer bien au contraire. Alors j'ai décidé vu qu'il y a une petite période d'accalmie, de t'expliquer et donc de carrément construire une partie de l'arithmétique qui te manque pour bien assimiler les choses.

Je tiens à préciser d'entrée de jeu que tout ce que je vais raconter par la suite est totalement hors programme de terminale S. Cependant, je considère sans doute à tord, je vais justement voir que tout ce que je vais raconter est totalement accessible avec un niveau terminale S (et même un niveau inférieur vu que cela était à une époque enseigner bien avant la terminale mais les programme et les moeurs évolue ce qui est un bien ou un mal on jugera sur la durée après tout). Alors allons-y et posons un cadre voire mêem une motivation de ce qui va suivre.

Pour le cadre, je souhaite en fait travailler sur les entiers relatif ou naturel peu importe vu que par multiplication par (-1) un entier relatif négatif peu s'écrire comme un entier naturel. Pour cela, on a vu cette année la notion de congruence qui est en fait qu'une simplification d'écriture où on sous entend une addition à un facteur près qu'on ne souhaite pas écrire tout simplement:

En effet, pour a,b et c des entiers, a≡b[c] <=> il existe k dans Z tel que a=b+k*c (ce qui est tout à fait possible d'accès pour un élève de troisième qui a manipulé un peu les nombres entiers, je pense mais nous avons d'autre chose à faire en 3ème que de "s'amuser" avec ce genre de notation)

Mais ne fait qu'est-ce que Z?

Nous savons depuis quelque temps déjà qu'il s'agit de l'ensemble des nombre relatif mais ce que nous n'avons jamais mis en évidence c'est sa structure en tant qu'objet. Comment on manipule les éléments dans l'ensemble Z? C'est ça la question primordiale car nous n'avons pas le droit de tout faire, hélas (le risque serait de faire une division brute et paf on arriverait dans D ou Q et plus dans Z lui-même).

Et bien essayons de formaliser un peu tout ça. Je vais dire que j'associe à Z deux lois "+" et ".". En fait une loi n'est autre qu'une simple fonction tout simplement, l'une dite additive et l'autre dite multiplication. C'est deux lois sont dites internes car l'ensemble de départ est un couple d'entiers relatif et l'ensemble d'arriver est encore un entier relatif. Donc nous restons dans l'ensemble des entiers relatif ce qui explique le mot "interne".

On appelle élément neutre pour l'addition, un élément a dans Z tel que pour tout b dans Z, b+a=b. Il s'agit vous l'aurez compris du 0 tout simplement. On dit donc que 0 est l'élément neutre pour l'addition dans Z

Qui dit élément neutre pour l'addition, annonce la notion d'élément neutre pour la multiplication. Il s'agit de l'existence d'un a dans Z tel que pour tout b dans Z, a*b=b. Vous l'aurez aussi compris qu'il s'agit du 1 qui correspond au neutre pour la multiplication.

De plus, pour tout a et b dans Z, a*b=b*a (il n'y a pas d'autre pour faire des multiplications). On appelle cette propriété, la commutativité. Il s'agit du fait qu'on puisse multiplier deux nombre dans un sens ou dans un autre. Vous n'avez pas encore vu d'ensemble qui ne vérifie pas cette propriété mais sachez qu'il en existe et peut-être l'avez vous remarquer dans l'ensemble des fonctions où la loi de multiplication ici est la composition "o". Vous testerez, mais il est très rare que FoG=GoF. On dit que l'ensemble des fonctions n'est pas commutatif .

Ainsi défini, on appelle tout simplement le triplet (Z,+.) un anneau (c'est le nom de sa structure). Et en fait, on peut même faire mieux car l'anneau Z est engendré par 1. En effet, pour tout k=1+....+1 (avec k fois le chiffre 1) et -k=-1....-1 (avec k fois le chiffre -1 qui est l'opposer de 1). Et là, je vais bluffer mais j'ai pas le choix (le travail serait trop long), il en va de même pour tout sous ensemble de Z c'est à dire qu'on peut trouver un élément qui engendre le sous ensemble en question.

Mais où voulons-nous en venir???

Propriété [admise]:
Tout sous groupe de Z peut s'écrire s'écrire de la forme nZ={n*k, kЄZ} avec nЄN*. (n*Z est appelé un idéal de Z).

Définition-Propriété:
Soit n un entier naturel non nul. Soient a et b deux entier relatif, on a:
"a≡b[n]" <=> "(a-b)ЄnZ"

Démonstration: a≡b[n] <=> a-b≡0[n] <=> il existe k dans Z tel que a-b=n*k
Fin de la démonstration

Ainsi, on a complètement redéfini la notion de congruence pour avoir une notion ensembliste tout simplement (ce qui est beaucoup plus simple à manipuler comme tu vas le constater tout de suite)

Maintenant, on va définir ce qu'est un ensemble quotient. C'est la chose la plus complexe à appréhender mais vous allez vite comprendre par une image simple. Le but ici est de déterminer concrètement à quoi correspond l'objet Z/nZ. Il s'agit d'un quotient de deux ensembles d'entiers ici mais concrètement c'est quoi?

Et bien si je prend x dans Z et que je considère la division euclidienne de x par n, j'obtiens l'existence d'un couple (q,r) d'entier tel que:

x=n*q+r avec |r|<|n|

Et bien, je vais définir le quotient Z/nZ comme l'ensemble des restes de la division euclidienne de tous les éléments de Z par l'entier n.

C'est à dire que tous les éléments de Z/nZ sont tous les entiers positifs inférieurs strictement à n. Donc Z/nZ contient exactement {0;1;2;....;n-1}. Mais là, tu t'insurges contre le bluff !!!!! En effet, -1 est aussi dans cette ensemble vu que n-1=n*1 -1 et |-1|<|n| !!! Et bien oui, il y a une subtilité non négligeable ici qu'il faut absolument bien comprendre.

En effet, les éléments de Z/nZ ne sont pas exactement des entiers mais des groupes d'entier qu'on appelle des classes. En effet, 0 représente en fait tous les entiers relatifs divisible par n, donc ce n'estp as exactement le 0 qu'on connait même s'il s'écrit pareil car il a exactement les mêmes propriétés. Et on l'écrit ainsi car 0 ici est exactement l'élément neutre pour l'addition! 1 est exactement un représentatn de la classe de tous les nombres s'écrivant 1+k*n tout simplement et on l'écrit ainsi car il s'agit aussi de l'élément neutre pour la multiplication.

Et là, tu commences à entrevoir la congruence à l'état le plus pure!!!! Mais oui mais c'est bien sur!! Regardons de plus près:

Si je travaille Z, je vais écrire: a≡b [n]. Mais si j'écris cela en forme développée, j'obtiens qu'il existe un entier relatif k tel que: a=b+k*n. Et dans la dernière expression, il s'agit bien d'une égalité!
Maintenant, si je prend la classe dans Z/nZ de chacun des nombres dans cette égalité j'obtiens: a=b !!!!!!!!!!!!!!!!!!!!!!!!! Et bien oui, nous venons de voir que n*k faisait partie de la classe de 0, donc on ne l'écrit pas.

Et en fait, écrire des congruence c'est tout simplement travailler dans l'anneau Z/nZ muni de l'addition et de la multiplciation interne découlant de l'addition et de la multiplication définies pour l'anneau Z (c'està dire qu'il s'agit des mêmes fonctions tout simplement celle que vous connaissez depuis toujours).

Maintenant, on constate que dans Z/nZ, la multiplication par n rend les objets nuls. Donc nous n'avons plus la propriété suivante que nous avions dans R ou Q par exemple: "x*y=0 <=> x=0 ou y=0".
En effet, contre exemple: dans Z/3Z (donc ici n=3), on a 2*3=0 (6 est un multiple de 3 donc est nul dans Z/3Z

Et nous avons aussi perdu la notion d'inverse qui est propre à R ou Q permis les ensembles que nous connaissons. Cependant, si on écrit cette définition dans Q ou dans R avec la notion ^-1, on enlève le côté fractionnaire de la chose pour passer à un côté plus formelle et plus utilisable ne quelque sorte.

En effet, d'une manière générale la définition d'un verse peut être écrite pour tout anneau quelconque ainsi:

Définition:
Soit a dans un anneau E muni des lois "+" et "." avec 1 élément neutre pour l'addition,
S'il existe un bЄE tel que a.b=1 dans E alors b s'appelle l'inverse de a et on le note b=a^-1.


Grâce à cette définition, on peut regarder par exemple les éléments qui serait inversible dans Z.
Bon 0 c'est pas possible car tout multiplication par 0 donne 0 (on appelle cela un élément absorbant).
1 par contre admet un inverse dans Z, c'est lui-même car 1 est le neutre pour la multiplication donc on a 1*1=1!! donc 1^-1=1 dans Z (ici, il n'y a pas de fraction mais seulement une notation pure).
ensuite pour les entiers naturels supérieur ou égale à 2, leur inverse est dans Q, donc il n'ont pas d'inverse dans Z.
Dans les négatif, -1 admet un inverse! En effet, (-1)*(-1)=1. Par conséquent, -1 est l'inverse de lui-même c'est à dire que: (-1)^-1=-1 dans Z (ici encore il ne s'agit que d'un notation).
Et de même tous les entiers inférieurs ou égale à -2 admettent des inverse dans Q mais pas dans Z.
En conclusion, dans Z, l'ensemble des inverses est se réduit à {-1;1} tout simplement.

Mais on peut faire les mêmes manipulation dans Z/nZ en utilisant la même définition vu qu'il s'agit du même élément neutre et des mêmes lois que dans Z. C'est à dire qu'un élément a sera inversible dans Z/nZ s'il existe b dans Z/nZ tel que a.b=1 et on notera a^-1 cet inverse.


Ce qui conclut la théorie que je souhaite mettre en place.


Retour à l'exercice:

On se place dans Z/11Z et on va admirer la puissance de cette théorie à l'oeuvre.

On a: 3⁵=1 dans Z/11Z
Or 3⁵=3.3⁴

Donc 3.3⁴=1 dans Z/11Z

D'où par définition 3 est inversible dans Z/11Z et son inverse vaut 3⁴.

Or 3⁴=4 dans Z/11Z (le reste de 3⁴ par 11 est bien égale à 4)

En conclusion, l'inverse de 3 dans Z/11Z est 4. Et par définition, on a donc: 3^-1=4 dans Z/11Z (3^-1 signifiant tout simplement "inverse de 3 dans Z/11Z").


Est-ce qu'ainsi cela te paraît plus clair ??? Je l'espère en tout cas car même si je n'ai pas détaillé toute la théorie et est admis des choses, au moins là tu as un cadre logique et structuré pour mieux appréhender les choses qui te semblait flou ou tout du moins je l'espère.

N'hésite pas à poser des questions sur tout mon baratin ce quelque chose ne te semble pas clair ou totalement flou même.

Bonne continuation!