Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. Reprise d'études-Ter ArithmétiqueTopics traitant de Arithmétique [tout]Lister tous les topics de mathématiques
Niveau Reprise d'études-Ter
Partager :

Congruence passage d'un modulo à un autre

Posté par
hbx360 24-08-21 à 09:43

Bonjour,

Dans cette exercice il est demandé de déterminé en fonction de 'n' le PGCD de 11n+3 et 13n-1.

J'ai regardé la correction qui est la suivante :

- Recherche d'une combinaison linéaire donc :
(11n + 3)(13) +  (13n-1)(-11) = 50

- Puis recherche les diviseurs de 50 :

soit D={1, 2, 5, 10, 25, 50}

- Ensuite on recherche si 11n + 3 et  13n-1 sont multiples de 50 simultanément :

\begin{cases} 11n + 3 \equiv 0 [50] \\ 13n - 1 \equiv 0 [50] \end{cases} et on trouve n \equiv 27 [50].

Puis on cherche si 11n + 3 et 13n - 1 sont multiple de 25 et on trouve n \equiv 2 [25].

Et c'est là, que je ne comprends pas, parce que dans la correction on ramène n \equiv 2 [25] à
n \equiv 2 [50] et n \equiv 27 [50].

Dans la correction c'est mis comme ça :

                                                                 n \equiv 2 [50]
n \equiv 2 [25]
                                                                 n \equiv 27 [50]

avec 2 flèches qui parte de n \equiv 2 [25] une qui va vers n \equiv 2 [50] et l'autre qui va vers n \equiv 27 [50]


Pourquoi on change le modulo, pourquoi passe t-on de modulo 25 à 50 j'ai du mal à comprendre et en quoi n \equiv 2 [25] est lié à n \equiv 2 [50] et n \equiv 27 [50]  et pour modulo 10 c'est pareil on ramène tout à modulo 50.

Je pensais qu'on avait pas le droit quand on fait des congruences de modifier le modulo. Qu'est-ce qui justifie que n \equiv 2 [25] est équivalent à n \equiv 2 [50] ?

Posté par
hbx360re : Congruence passage d'un modulo à un autre 24-08-21 à 09:49

A oui j'oubliais il met aussi les réponse comme suite :

Si n \equiv 27 [50] alors le PGCD = 50
Si n \equiv 2 [50] alors le PGCD = 25

C'est pareil c'est la 2e phrase qui me pose problème pourquoi il met n \equiv 2 [50] au lieu de mettre n \equiv 2 [25] puisqu'on cherche le pgcd pour modulo 25 ?

malou edit > ** balises Ltex rajoutées**

Posté par
hbx360re : Congruence passage d'un modulo à un autre 24-08-21 à 11:27

Merci malou  pour le rajout des balises.

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 11:53

tout simplement parce que 27 = 2 + 25 donc 27 = 2 [25] = 2 [50]

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 11:56

ha non pardon !!!

par contre on a :

n = 2 [50] => n = 2 [25]
n = 27 [50] => n = 2 [25]

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 11:59

et n = 2 [25] => n = 2 [50] ou n = 27 [50]

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 12:02

maintenant tu peux toujours vérifier en traduisant à chaque fois les congruences en "vraies" égalités :

n = 2 [50] <=> n = 2 + 50k avec k

et tu remplaces dans 11n + 3 et 13n - 1 ...

et idem avec les autres cas ...

Posté par
hbx360re : Congruence passage d'un modulo à un autre 24-08-21 à 14:19

Merci carpediem pour ta réponse.

Posté par
hbx360re : Congruence passage d'un modulo à un autre 24-08-21 à 14:24

Mais c'est ça que je ne comprends pas n \equiv 2 [50] => n \equiv 2 [25] pourquoi  n \equiv 2 [50] équivaut à n \equiv 2 [25].

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 15:05

il n'y a pas équivalence

27 = 2 [25] mais 27 2 [50]

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 15:08

peut-être une erreur du corrigé ...

il faudrait avoir le corrigé exact de la page ...

vu que tu as tapé l'énoncé éventuellement tu peux mettre le corrigé en image pour qu'on puisse voir exactement ce qui est écrit ...

