Z/nZ 5 : Théorème des restes chinois version pratique
Vložit
- čas přidán 27. 07. 2024
- Version plus utile pour résoudre les problèmes posés en exercices !
Les diapos sont ici :
docs.google.com/presentation/...
Merci aux tipeurs (fr.tipeee.com/maths-adultes) :
Paul, Valoukanga
Un immense merci!!! Pour l'ensemble de vos formidables vidéos bien sur, mais aussi et surtout pour la méthode de Lamé-Lucas!!!!
Tout cela m'est d'une grande aide dans mes révisions de concours!
Bon sang, cette méthode Lamé Lucas ! Quelle trouvaille !
Juste énorme. Ce petit problème de famille au départ, détonnant dans sa résolution
Merci, bientôt dans tous les manuels la méthode de Lamé-Lucas.
j'ai devoir ce soir et j'avoue que votre vidéo me fait du bien merci beaucoup
Cré bon sang d'bon soir, pourquoi ne trouve-t-on pas la méthode de Lamé-Lucas dans tous les cours sur les équations diophantiennes... Que c'est simple ainsi !
MERCI, je ne connaissais pas ce Lamé-Lucas, eh oui on apprend toujours
Méthode Lamé-Lucas, n'existe même pas sur Wikipédia !
Merci pour ce partage !
Je ne connaissais pas cette méthode de Lamé-Lucas, elle est très pratique! Je vais la montrer à mes élèves de Maths expertes!
oui c'est chouette !
Pareil
merci ! super clair !!
Super video. Merci
MERCI !
Merci encore :-)
Merci!
Impressionnant le théorème de Lamé-Lucas. Je ne vois plus comment m'en passer quand je cherche les coefficients de Bezout.
Thank U so much
Pourquoi n'avez vous pas réduit [8] en [4] pour simplifier les calculs?
Merci pour l'algo de Lamé Lucas. Une forme bien plus agréable que l'originale.
Car on perds de l’information car un nombre congrus a 3 [4] n’est pas forcément congrus à 3[8]
je pense qu'à l'énoncé de l'exercice il fallait mettre au plus 160 eleeves, pour mettre x
Félicitations pour ces explications, parfaitement limpides, très pédagogiques !
Petite question : je ne trouve rien sur la méthode de Lamé-Lucas qui est exquise. Je voulais en savoir un peu plus dessus. Auriez vous des infos ?
Merci
Non pas du tout désolé...
Bonjour Monsieur, je vous remercie pour vos vidéos ! Je viens de les découvrir et elles m'aident beaucoup pour préparer l'agrégation ! Auriez vous une référence de livre pour la méthode de Lamé-Lucas, s'il vous plait ?
malheureusement non...
@@MathsAdultes Je vous remercie pour votre réponse rapide !
Bonjour. En voulant résoudre le pb du mariage, j'ai réduit au maximum, en arrivant à x~1[2]~1[3]~1[7] (~pour le symbole de congruence). Ce qui me conduit à des solutions modulo 42. Et j'en trouve ainsi 3. à savoir 211 (gagné ^^ ) mais aussi 253 et 295. :s Du coup, après, il faut vérifier quelle est la bonne en vérifiant les modulos 8, 12 et 14, mais est-ce acceptable comme méthode?
tout à fait !
Bonjour, dans quel livre peut-on trouver la formule qui tue? avec démonstration?
j'en donne une preuve là en fait mais sinon c'est dans "arithmétique et cryptologie" chez ellipses ;-)
Avez vous une référence également pour vos exemples interessants?
@@MathsAdultes je n'ai pas vraiment compris d'où elle sort ni le rapport avec les restes chinois.
Bonjour Monsieur
J'informe Monsieur que la résolution des systèmes linéaires de types plus général c'est à dire de type
Ai x_= Bi [mod Mi] , i=1 à n (i étant un indice)
au moyen de mon schéma : le schéma d'OURAGH.
Exemple
37x_=12[mod 137]
21x_=5[mod 89]
11x_=8[mod 43]
3x_=17[mod 23]
qui peut se faire en moins de cinq minute et ce en trois lignes et une relation qui suivra.
Pour le dernier exemple que vous avez résolue je vous invite à regarder la solution au moyen du schéma d'Ouragh
7:::::::9::::::7::::::2:::::::1::::::63:::::::11:::::::8:::::::3::::::2::::::1::::::693::::::13:::::::4:::::::1
:::::::::0::::::-1::::-3:::::::0:::::::0:::::::::-5::::::-1:::::::-2::::-1::::::0:::::::::0:::::::-53::::::-3
::::::::-3:::::::4::::-3:::::::1::::::-4:::::::::23:::::-4:::::::3:::::-1::::::1::::::::-3::::::160:::::-3:::::::1
Et il vient donc
x_=Partie décimale de { (-3*1*23*160/7)+(4*2*23*160/9)+(-4*3*160/11)+(-3*4/13)}*7*9*11*13
soit
x_=4502[mod 7*9*11*13]
Le tableau précédent a été obtenu en moins de 4 mn:
Ce schéma permet aussi (avec la même technique ) de résoudre par exemple une équation diophantienne polynomiale de type
A(x) u(x) + B(x) v(x) = C(x) ou C(x) est divisible par PGCD(A,B).
Cordialement.
C'est étrange, cette méthode de Lamé-Lucas je la connaissais sous le nom d'algorithme d'Euclide étendu, est-elle vraiment dû à Lamé-Lucas ?
Oui je te confirme bien que c'est grâce à lui
Dommage de ne pas démontrer la formule qui tue.
😀👍💐🇩🇿😇
A l'aide ! Et si j'ai: x ≡ 1 mod 12 et 2x ≡ 20 mod 45
c'est quoi la méthode générale pour le résoudre avec la méthode chinoise ? Je n'y arrive pas car 12 et 45 ne sont pas premiers entre eux (leur pgcd est 3).
comme 2 est inversible modulo 45 tu a x ≡ 10 mod 45
tu résous y ≡ 1 mod 4 et y ≡ 10 mod 45 tu trouves y = 145 + 180k et donc (coup de bol) on a
y ≡ 1 mod 12 pour toutes les valeurs de k donc finalement x = 145 + 180k avec k dans Z.
Bonjour Monsieur,
À 27:55 , vous nous dîtes que toutes les solutions du nouveau système de congruence que l’on a mis en évidence (qui nous arrange bien car nous pouvons le résoudre grâce au théorème des restes chinois), seront solutions du système de congruence qui traduit la situation du mariage. Êtes-vous bien sûr de ceci ? Je vous explique ci-dessous d’où proviennent mes doutes, en espérant que vous pourrez corriger d’éventuelles erreurs dans mon raisonnement.
Après avoir appuyé sur pause pour tenter de résoudre l’exercice, je me suis retrouvé avec le système de congruences :
x congru à 1 (modulo 2) (vous avez gardé x congru à 3 modulo 8, mais cela semble cohérent)
x congru à 1 (modulo 3)
x congru à 1 (modulo 7)
Remarque : à ce stade, je n’ai pas cherché à démontrer l’équivalence entre le système découlant de la situation du mariage, et mon nouveau système. J’ai juste constaté que les hypothèses pour appliquer le théorème n’étaient pas vérifiées pour résoudre le système initial : je me suis débrouillé pour qu’elles le deviennent dans le nouveau système, et je me suis attelé à résoudre celui-ci sans réfléchir…
Mon système admet x = 1 (modulo 42) comme unique solution d’après le théorème des restes chinois. Or, force est de constater que toutes les solutions de ce système de congruence ne sont pas forcément solutions du système de congruence initial, celui qui traduit la situation de notre mariage. Pour x entre 200 et 300, j’ai 211,253,295 qui sont congrus à 1 modulo 42. Or, seul 211 fonctionne pour le cas de figure du mariage.
En réfléchissant un peu, j’ai remarqué que la réciproque de « si x congru à 7 modulo 12, alors x congru à 1 modulo 3 » n’est pas vraie ( 4 est congru à 1 modulo 3, mais pas à 7 modulo 12). Tout ceci me fait postuler que, bien que toutes les solutions du système de congruence initial seront bien des solutions du système « qui nous arrange » (celui-ci qui nous permet d’utiliser le théorème des restes chinois), la réciproque ne sera pas vraie : seul un sous-ensemble de l’ensemble des solutions de notre nouveau système fonctionnera pour le système initial. Qu’en pensez-vous ?
Remarque supplémentaire : l’ensemble des solutions de mon système est S = {42q+1, q entier relatif}
Et je constate, sans pouvoir l’expliquer, que le sous-ensemble de S qui contient les solutions qui fonctionnent aussi pour le système directement issu de la situation du mariage, est S’ = {42q+1, q entier relatif congru à 1 modulo 4} = {43 + 168q’, q’ entier relatif}.
S’ est exactement l’ensemble des solutions que vous trouvez dans la vidéo avec votre système de congruence ! (en gardant x congru à 3 modulo 8 au lieu de prendre x congru à 1 modulo 2). S’agit-il d’une coïncidence ou est-ce que quelque chose m’échappe ?
Bonne journée et merci infiniment pour tout ce que vous faites.
vous avez parfaitement compris, on ne trouve que des conditions nécessaires sur les solutions du système, il faut ensuite vérifier si elles conviennent au système initial ou pas...
@@MathsAdultes Merci bien. Ça valait vraiment le coup d’appuyer sur pause :)
Bonsoir
Inverse de 17 modulo 360 peut être déterminer comme suite
360:::::::17::::::::3:::::::2:::::::1
:::::::::::: -21 :::::-5:::::::-1
::::::::::::-123::::::6::::::::-1::::::1
et l'inverse de 17 modulo 360 est 360-123=237 très simplement.
Cordialement.
-6*21-1=-127 et donc je corrige 360-127=233
Je regrette monsieur on peut bien faire beaucoup plus facilement au moyen du schéma d'OURAGH. Avec un tel schéma
On peut résoudre tout système linéaires d'équations linéaires.
MERCI POUR LA METHODE DE LAME LUCAS !!!!!!!!!!
Bonsoir Monsieur
J'informe votre honneur qu'avec le schéma d'Ouragh on peut faire beaucoup mieux et est plus générale.
Bonsoir,
Résolution du système x_=3[8] , x_=7[12] , x_=1[14] . Ce système se transforme facilement en
47x_=5[168] et donc on cherchera l'inverse de 47 modulo 168. Pour cela on utilisera le schéma d'Ouragh
168:::::::47:::::::::27::::::::20::::::::7:::::::::6::::::::1
:::::::::::::::-3:::::::::-1::::::::::-1::::::::-2:::::::-1
::::::::::::-25:::::::::::7:::::::::-4:::::::::3::::::::-1::::::::1
Cet inverse est 168-25=143
Alors il vient x_=5*143[168]_=715[168]_=43[168]
Très simplement.
Cordialement.
On aura x compris entre 200 et 300 comme suite x=43+168=213
43+168=211 et non 213
Mr6