Morphisme de réduction

JLT

Plus précisément : montrer que si $m$ et $n$ ne sont pas premiers entre eux alors les groupes $\Z/mn\Z$ et $\Z/m\Z\times \Z/n\Z$ ne sont pas isomorphes.

L'un possède un élément d'ordre $mn$ et pas l'autre.

troisqua

Déjà corrigé en détail.

OShine

@JLT en effet merci c'est un résultat que j'ai gardé en tête. 
Je vais essayé de donner au moins une bonne réponse dans cet exercice où j'ai fait n'importe quoi.
Soit $f : A  \longrightarrow B$ un morphisme de groupe. Si $f$ est isomorphe alors pour tout $a \in A$, $a$ et $f(a)$ ont le même ordre.
$\Z / mn \Z$ est un groupe cyclique engendré par $\bar{1} [mn]$. Cet élément est d'ordre le cardinal du groupe qui vaut $mn$.
On $mn = pgcd(m,n) \times ppcm(m,n)$ et comme $m$ et $n$ ne sont pas premiers entre eux on a $pgcd(m,n) >1$.
Soit $(\bar{1} [m], \bar{1}[n]) \in \Z / m \Z \times \Z / n \Z$. Alors $(\bar{1} [m], \bar{1}[n]) $ est d'ordre $ppcm(m,n) = \dfrac{ mn }{ pgcd(m,n) } < mn$.
Il n'existe donc aucun élément d'ordre $mn$ dans $ \Z / m \Z \times \Z / n \Z$.

bd2017

Là, j'avoue ma faiblesse: je n'ai pas compris cette dernière démonstration. Si j'ai bien compris  (1,1) est d'ordre $ppcm(m,n).$  Mais pourquoi, le fait que (1,1) n'est pas d'ordre $mn$ implique qu'il n'y a pas d'autre élément d'ordre $mn$?     

lourrran

quand tu écris : car $1 \not\equiv 3 [3]$
Le 1 et le premier 3, on voit d'où il viennent.
Et le 2ème 3, il vient d'où ?
Il vient d'un truc que tu as recopié sans comprendre, ou il vient d'un calcul que tu as oublié d'expliquer.

NicoLeProf

OShine a dit :

NicoLeProf a dit :

Bon, j'avais mal lu. Il n'y a pas équivalence logique entre $x \equiv 4 \pmod {45}$ et $x \equiv 4 \pmod 5$ .

J'ai utilisé une technique dans la vidéo de Maths Adultes qui transforme les modulo pour avoir que des nombres premiers.
Une condition nécessaire n'a pas besoin d'équivalence : $x \equiv 4 [45] \implies x \equiv 4 [5]$ car $45$ est un multiple de $5$.

Tu n'as pas compris ce que je veux dire.

Pour toi l'ensemble des solutions du système $x \equiv 4 \pmod{45}$ et $x \equiv 1 \pmod 6$ est l'ensemble des $x \equiv 19 \pmod {30}$ .

Car tu as fait une "simplification" en te disant que comme $x \equiv 4 \pmod  {45}$ alors $x \equiv 4 \pmod 5$. Cette implication est juste oui mais la simplification effectuée est fausse car tu as utilisé une condition trop faible. Il te faut impérativement une équivalence logique pour simplifier... !

C'est comme si tu écrivais lorsque tu résous une équation produit-nul de collège : $x(x+4)=0$ donc $x=0$ . Et tu oublies que $x$ peut être égal à $-4$ aussi !!!

Autrement dit (mais cela reste similaire à mes remarques précédentes) : l'ensemble des nombres entiers congrus à $4$ modulo $45$ n'est pas égal à l'ensemble des nombres entiers congrus à $4$ modulo $5$ donc ils ne sont pas interchangeables !!!

Vérifie ton ensemble de solutions : $x \equiv 19 \pmod {30}$ . Est-ce cohérent avec l'énoncé?

$19 \equiv 19 \pmod {30}$ donc logiquement $19$ est une solution du système selon toi? Est-ce le cas? Regarde $19$ modulo $45$ et modulo $6$ et tu vas t’apercevoir en 2 secondes qu'il y a un problème...

Tu en veux un autre ? Regarde : $79 \equiv 19 \pmod {30}$ et $79$ est congru à ??? modulo $45$ puis $6$ .

Je te conseille de t'entraîner sur d'autres systèmes pour vraiment comprendre les méthodes...

OShine

@NicoLeProf

J'ai voulu suivre la technique donnée dans cette vidéo de Maths Adultes à 27 min https://www.youtube.com/watch?v=xIzoYxOqmXs il raisonne par conditions nécessaires et non par équivalences.
Ma solution est fausse mais je ne comprends pas vraiment l'erreur.

OShine

@bd2017 oui tu as raison je cherche une solution autre mais je ne vois pas pour l'instant. 

troisqua

Déjà corrigé en détail.

NicoLeProf

OShine a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2379038/#Comment_2379038

L'erreur est ta simplification car elle ne fait pas intervenir le $PPCM$ de $45$ et $6$ qui est $90$ et non $30$ donc tu perds l'équivalence logique (le fameux isomorphisme avec $\mathbb{Z}/PPCM(m,n) \mathbb{Z}$ qui signifie que si $x$ est solution du système alors $x$ est congru à un certain nombre modulo le $PPCM$ et réciproquement, pour un système de deux équations).

Dans la vidéo de Maths Adultes, Gilles passe des choses sous silence pour ne pas perturber le lecteur et pour ne pas rendre le tout indigeste et aussi parce qu'il s'agit d'une étude pratique du théorème des restes chinois.

Il faut voir que les simplifications de Gilles fonctionnent car le $PPCM$ de $8$ et $12$ est $24$ et $3 \times 8=24=PPCM(3;8)$ donc en faisant cette manipulation, on "conserve" le $PPCM$ . On repère ensuite que raisonner modulo $14$ ou modulo $7$ ne change pas le $PPCM$ des trois nombres ($8$ ; $ 3$ ; $14$ ou $8$ ; $3$ ; $7$, peu importe le $PPCM$ est le même sauf que $8$ ; $3$ et $7$ sont deux à deux premiers entre eux) . C'est subtil quoi et pas évident à maîtriser...

Si tu veux appliquer le théorème des restes chinois : tu dis que $x \equiv 4 \pmod {45}$ et $x \equiv 1 \pmod 6$ doit pouvoir se simplifier en quelque chose modulo $2$, modulo $5$ et modulo $9$ qui sont deux à deux premiers entre eux et qui ont le même $PPCM$ que $45$ et $6$ qui est $90$ (cela se voit en étudiant les décompositions en produits de facteurs premiers de $45$ et $6$).

On regarde modulo $2$ ---> $x \equiv 1 \pmod 2$

On regarde modulo $5$ ---> $x \equiv 4 \pmod 5$

On regarde modulo $9$ ---> $x \equiv  4 \pmod 9$ .

Je te laisse finir avec la formule que tu as trouvée sur le théorème des restes chinois dans le cas général et je te garantis que tu vas trouver comme mon post que j'ai écrit avec les outils de terminale et les posts des autres contributeurs...

OShine

Sa vidéo manque de précision dans de nombreux détails, il va trop vite et passe sous silence des détails importants. 
Je ne comprends pas les gens qui disent qu'il explique bien, il ne démontre même pas le théorème donné pour résoudre le système.

Il explique tout vaguement et non rigoureusement.

Mais comment tu sais que le PPCM doit être conservé ? Je n'ai pas compris dans la pratique c'est où qu'on utilise l'isomorphisme de l'image avec $\Z / \mathrm{ppcm}(m,n) \Z$.

Je vais revoir cet exercice en cours particulier, il me pose trop de difficultés, c'est insurmontable.

Thierry Poma

@OShine : l'auteur des vidéos, dont celle qui nous concerne ici, ne manque nullement de précision ou de rigueur. Les détails y sont également. J'ai l'impression que l'auteur est intimidé, mal à l'aise. Je le serais également à sa place. La méthode qu'il propose est celle du Liret que tu as déposée en image sur ce site (je n'ai pas envie de chercher). La nouveauté que je trouve particulièrement efficace et rapide est la méthode de Lamé-Lucas pour déterminer très rapidement les coefficients dans une identité de Bézout. Voici une autre vidéo, où l'auteur détaille le tout. Il serait bien de l'enseigner aux Terminales. Arrête d'être de mauvaise foi, s'il te plait.

J'ai également visionné la partie théorique ; je me suis régalé.

troisqua

@Thierry Poma  : c'est l'algorithme d'Euclide étendu (je l'ai implémenté en Sage au dessus pour répondre à @gai requin ). J'ai montré sa convergence et détaillé le calcul de sa complexité en pire des cas dans un post récent : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2377677/#Comment_2377677

@Bisam a rajouté une remarque intéressante en rappelant qu'on pouvait s'autoriser des divisions à restes relatifs en valeur absolue inférieurs à la moitié du diviseur, ce qui améliore à un facteur près la complexité (mais on reste logarithmique). Le code de la méthode suggérée par Bisam a également été fourni. Bonne journée à toi.

Thierry Poma