(les modos nous ferons une remarque si ce n'est pas possible mais il me semble qu'il n'y a pas contre-indication dans la charte)

Posté par
carpediemre : Congruence passage d'un modulo à un autre 24-08-21 à 19:03

vu que le pgcd de a et b est 50 peut-être veut-il donner les valeurs de n modulo 50

si n = 27 + 50k alors

a = 11n + 3 = 50(6 + 11k)
b = 13n - 1 = 50(7 + 13k)

et on vérifie que 6 + 11k et 7 + 13k sont premiers entre eux

si n = 2 + 25k (comment cela est-il trouvé ?)

a = 11n + 3 = 25(1 + 11k)
b = 13n - 1 = 25(1 + 13k)

mais 13(1 + 11k) - 11(1 + 13k) = 2

effectivement  si k est impair alors 1+ 11k et 1 + 13k sont pairs dont multiples de 2

il en faut donc prendre que les k pairs

or n = 2 + 25k et k pair donne n = 2 + 50k donc n = 2 [50]

à toi de vérifier ce qui se passe lorsque n = 27 + 25k ...

Posté par
hbx360re : Congruence passage d'un modulo à un autre 25-08-21 à 10:13

Merci pour ton aide  carpediem, c'est une correction d'un exercice sur Youtube je donne le lien https://www.youtube.com/watch?v=aF6qrMRKjf0 il faut regarder à 6min.

En fait n \equiv 2 [25] => n \equiv 2 [50]  est une implication et non une équivalence .

Mais j'ai du mal à comprendre pourquoi n \equiv 2 [25] implique n \equiv 2 [50] ; pourquoi on passe de modulo 25 à 50.

Voici l'image de la vidéo à 6 min :

Congruence passage d\'un modulo à un autre

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 25-08-21 à 12:19

Bonjour,
Je me permets de répondre en l'absence des autres intervenants.

Citation :
Mais j'ai du mal à comprendre pourquoi n \equiv 2 [25] implique n \equiv 2 [50]
C'est normal que tu aies du mal à comprendre car c'est faux.
Regarde avec n = 27.

As-tu lu le message ci-dessous ?
carpediem @ 24-08-2021 à 11:59

et n = 2 [25] => n = 2 [50] ou n = 27 [50]

Il manque une flèche dans le corrigé avant le "27 [50]" tout en bas.

Posté par
hbx360re : Congruence passage d'un modulo à un autre 25-08-21 à 14:09

Merci de ton aide Sylvieg, oui j'ai lu son message , j'ai compris que qu'en on cherche n pour modulo 50 on a n \equiv 27[50]
mais je n'ai pas compris pourquoi qu'en on cherche n pour modulo 25 cela implique que n devient modulo 50.

J'ai pas compris pourquoi n \equiv 2[25] implique n \equiv 2[50] pourquoi passe t-on de modulo 25 à modulo 50 qu'est-ce qui justifie ce changement.

Pourquoi dans la solution (écris en rouge) on dit que si n \equiv 2[50] alors pgcd = 25 au lieu de dire si n \equiv 2[25] alors pgcd = 25 puisque l'on cherche n en fonction du modulo 25.

Je suis désolé si je n'arrive pas à exprimé ce que je veux dire en fait qu'est-ce qui justifie qu'on passe de n \equiv 2[25] à n \equiv 2[50].

Posté par
carpediemre : Congruence passage d'un modulo à un autre 25-08-21 à 14:17

carpediem @ 24-08-2021 à 19:03

vu que le pgcd de a et b est 50 peut-être veut-il donner les valeurs de n modulo 50

si on traite le cas de tous les pgcd possibles on obtiendra l'ensemble des résultats pour n en fonction d'un modulo 50 (et on aura bien traiter toutes les valeurs de n)

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 25-08-21 à 17:25

Citation :
J'ai pas compris pourquoi n \equiv 2[25] implique n \equiv 2[50]
J'ai déjà signalé que c'est faux.

Posté par
hbx360re : Congruence passage d'un modulo à un autre 25-08-21 à 20:33

Merci pour vos réponses.

Sylvieg @ 25-08-2021 à 17:25

Citation :
J'ai pas compris pourquoi n \equiv 2[25] implique n \equiv 2[50]
J'ai déjà signalé que c'est faux.


Oui en fait j'ai pas tout dis, donc je reformule n \equiv 2 [25] implique n \equiv2 [50] ou  n \equiv 27 [50].

Mais comme dis plus haut ce que je ne comprends pas c'est pourquoi on passe modulo 25 à modulo 50. Pourquoi on ne dis pas tous simplement que n \equiv 2 [25] ou n \equiv 27 [25].

Pourquoi dans la solution (écris en rouge) on ne dit pas tous simplement que si n \equiv 2 [25] alors pgcd = 25 ou n \equiv 27 [25] alors pgcd = 25 ?

Posté par
carpediemre : Congruence passage d'un modulo à un autre 25-08-21 à 22:27

et je répète pour la troisième fois

carpediem @ 25-08-2021 à 14:17

carpediem @ 24-08-2021 à 19:03

vu que le pgcd de a et b est 50 peut-être veut-il donner les valeurs de n modulo 50

si on traite le cas de tous les pgcd possibles on obtiendra l'ensemble des résultats pour n en fonction d'un modulo 50 (et on aura bien traiter toutes les valeurs de n)

Posté par
hbx360re : Congruence passage d'un modulo à un autre 25-08-21 à 22:53

Merci pour ta réponse carpediem

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 26-08-21 à 09:10

Bonjour,
@hbx360,
Après relecture de tes messages, je me demande si tu as compris que
n \equiv 2 [25] \; est équivalent à \; n \equiv 27 [25].

Posté par
hbx360re : Congruence passage d'un modulo à un autre 26-08-21 à 15:06

Bonjour Sylvieg, oui ça j'avais compris, ce qui me pose problème c'est pourquoi on passe de modulo 25 à modulo 50 comme sur la 1er image.

Ne devrait-on pas avoir plutôt comme sur la 2e image ?

Et au final au lieu d'avoir image 3 en conclusion avoir :

si n \equiv 27 [50] alors pgcd = 50
si n \equiv 2 [25] alors pgcd = 25

Congruence passage d\'un modulo à un autre

Congruence passage d\'un modulo à un autre

Congruence passage d\'un modulo à un autre

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 26-08-21 à 16:39

Citation :
si n \equiv 27 [50] alors pgcd = 50
si n \equiv 2 [25] alors pgcd = 25
C'est ce que tu voudrais avoir comme conclusion ?

Posté par
hbx360re : Congruence passage d'un modulo à un autre 26-08-21 à 17:42

* Modération > Citation inutile effacée. *

C'est juste que je ne comprends pas pourquoi la conclusion c'est
n \equiv 27 [50] alors pgcd = 50
n \equiv 2 [50] alors pgcd = 25

Alors que pour moi j'aurai plutôt mis
n \equiv 27 [50] alors pgcd = 50
n \equiv 2 [25] alors pgcd = 25 et pas modulo 50 puisqu'on cherche les n en fonction des diviseurs (50, 25, etc)

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 26-08-21 à 18:23

C'est bien ce que je pensais.
Si n 2 [25] alors le pgcd peut ne pas être 25 :
Regarde n = 52.

On peut avoir en même temps n 2 [25] et n 2 [50].
Pour que le pgcd soit 25, il ne faut pas que le pgcd soit 50.

Posté par
hbx360re : Congruence passage d'un modulo à un autre 27-08-21 à 08:45

Merci  Sylvieg pour ton aide.

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 27-08-21 à 08:57

De rien

Posté par
hbx360re : Congruence passage d'un modulo à un autre 27-08-21 à 09:04

Sylvieg @ 26-08-2021 à 18:23



On peut avoir en même temps  n 2 [25] et n 2 [50].


C'est ça que je n'ai pas compris pourquoi on peut avoir en même temps n 2 [25] et n 2 [50], est-ce que c'est la même chose ? Est-ce qu'il y a une règle qui permet de changer de modulo de passé de 25 à 50 ?

Dans l'image ci-dessous pourquoi on change le modulo ? On cherche pour modulo 25 la valeur de n donc 2 pourquoi ensuite dans l'image on met à droite de n 2 [25], n 2 [50]  et n 27 [50]  ? Puisqu'on a trouve n pour le modulo 25 pourquoi on le change en 50 ?

Je ne comprends pas aussi si on cherche n avec un modulo 25 pourquoi ensuite le modulo devient 50 comme ça s'en justification ?

Congruence passage d\'un modulo à un autre

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 27-08-21 à 09:38

Là, je commence à fatiguer un peu...
Si tu prenais un peu de distance avec ce corrigé mal fichu ?

Pour " n 2 [25] et n 2 [50] " :
Non, ce n'est pas la même chose.
27 vérifie l'un et pas l'autre.

Plutôt que de vouloir des règles, reviens au sens :
n 2 [50] signifie qu'il existe k entier tel que n = 50k + 2.
Donc si n 2 [50] alors il existe k entier tel que n = 252k + 2.
Donc n 2 [25].

Posté par
Sylvieg Moderateurre : Congruence passage d'un modulo à un autre 27-08-21 à 10:28

Pour l'exercice, il y a à priori 6 cas à envisager puisqu'il y a 6 pgcd possibles qui sont 1,2,5,10,25,50.

1er cas : pgcd = 50.
On trouve que c'est équivalent à n 27 [50].

2nd cas : pgcd = 25.
Pour ce cas, n ne doit pas être congru à 27 modulo 50.

Posté par
hbx360re : Congruence passage d'un modulo à un autre 27-08-21 à 12:08

Merci pour ta patience et d'avoir pris le temps de me répondre.

Sylvieg @ 27-08-2021 à 09:38


Si tu prenais un peu de distance avec ce corrigé mal fichu ?


Oui je crois que je vais faire comme ça. Merci pour ton aide.


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !