Ma démonstration est-elle correcte ?

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à tous,

Dans le cadre d'un TP sur l'algorithme d'Euclide, je dois faire une démonstration par récurrence. J'aimerais bien que vous me donniez votre avis, pour savoir si ce que j'ai écrit est correct ou si je dois changer quelques trucs.

Données du TP

On considère l'espace $\mathbb Z_n = \mathbb Z/n\mathbb Z$. C'est donc l'ensemble des classes d'équivalences $\overline{0}, \overline{1}... \overline{n-1}$. On dit que $b \in \mathbb Z_n$ est inversible si, et seulement si : $pgcd(b, n) = 1\space mod\space n$ (avec $n \in \mathbb N^*$).

L'algorithme d'Euclide permet de savoir s'il est possible d'effectuer cette inversibilité dans $\mathbb Z_n$. L'algo d'Euclide étendu, lui, permet de calculer cet inverse dans $\mathbb Z_n$.

D'après l'algorithme d'Euclide : "si a et b sont deux entiers avec par exemple a>=b, si r est le reste de a par b, alors le pgcd de a et b vaut le pgcd de b et r". Il consiste donc à faire ces divisions :

$r_0 = a$

$r_1 = b$

$r_0 = q_1r_1 + r_2$

$r_1 = q_2r_2 + r_3$

$ etc. $

$r_{m-2} = q_{m-1}r_{m-1} + r_m$

$r_{m-1} = q_mr_m$

$r_m$, dernier élément non-nul, est alors le PGCD de $r_0$ et $r_1$.

Définissons maintenant la suite récurrente $t_0, t_1, ..., t_n$, utilisée pour l'algorithme d'Euclide étendu, et pour laquelle la suite $q_j$ est définie par l'algorithme d'Euclide précédemment écrit :

$t_0 = 0$

$t_1 = 1$

$t_j = t_{j-2} - q_{j-1}t_{j-1} \space mod \space r_0$ (si $j \ge 2$)

Démonstration à faire

Montrez par récurrence : Pour $0 \le j \le m$, on a : $r_j \equiv t_jr_1 \space (mod \space r_0)$.

Ce que j'ai écrit (est-ce correct ?)

Montrons par récurrence que :

$\forall j \in [0;m], r_j \equiv t_jr_1 \space (mod \space r_0)$

Vérifions que la propriété est vraie aux rangs $j = 0$ et $j = 1$.

Au rang $j = 0$ :

$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_0 = t_0r_1 + kr_0$

$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_0 = kr_0$ (car $t_0 = 0$)

$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow k = 1$

Donc k existe bien pour $j = 0$.

Donc la propriété est vraie au rang $j = 0$.

Au rang $j = 1$ :

$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_1 = t_1r_1 + kr_0$

$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_1 = r_1 + kr_0$ (car $t_1 = 1$)

$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow k = 0$

Donc k existe bien pour $j = 1$.

Donc la propriété est vraie au rang $j = 1$.

On considère que la propriété est vraie aux rangs $j-1$ et $j$. Montrons qu'elle est vraie au rang $j+1$.

$\forall j \in [0;m], r_j \equiv t_jr_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_j = t_jr_1 + kr_0$

$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = t_{j+1}r_1 + kr_0$

$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = r_1(t_{j-1} - q_jt_j) + kr_0$

$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = $

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

Une première remarque d'ordre éthique. Je ne pense pas que le choix du mot « inversible » soit très bon. Ou alors j'ai raté une justification. On s'attendrait plutôt à dire qu'on a inversibilité quand la classe d'équivalence est la même.

Ensuite, faire une introduction à ton problème est une très bonne chose. Mais elle est peu claire. On baigne dans des notations que tu as plus ou moins introduites, c'est pas super pour la lisibilité.

Pour ce qui est de la forme de ta démonstration, elle est clairement trop abrupte. Il faut que tu « parles » plus. Le langage mathématique c'est bien, mais ça n'est clair que pour celui qui a compris. Donc il faut nous faire comprendre (de préférence) avant d'écrire en langage mathématique. Plus brièvement, donne-nous les idées qui entrent en jeu au lieu de nous faire un exposé uniquement technique (ce qui n'est jamais intéressant).

Enfin, je n'ai toujours pas compris ce que tu démontres :

Montrons par récurrence que :

$\forall j \in [0;m], r_j = t_jr_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_j = t_jr_1 + kr_0$

Lern-X

C'est une définition, non ?

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0
Auteur du sujet

Bonjour Holosmos,

En ce qui concerne la signification de "inversible" : il me semble que le prof pense à la définition de l'inversabilité des éléments d'un groupe (ie. : la propriété d'un groupe qui permet de retrouver l'élément neutre de celui-ci).

Et ok, je vais travailler sur la rédaction de l'intro et de la démonstration.

Pour ce qui est du bloc "Montrons par récurrence que : ", oups, mea culpa ! Je vais modifier ça.

Université de Bretagne-Sud <3

+0 -0
Staff

