NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Atlas / Références /    Nouveautés

ORIENTATION GÉNÉRALE    -   M'écrire   -   Édition du: 09/03/2011

Débutants

Opérations

Arithmétique

Glossaire

Nombres

 

MODULO

 

Index des pages

Arithmétique et Théorie des nombres

 

>>> INDEX

Introduction

Mod 9, 10, 11

Applications

Jeux

Théorie

Carrés

Propriétés

Calculs

7 ^ 7 ^ 7

 

Sommaire de cette page

>>> Mise en jambe sur exemples simples

>>> Divisibilité de 77 par 11

>>> Divisibilité de 711 k par 11

>>> Cas de (77)7

>>> Cas de 77^7

 


  

 

CONGRUENCES

Exemples de calculs

Avec les puissances à étages de 7

 

Le petit théorème de Fermat associé au monde du modulo permet des calculs sur de très grands nombres sans à avoir à calculer la valeur de ce nombre.

 

 

 

Mise en jambe sur exemples simples

 

*      Se familiariser avec le petit théorème de Fermat:

 

 

Exemples

25 = 2 mod 5

37 = 3 mod 7

 

 

*      Voici deux exemples simples pour illustrer le calcul généralement pratiqué sur des cas plus complexes.

 

 

 

*    Est-ce que 30 est divisible par 5?

30 = 32 – 2

     = 25 – 2

En modulo 5 cela devient:

30  2 – 2 mod 5

      0      mod 5

Oui! 30 est divisible par 5.

 

*    Est-ce que 2 184 est divisible par 7?

2 184 = 2 187 – 3

         = 37 – 3

En modulo 7 cela devient:

2 184   3 – 3 mod 7

           0      mod 7

Oui! 2 184 est divisible par 7.

 

 

 

 

Divisibilité de 77 par 11

Remarque

 

7 n'est pas divisible par 11

7 x 7 = 49 non plus

7 x 7 x 7 = 343 = 11 x 31 + 2 non plus

Ensuite ?

 

Fermat à l'œuvre

 

7 x … x 711 fois = 711  7 mod 11

Avec la puissance 11, Fermat permet de conclure.

Un paquet de 7 multiplié 11 fois par lui-même, divisé par 11, donne 7 pour reste

Examen

 

 

Pour information, valeurs de 7n

 

1, 7

2, 49

3, 343

4, 2 401

5, 16 807

6, 117 649

7,  823 543

8, 5 764 801

9, 40 353 607

10, 282 475 249

11, 1 977 326 743

 

 

 

 

 

71                     7   mod 11

72                    5   mod 11

73                    2   mod 11

74                    3   mod 11

75                    10   mod 11

76                    4   mod 11

77                    6   mod 11

78                    9   mod 11

79                    8   mod 11

710                   1   mod 11

711                   7   mod 11

Seules les puissances 1 et 11 donnent 7 pour reste.

Aucun résidu nul.

 

Aucune de ces puissances n'est divisible par 11.

Pour l'exemple, calculons le résidu de 77

 

 

Ce nombre vaut:

823 543

 

 

 

 

n = 77 Quel est le reste de la division par 11 ?

On peut écrire ce nombre: 711-4

Qui vaut: n = 711 / 74

Avec Fermat: 711  7 mod 11

Calcul de 74 = 2401 = 11 x 218 + 3  3 mod 11

Retour à n = 711 / 74  7 / 3 mod 11

Pour obtenir une division qui tombe juste, il faut ajouter 1 fois 11 au numérateur, ce qui ne change pas la valeur en modulo 11:

n   (7 + 11) / 3  18 / 3

n = 77  6 mod 11.

 

 

 

Divisibilité de 711k par 11

Avec Fermat, nous savons

 

7 x … x 711 fois = 711  7 mod 11

 

711  7   mod 11

 

k paquets

de 11

 

 

 

722 = 711 + 11 = 711 x 711

                 7  x 7   mod 11

                 49   mod 11

Or 49 = 11 x 4 + 5

       722      5   mod 11

 

733 = 711 + 11 + 11 = 711 x 711 x 711

                 7  x 7 x 7  mod 11

                     5    x 7   mod 11

Or 35 = 11 x 3 + 2

        733     2   mod 11

 

Conclusion

 

777 =

118 181 386 580 595 879 976 868 414 312 001 964 434 038 548 836 769 923 458 287 039 207

= 0,11 1066

 

 

Le résidu de 711k est celui de 7k

 

Ainsi 777 = 77 x 11  77  6 mod 11

Puissance K

de 7

On peut toujours exprimer K la puissance de 7 par K = 11k + q avec q = {0 à 10).

Or, en modulo 11, le 11 k donnera des produits de 7 (7K1) et q ne donnera jamais 0 comme résidu.

À son tour 7K1, en modulo 11,  donnera des produits de 7 (7K2) et q ne donnera jamais 0 comme résidu.

Etc.

7K n'est pas divisible par 11.

 

 

 

Cas de (77)7 par 11

Grand nombre!

 

 =

256 923 577 521 058 878 088 611 477 224 235 621 321 607

= 0,25 1042

 

 

Que dire de n = (77)7  modulo 11?

n = (77)7  = (77)(11-4) = (77)11 / (77)4

 

N = (77)11  77 mod 11  6 mod 11

D = (77)4  (6)4 mod 11

             = 1 296 mod 11

             = 117 x 11 + 9  9 mod 11

 

n = N / D  6 / 9  6 + 6 x 11/9 = 8

n = (77)7   8 mod 11

 

 

 

 

Cas de 7(7^7) par 11

Grand nombre!

 

=

0,37 10695 975

 

Presque

700 000 chiffres!!!

 

 

 

 

 

 

 

 

 

 

Que dire de n =   modulo 11?

Je crains qu'il faille calculer 77 = 823 543 pour y chercher les paquets de puissance 11.

 

Sa division par 11: 823 543 = 11 x 74 867 + 6

n = 7 11 x 74 867  x 76

n  7x7x … x 774 867 fois   x 76

 

Or 74 867 = 11 x 6806 + 1

n  711 x … x 711 6 806 fois  x 7 x 76

n  7 x … x 7 6 806 fois  x 77

 

Or 6 806 = 11 x 618 + 8

n  711 x … x 711 618 fois  x 78 x 77

n  7 x … x 7 618 fois  x 715

 

Or 618 = 11 x 56 + 2

n  711 x … x 711 56 fois  x 72 x 715

n  7 x … x 7 56 fois  x 717

 

Or 56 = 11 x 5 + 1

n  711 x … x 711 5 fois  x 7 x 717

n  7 x … x 7 5 fois   x 718

n  75 x 7 x 718 = 723

 

Or 23 = 11 x 2 + 1

n  711 x 711  x 7 = 73 = 343 = 11 x 31 + 2

n =   2 mod 11

Avec un peut de pratique, on peut résumer la recherche comme indiqué =>

 

 

 

 

823 543

74 867

6 806

618

56

5

 

23

2

= 11 x 74 867

= 11 x 6 806

= 11 x 618

= 11 x 56

= 11 x 5

= 11 x 0

 

= 11 x 2

= 11 x 0

 

+ 6

+ 1

+ 8

+ 2

+ 1

+ 5

Total 23

+ 1

+ 2

Total 3

Soit 73  = 343 = 11 x 3 + 2  2 mod 11

 

 

 


 

Retour

*    Approche

*    Divisibilité par 11

*    Divisibilité par 11 – Étude de cas

*    Autres exemples de calculs

Voir

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

*    Divisibilité

*    Exemple d'application du modulo en Codage RSA

*    La division

Aussi

*    Calcul mental

*    Équations

*    Géométrie

*    JeuxIndex

*    Nombres Premiers

*    Théorie des nombres

DicoNombre

*    Nombre 7

*    Nombre 11

*    Nombre 343

*    Nombre 823 543