Classes de congruences

INDEX Théorie des nombres Types de nombres	Arithmétique – Modulo
	Introduction	Théorie	Propriétés	Formulaire
	Applications	Calculs	Carrés	Cubes
	Jeux	Sun Zi	Mod 9, 10, 11	Carrés et Cubes
	Parité	7 ^ 7 ^ 7	Log Modulaire	11¹⁰ = 32 mod 71
	Classes de congruence

CLASSES de CONGRUENCES

Problème de la couverture par ensembles

Nous avons vu comment classer les nombres selon les restes de leur division par k, comme avec pair et impairs pour la division par 2.

Cette page est consacrée à la recherche d'autres type de partage des nombres en familles, en classes.

La généralisation va nous conduire à comment compléter, à moindre coût, notre collection de cartes Pokémon. La solution de ces problèmes n'est pas simple …

Sommaire de cette page

>>> La classe des diviseurs de 12

>>> Extension

>>> Généralisation

Débutants

Opérations / Groupe

Glossaire

Nombres / Classes

Voir préalablement Base de la théorie

La classe des diviseurs de 12			haut
Mod 12	Avec la division par 12, l'ensemble des nombres est partitionné douze classes d'équivalence. L'ensemble est l'ensemble quotient de ℕ mod 12.
Mod (Div. de 12) Tout nombre est soit: = 0 mod 2 = 0 mod 3 = 1 mod 4 = 1 mod 6 = 11 mod 12	Initialisation du procédé Sur cet échantillon de nombres de 15 à 31, on calcule le reste de leur division par les diviseurs d de 12. Ce sont les nombres: d = {2, 3, 4, 6, 12}. Par exemple 15 divisé pat 12 a 3 pour reste. On écrit: Identification des couples On cherche une configuration associant d à un reste pour couvrir toutes les lignes. Il est naturel de cocher (jaune) toutes les lignes avec 0 pour reste avec la division par 2 ou par 3. On a les couples: (2, 0) et (3, 0). Avec 4, pour cocher d'autres lignes, prenons le reste 1. Soit le couple (4, 1). Avec le 6, idem. Soit le couple (6, 1). reste une ligne non cochée de jaune, celle du 23 où la division par 12 donne 11 pour reste. Soit le couple (12, 11).
Système de congruence avec les diviseurs de 12 Les classes ne sont pas disjointes: le nombre 6 appartient à la classe 2 comme à la classe 3, par exemple.	Avec ces cinq couples (2, 0), (3, 0), (4, 1), (6, 1) et (12, 11), nous couvrons tous les cas de l'échantillon. Une recherche plus complète montre que c'est le cas pour tout nombre. Liste pour n de 1 à 50 [1, 6], [2, 2], [3, 3], [4, 2], [5, 4], [6, 3], [7, 6], [8, 2], [9, 4], [10, 2], [11, 12], [12, 3], [13, 6], [14, 2], [15, 3], [16, 2], [17, 4], [18, 3], [19, 6], [20, 2], [21, 4], [22, 2], [23, 12], [24, 3], [25, 6], [26, 2], [27, 3], [28, 2], [29, 4], [30, 3], [31, 6], [32, 2], [33, 4], [34, 2], [35, 12], [36, 3], [37, 6], [38, 2], [39, 3], [40, 2], [41, 4], [42, 3], [43, 6], [44, 2], [45, 4], [46, 2], [47, 12], [48, 3], [49, 6], [50, 2]
Liste des nombres de 1 à 100 par appartenance à sa plus grande classe.		2: {2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46, 50, 52, 56, 58, 62, 64, 68, 70, 74, 76, 80, 82, 86, 88, 92, 94, 98, 100} 3: {3, 6, 12, 15, 18, 24, 27, 30, 36, 39, 42, 48, 51, 54, 60, 63, 66, 72, 75, 78, 84, 87, 90, 96, 99} 4: {5, 9, 17, 21, 29, 33, 41, 45, 53, 57, 65, 69, 77, 81, 89, 93} 6: {1, 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, 73, 79, 85, 91, 97} = 6n + 1 12: {11, 23, 35, 47, 59, 71, 83, 95} = 12n + 11

Anglais: Covering set

Extension

IL existe effectivement quelques autres nombres présentant cette propriété.

Tous les nombres peuvent être partagés en classes d'équivalence avec les diviseurs des nombres B =

{12, 120, 720, 2520, 10 080, 30 240, 75 600, 604 800}.

Tout entier n vérifie l'une des congruences:

Les couples (d_i, m_i) sont formés de nombres d_i (par exemple les diviseurs) de B, et des résidus appropriés m_i tous allant en croissant.

Davenport en 1952 cité par Le Lionnais

Généralisation

La généralisation fait partie du problème de la couverture par ensemble (Set cover problem):

Un ensemble E et des sous ensembles S

On cherche à couvrir tous les éléments de E par ceux de S

Si, c'est le cas, on cherche le lot minimal de sous-ensembles S couvrant tous les éléments de E.

Exemple un ensemble E donné de nombres entiers et un sous-ensemble de nombres premiers S tels les éléments de E sont divisibles par l'un au moins des éléments de S.

Exemple concret: Nathan a une collection de cartes Pokémon. Il souhaite la compléter avec des lots de cartes du commerce. Le lot comprend des cartes qu'il souhaite et aussi des cartes qu'ila déjà. Son problème consiste à couvrir toute la collection avec un minimum de lots à acheter.

Suite Retour	Modulo Carrés modulo 4 et 8 Approche Groupe des entiers modulo 4 avec addition (Z₄) Tour de magie avec les modulos
Congruence	Voir en tête Clé de divisibilité, une application de la théorie du modulo Log Modulaire Nombres congruents Résidus quadratiques Application à la puissance 11 Congruence avec trigonométrie
Voir	Application à la factorisation Calcul mental – Index Divisibilité Exemple d'application du modulo en Codage RSA Fractions et horloges Géométrie – Index La division Nombres Cycliques	Nombres de Carmichaël Nombres Premiers Nombres Rationnels Preuve par 9 – Glossaire Pseudo Premiers Pseudo Premiers Absolus Théorie des nombres – Index
Livre	Algèbre 1 – Cours et 600 exercices corrigés – 1^re année MPSI, PCSI, PTSI – Jean-Marie Monier – Dunod – 1996
Sites	Problème de la couverture par ensembles – Wikipédia Covering set – Wikipedia OEIS A016921 – a (n) = 6n + 1 OEIS A017653* – a(n) = 12n + 11 – Nombre égaux à 1 mod 12 – Nombres égaux à 2 mod 3 et à 3 mod 4* Résolution du Set Covering Problem** – Delorme
Cette page	http://diconombre.fr/ThNbDemo/ModClass.htm