LaboraToile MATh.en.JEANS. Année 2001-2002

Les divisions justes

sujet 02C02 proposé par Pierre Duchet

Comment savoir si un nombre en divise un autre sans faire la division

 

Lorsque que l'écriture décimale d'un nombre se termine par 0 ce nombre est divisible par 10. Voila le plus simple des "critères de divisibilité" : on peut savoir si une division va tomber juste sans la faire (bien que dans le cas d'une division par 10, la division soit ridiculement facile à effectuer).

Autre exemple : un nombre est divisible par 2 si et seulement si il se termine par l'un des chiffres pairs : 0,2,4,6,8. Là encore, on peut savoir si la division tombe juste sans la faire.

Saurez-vous trouvez de bons critères de divisibilité par 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... ?

Les méthodes devront être le plus simples possible : en tout cas il s'agit d'être nettement plus rapide qu'un calculateur qui effectuerait la division, avec quotient et reste : la division usuelle (euclidienne) d'un nombre à p chiffres par un nombre à q chiffres nécessite p-q +1 multiplications et p-q +1 soustractions (en général).

Que se passe-t-il dans d'autres systèmes de numération ?

Par exemple dans les bases 2, 3, 5, 7 , 12, 60 ?

 

Entrées possibles

 

A quoi cela sert-il ?

La transmission secrète des informations numérisées (images numériques, cédéroms et dévédéroms, télévision par satellite, réseaux téléphoniques et internet,...) repose sur l'utilisation de codes secrets, mis au point par des mathématiciens. Les meilleures méthodes connues utilisent de grands nombres qui ont exactement deux diviseurs non triviaux (autres que 1 et le nombre lui-même) : la connaissance du nombre seul ne permet pas de trouver ses diviseurs, car ... on ne sait pas le faire dans un temps raisonnable, même avec des ordinateur puissants.

Savoir trouver rapidement les diviseurs d'un nombre, est ainsi l'un des grands problèmes qui occupe les théoriciens des nombres. Une méthode, très lente, consiste à essayer toute les divisions possibles : dès que l'une tombe juste, on a trouvé un diviseur. La recherche de méthodes plus rapides repose en partie sur la compréhension de la répartition des nombres premiers (ceux qui n'ont d'autres diviseurs que 1 et eux-mêmes) mais bénéficierait aussi de tout progrès décisif sur les propriétés de divisibilité.

La recherche de critères de divisibilité d'un nombre par un autre est l'une des parcelles de cet immense champ d'investigation.

Documentation


Début

Sujets collèges
Sujets du LaboraToile