Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 03/01/2021

M'écrire

Brèves de Maths

 

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

1110 = 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 (di, mi) sont formés de nombres di (par exemple les diviseurs) de B, et des résidus appropriés mi 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 (Z4)

*    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 mentalIndex

*      Divisibilité

*      Exemple d'application du modulo en Codage RSA

*      Fractions et horloges

*      GéométrieIndex

*      La division

*      Nombres Cycliques

*      Nombres de Carmichaël

*      Nombres Premiers

*      Nombres Rationnels

*      Preuve par 9Glossaire

*      Pseudo Premiers

*      Pseudo Premiers Absolus

*    Théorie des nombresIndex

Livre

*    Algèbre 1 – Cours et 600  exercices corrigés – 1re 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) = 6*n + 1

*      OEIS A017653 – a(n) = 12*n + 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://villemin.gerard.free.fr/ThNbDemo/ModClass.htm