NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 29/03/2021

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths

       

Arithmétique

 

Débutants

Opérations

MODULO

 

Glossaire

Nombres

 

 

INDEX

 

Théorie des nombres

 

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

Cas de 2^33 et 2^99

Magie

Terminale S

 

Sommaire de cette page

>>> Pièces de monnaies

>>> Grand nombre …

>>> Un peu  d'astuce avec les grands nombres

>>> Algorithme de calcul modulaire rapide

>>> Méthode de calcul de restes sur grands nombres

>>> Exemple avec l'année 2021

 

 

 

 

 

  

CONGRUENCES

Exemple de calculs

Algorithme de calcul modulaire

 

 

 

PIÈCES DE MONNAIE

 

Utilisation des congruences (modulo)

pour résoudre un problème de pièces de monnaie

 

J'achète 351 euros avec un lot de pièces de 17 et 18 euros.

Combien de pièces de chaque?

 

On pose l'équation

18 x + 17 y

= 351

On cherche une solution simple, en utilisant le fait que 17 et 18 sont deux nombres consécutifs

18 – 17

18 x 351 – 17 x 351

=     1

= 351

Retranchons membre à membre  les deux équations

18 x + 17 y

18 x 351 – 17 x 351

= 351

= 351

Résultat

18(x - 351)

= – 17(y + 351)

Et pour x

x

= – 17(y + 351)/18 + 351

Si on divise x par 17, on obtient les restes suivants (x mod 17)

x mod 17

= 0 + 351 mod 17

Or, le reste de 351 par 17 est 11

x mod 17

= 11

Autrement dit x est un multiple de 17 plus 11

x

= 17 k + 11

Même chose pour y

y

= – 18(x - 351) /17   – 351

En reste par 18

y mod 18

= 9 (ou -9)

Valeur de y

y

= – 18 k' + 9

Essayons k= k' = 0

18 x 11 + 17 x 9

= 198 + 153 = 351

Avec d'autres valeurs, on trouve des valeurs trop grandes pour x ou négatives pour y

18 x 28 + 17 x 9

18 x 11 – 17 x 9 

= 657

= 45

Seule solution

x = 11

et y = 9

 

 

 

Grand nombre …

 

Démontrez que N = 101 million + 10 est divisible par 13

 

Avec 10, il manque 3 pour arriver à 13.

Élévation au carré.

Effectivement 100 = 7x13 + 9

Poursuivons en prenant le cube.

Super! Car le 1, élevé à une puissance quelconque, donne toujours 1.

Pour approcher le million proposé en exposant.

L'exposant est impair, le signe moins est conservé.

En multipliant par 10.

Reste à ajouter 10 pour avoir N.

 

Exemple donné par Malcom Lines dans: Dîtes un chiffre – Champs Flammarion - 1990

 

Un peu  d'astuce avec les grands nombres

Calculer le reste de la division par 5 de 20092009

On note que

Or, 2009 = 3 x 669 + 2

Calculer le reste de la division par 5 de 20092009

On note que 2009 = 2010 – 1
avec 2010 divisible par 5

Rapidement, on obtient:

Vérification par logiciel de calcul

 

 

 

Algorithme de calcul modulaire rapide

Particulièrement utile pour calculer les congruences avec grand exposants (test de Fermat)

 

Son Principe

 

1)   Calculer les congruences au fur et à mesure
Fastidieux, s'il faut répéter 100 fois.



 

Calculez

?

 

Base de la méthode

On pourrait calculer au fur et à mesure

Etc.

2)   En profitant d'une décomposition en puissance de 2 pour accélérer le calcul

 

Accélération avec les puissances de 2 

100 = 64 + 32 + 4

        = 26 + 25 + 22  (1100100 en binaire)

 

 

Algorithme

 

Calcul de:  ab mod n

 

(x, y, z ) = (a, b, 1) – Initialisation

Boucle jusqu'à y = 0

  Si y est pair     (x, y, z) = ( x² mod n, y/2, z mod n)

  Si y est impair (x, y, z) = ( x² mod n, (y-1)/2, x.z mod n)

Résultat = z.

 

 

Commentaires

 

Initialisation d'un triplet (x, y, z) avec a et b et z = 1 pour commencer. Z sera le résultat du calcul.

Lancement de la boucle ave while (tant que).

Le nouveau triplet (x, y, z) est calculé selon les valeurs indiquées dans l'algorithme.

Notez que dans le cas impair, la valeur de x est nécessaire pour calculer z. On prend soin de calculer z avant le nouveau x.

Pour illustrer le calcul on imprime les résultats intermédiaires.

 

Résultats

 

Notez que dans les résultats intermédiaires, la première colonne donne x avec ses valeurs pour 17 mod (successivement 1, 2, 4, 8, 16, 32, 64 et 128).

La deuxième colonne montre 100 divisé par 2 (valeur entière).

La troisième montre le calcul progressif du modulo.

 

Autre exemple (programme et calcul direct)

Voir ProgrammationIndex

 

 

Méthode de calcul de restes sur grands nombres

Calcul d'une puissance mod m.

Le calcul est accéléré

en profitant de cette relation

 

Exemple: 31304 (mod 121)

 

Étape 1 – Ligne 1: remplir les cellules de gauche à droite en commençant par l'exposant (1304). Si le nombre est pair, le suivant est sa moitié; sinon soustraire 1.

 

k

1304

652

326

163

162

81

80

40

20

10

5

4

2

1

 

(3652

(3326

(3163

3·3162

(381

3·380

(340

(320

(310

(35

243

81

9

3

3k [121]

27²

3·9

3·1

 

 

 

 

 

81

9

3

27

9

3

1

1

1

1

1

81

9

3

 

Étape 2 – Lignes 2, 3 et 4: on inscrit dans chaque cellule la valeur de 3nombre du haut mod 121.

Le calcul est simplifié en remplissant les cellules de droite à gauche (donc dans l'autre sens). On profite des résultats précédents. Exemple: 310 = 35x2 = (35)² soit (1)² en mod 121.

 

Vérification avec logiciel de calcul

 

 

Exemple avec l'année 2021

Calculer le reste de la division par 13 de 20212021

Premier pas

Reduire la base 2021

2021 = 155 x 13 + 6

Conversion en binaire de 2021.

 

On se souvient que
210 = 1024

En colonnes centrales toutes les puissances de 2 inférieures à 2021.

En colonne de gauche, le nombre N puis sa valeur diminuée des valeurs successives de 2k. Si le résultat reste positif, un 1 est placé en colonne de droite (binaire). Sinon, on conserve la valeur et on place un 0 à droite.

La colonne de droite (B) indique la conversion en binaire de 2021.
202110 = 111 1110 01012

Avec les puissances de 2

Attention

Voir Puissances à étages

Calcul des puissances de 6 mod 13

ð [6, 10, 9, 3, 9, 3, 9, 3, 9, 3, 9]

Multiple de 13

13, 26, 39, 52, 65, 78, 91, 104, 117, 130, …

Retour au calcul demandé

Année 2021 en modulo

2021 = [0, 1, 2, 1, 1, 5, 5, 5, 5, 1, 8, 5, 6, 5, 11, 5, 15, 5, 7, 1]   mod (1, 2, 3,.., 13, …, 20)

20212021 = [0, 1, 2, 1, 1, 5, 3, 5, 2, 1, 8, 5, 2, 3, 11, 5, 2, 11, 11, 1]   mod (1, 2, 3,.., 13, …, 20)

Voir Nombre 2021

 

 

 

 

 

 

Suite

*    Problème de Sun Zi – Autre exemple de calculs

*    Puissances de 2 mod 641

*    Cas de 2^33 et 2^99

Voir

*    JeuxIndex

*    Équations

*    Divisibilité

*    Clé de divisibilité, une application de la théorie du modulo

*    La division

*    Exemple d'application du modulo en Codage RSA

*    Nombres pseudo-premiers

Aussi

*    Calcul mental

*    Géométrie

*    Nombres Premiers

*    Nombres Rationnels

*    Preuve par 9Glossaire

*    Théorie des nombres

*    Variations sur les carrés

Cette page

http://villemin.gerard.free.fr/ThNbDemo/ModExemp.htm