@troisqua : j'avais abandonné ce fil depuis un certain temps. OS me gave. Je suis sur autre chose, en plus de ma recherche d'emploi. Je vais lire ta publication avec beaucoup d'intérêt. Le cas échéant, je te ferai un retour par MP, si tu es d'accord. Je te remercie beaucoup pour tes interventions.

OShine

@Thierry Poma 

Non le Liret ne donne pas ce théorème.

Dans la vidéo il ne la démontre pas et dit que c'est évident. 

De toute façon j'ai envoyé un mail à mon prof particulier pour qu'on fasse une séance sur cet exercice, il y a trop de choses qui me bloquent. En même temps je demanderai comment démontrer ce théorème.

lourrran

L'exercice final est sympa. ça me rappelle les jeux qu'il y avait dans le journal Ouest-France quand j'étais gamin. Pendant les mois d'été, il y avait des jeux comme ça. J'adorais ça quand j'avais 9 ou 10 ans.  

NicoLeProf

Oshine, le théorème des restes chinois dans le cas général est démontré dans cette vidéo et je trouve cela très bien expliqué avec un bel accent québécois : .

Cela constitue un très bon développement d'agrégation donc je la garde sous le coude. En espérant que tu comprennes bien et que cela te convienne.

troisqua

@NicoLeProf : ta vidéo est très bien pour lui.

Thierry Poma

@OShine : et l'image ci-dessous que tu as déposée sur ce fil, qu'en dis-tu ? Je ne te parle pas du théorème, mais d'une méthode développée dans le Liret et par l'auteur de la vidéo de manière similaire.

troisqua

@Thierry Poma  : oui mais ça, c'est du passé ! Il y a un processus de type "sans mémoire" dans ce genre de fil.

Thierry Poma

@OShine : pour ledit théorème, re-consulter les pages 92 et 93 du Liret, où une variante est donnée avec démonstration.

OShine

$\newcommand{\ppcm}{\mathrm{ppcm}}\newcommand{\pgcd}{\mathrm{pgcd}}$@NicoLeProf
Ok je comprends à peu près, même s'il y a quelques détails qui ne sont pas très bien expliqués.
Par exemple je ne comprends pas pourquoi si $x \sim y \mod  m$ alors il existe $c \in Z_m$ tel que $y+c \equiv x \mod  m$

Ok merci Thierry.
J'ai trouvé une solution pour la dernière question. Il existe un élément d'ordre $mn$ dans $\Z / mn \Z$ car $card (\Z / mn \Z)=mn$.
Soit $(x,y) \in \Z /m \Z \times \Z /n \Z$. Il existe un élément d'ordre inférieur à $\ppcm(m,n)$. En effet, $x$ est d'ordre inférieur à $m$ et $y$ inférieur à $n$. On a $mx=0$ et $ny=0$ donc $\ppcm(m,n) (x,y)=0$ donc l'ordre de $(x,y)$ divise $\ppcm(m,n)$.
Or, $\ppcm(m,n) = mn / \pgcd(m,n) <mn$ car $\pgcd(m,n) >1$ car $m$ et $n$ ne sont pas premiers entre eux.

Il n'existe aucun élément d'ordre $mn$ dans $\Z /m \Z \times \Z /n \Z$ il n'y a donc pas isomorphisme.

Ma difficulté principale repose sur les résolutions d'équations de congruence et le lien avec le théorème Chinois, je dois voir ça en cours particulier.

JLT

Si on est indulgent, on va dire que c'est très mal rédigé. Mais on a plutôt envie de dire qu'il y a des erreurs grossières.

NicoLeProf

OShine, tu n'as pas compris le but de la vidéo... Pourquoi si $x \equiv y \pmod m$ alors ... ? $x \equiv y \pmod m$ est ce que l'on veut prouver donc on ne va pas partir de cela.

Quant à $y \in \mathbb{Z}_m \Rightarrow \exists c \in \mathbb{Z}_m,\ y+c \equiv x \pmod M$, cela me paraît plutôt évident, regarde ce qu'il se passe quand $y=0$, $y=1$ ... $y=M-1$ et regarde ce que vaut $c$ à chaque fois . Approprie-toi la preuve en faisant des exemples au brouillon et en explicitant les détails !

Concernant la suite de ton post, c'est ce que troisqua avait fait donc bon (enfin, je rectifie, ce que troisqua avait fait en rédigeant parfaitement et de manière compréhensible pour le lecteur)... 

troisqua

@Oshine : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2378498/#Comment_2378498

Un extrait :

Qu'il est fatigant...

OShine

@NicoLeProf ok je ne suis pas très fan de la preuve de la vidéo.