En ce qui concerne la signification de "inversible" : il me semble que le prof pense à la définition de l'inversabilité des éléments d'un groupe (ie. : la propriété d'un groupe qui permet de retrouver l'élément neutre de celui-ci).

Ouais je vois mais il n'empêche que dans ce cadre (où on s'intéresse à la primalité et aux divisions euclidiennes) c'est pas forcément super bien choisi. Mais c'est pas le plus important.

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0
Auteur du sujet

Voilà, j'ai édité l'OP : normalement la consigne "Montrez que […]" est OK, et j'ai écrit ma "démonstration". Démonstration entre guillemets car je bloque…

Je ne vois pas quoi écrire de plus dans l'introduction, que me conseillerais-tu ? Peut-être d'expliquer ce que sont $r_{machin}$ et $t_{truc}$ non ?

Le souci, c'est justement que je ne sais pas du tout de quoi il s'agit, je trouve que le prof a défini ça un peu à l'arrache… Je vois bien qu'il utilise la notion de congruence pour définir les $r_{machin}$, et d'ailleurs j'en fais moi-même usage dans l'algo d'Euclide que j'ai programmé, mais la notation du prof est vraiment peu claire, je me perds avec tous ces indices…

Et pour les $t_{truc}$, c'est encore pire… : je ne vois clairement pas à quoi ils correspondent.

Du coup si toi (ou quelqu'un d'autre évidemment :) !), tu as compris à quoi servent toutes ces variables, je veux bien que tu m'expliques s'il te plaît :)

EDIT :

Tu dois te demander pourquoi j'ai écrit une démonstration alors que je ne sais pas à quoi servent les variables qui y sont utilisées. En fait, le prof a donné une correction (donc une démonstration valide), mais j'ai l'impression qu'il saute des étapes, qu'il n'utilise pas certaines définitions. Par exemple, il n'a pas l'air de se baser sur l'existence d'un relatif $k$ pour faire la démonstration, alors que justement c'en est visiblement la pierre angulaire.

Du coup je m'inspire de sa démonstration et j'utilise les définitions/propriétés mathématiques de la congruence pour essayer de me plonger dans la logique de sa démonstration et, au bout d'un moment, de réussir à comprendre et à écrire cette dernière.

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

Ce sont les différentes variables qui interviennent dans l'algorithme d'Euclide. En fait, le mieux avant de rédiger ton introduction, c'est que tu t'appropries le problème. Prends le temps sur un exemple de bien identifier qui fait quoi. Ensuite, rédiger l'introduction sera plus facile, tu auras juste à dire qui fait quoi (comme tu l'as compris) et ça sera bien.

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0
Auteur du sujet

Ce sont les différentes variables qui interviennent dans l'algorithme d'Euclide. En fait, le mieux avant de rédiger ton introduction, c'est que tu t'appropries le problème. Prends le temps sur un exemple de bien identifier qui fait quoi. Ensuite, rédiger l'introduction sera plus facile, tu auras juste à dire qui fait quoi (comme tu l'as compris) et ça sera bien.

Holosmos

Bein j'ai déjà essayé de faire ça, mais à chaque fois je me retrouve bloqué parce que $r_2$ et $r_3$ ne sont définies nulle part :-/

Exemple (je ne fais que suivre son algorithme dit "de divisions").

$a = 20$ et $b = 10$ ($a$ est bien supérieur ou égal à $b$).

$r_0 = 20$ et $r_1 = 10$

$r_0 = 10q + r_2$ ($r_2 \in ]0;10[$)

$r_1 = q_2r_2 + r_3$ ($r_3 \in ]0;r_2[$)

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Auteur du sujet

D'accord je vois ton souci.

En fait $r$ désigne le reste dans la division euclidienne. En principe tu sais montrer qu'il est unique

Holosmos

Je ne comprends pas pourquoi tu as écrit la deuxième phrase ? Pourquoi y a-t-il des indices ?

Université de Bretagne-Sud <3

+0 -0
Staff

Je n'ai pas noté les indices parce que c'est sur le fait général que j'ai fait ce commentaire.

Dans l'expression :

$$ a =bq + r $$

$a,b,q$ sont entiers et $r>0$ est strictement inférieur à $b$, on dit que :

  • $q$ est le quotient de $a$ par $b$ ;
  • $r$ est le reste de la division euclidienne de $a$ par $b$.

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0
Auteur du sujet

Oui, je comprends bien, on peut même dire que : $a \equiv r \space mod \space b$ (par définition).

En revanche je ne vois toujours comment ça peut m'aider à comprendre ce qu'a écrit le prof :-/

Notamment : pourquoi les $r$ ont-ils $0$ et $1$ comme indices alors que les deux derniers $r$ ont les indices $m-2$ et $m-1$ ? Cela ne signifie-t-il pas que les indices doivent être incrémentés, et donc que le prof a oublié de faire ces incrémentations d'indices (par étourderie) ?

Université de Bretagne-Sud <3

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte