Théorème des restes chinois

En mathématiques, le théorème des restes chinois est un résultat d'arithmétique modulaire traitant de résolution de systèmes de congruences. Ce résultat, initialement établi pour Z/nZ, se généralise en théorie des anneaux. Ce théorème est utilisé en théorie des nombres. vignette|Exemple de Sun Zi : il y a 23 objets. La forme originale du théorème apparait sous forme de problème dans le livre de Sun Zi, le , datant du . Il est repris par le mathématicien chinois Qin Jiushao dans son ouvrage le Shùshū Jiǔzhāng (« Traité mathématique en neuf chapitres ») publié en 1247. Le résultat concerne les systèmes de congruences (voir arithmétique modulaire). Soient des objets en nombre inconnu. Si on les range par 3 il en reste 2. Si on les range par 5, il en reste 3 et si on les range par 7, il en reste 2. Combien a-t-on d'objets ? Cette énigme est parfois associée au général comptant son armée. La résolution proposée par Sun Zi pour ce problème est la suivante : Multiplie le reste de la division par 3, c’est-à-dire 2, par 70, ajoute-lui le produit du reste de la division par 5, c’est-à-dire 3, avec 21 puis ajoute le produit du reste de la division par 7, c'est-à-dire 2 par 15. Tant que le nombre est plus grand que 105, retire 105. Mais la solution n'explique qu'imparfaitement la méthode utilisée. On peut cependant remarquer que : 70 a pour reste 1 dans la division par 3 et pour reste 0 dans les divisions par 5 et 7 ; 21 a pour reste 1 dans la division par 5 et pour reste 0 dans les divisions par 3 et 7 ; 15 a pour reste 1 dans la division par 7 et pour reste 0 dans les divisions par 3 et 5. Le nombre 233 (2 × 70 + 3 × 21 + 2 × 15) a bien alors pour restes respectifs 2, 3 et 2 dans les divisions par 3, 5 et 7. Enfin, comme 105 (3×5×7) a pour reste 0 dans les trois types de division, on peut l’ôter ou l'ajouter autant de fois que l'on veut sans changer les valeurs des restes. La plus petite valeur pour le nombre d'objets est alors de 23.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (60)

En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne. L'idée de base de l'arithmétique modulaire est de travailler non sur les nombres eux-mêmes, mais sur les restes de leur division par quelque chose. Quand on fait par exemple une preuve par neuf à l'école primaire, on effectue un peu d'arithmétique modulaire sans le savoir : le diviseur est alors le nombre 9.

Traditionnellement, la théorie des nombres est une branche des mathématiques qui s'occupe des propriétés des nombres entiers (qu'ils soient entiers naturels ou entiers relatifs). Plus généralement, le champ d'étude de cette théorie concerne une large classe de problèmes qui proviennent naturellement de l'étude des entiers. La théorie des nombres occupe une place particulière en mathématiques, à la fois par ses connexions avec de nombreux autres domaines, et par la fascination qu'exercent ses théorèmes et ses problèmes ouverts, dont les énoncés sont souvent faciles à comprendre, même pour les non-mathématiciens.

Afficher plus

Cours associés (8)

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Study basic concepts of modern algebra: groups, rings, fields.

Afficher plus

Séances de cours associées (133)

Couvre les polynômes, leurs opérations, le théorème de division, et fournit des exemples illustratifs.

Couvre la fermeture algébrique de Qp et la définition des nombres complexes p-adiques, en explorant la dépendance continue des racines sur les coefficients.

Explore en profondeur les groupes cycliques, les générateurs, les isomorphismes et le problème du logarithme discret, en soulignant leur importance et leurs applications.

Afficher plus

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

Study basic concepts of modern algebra: groups, rings, fields.

Afficher plus

Couvre les polynômes, leurs opérations, le théorème de division, et fournit des exemples illustratifs.

Couvre la fermeture algébrique de Qp et la définition des nombres complexes p-adiques, en explorant la dépendance continue des racines sur les coefficients.

Explore en profondeur les groupes cycliques, les générateurs, les isomorphismes et le problème du logarithme discret, en soulignant leur importance et leurs applications.

Afficher plus