« Approfondissements de lycée/Arithmétique modulaire » : différence entre les versions

 

Nous formons un tableau à deux colonnes où le plus grand des deux nombres est sur la droite comme ce qui suit

 

Nous calculons maintenant 49 (mod 21) qui est 7 et nous le plaçons dans la deuxième ligne de la colonne ''plus petit'', et nous plaçons 21 dans la colonne ''plus grand''.

 

Exécutons la même action sur la deuxième ligne pour produire la troisième ligne.

 

Quand nous voyons apparaître le nombre 0 dans la colonne ''plus petit'', nous savons alors que le nombre correspondant dans la colonne d'à coté est le PGDC des deux nombres avec lesquels nous avons démarré, i.e. 7 est le PGDC de 21 et 49. Cet ''algorithme'' est appelé l'algorithme d'Euclide.

:Trouver le PGDC de 31 et 101

 

 

'''Exemple 3'''

:Trouver le PGDC de 132 et 200

 

 

'''Souvenez-vous'''

Appliquons l'algorithme d'Euclide sur les deux nombres, mais nous aimerions plus de détails; plus précisément, nous voulons rajouter une colonne appelée QP pour faire apparaître le quotient partiel. Le quotient partiel est juste un terme technique pour "Combien de ''n'' vont dans ''m''" c.a.d. Le quotient partiel de 19 par 3 est 6, le quotient partiel de 21 par 4 est 5 et, en dernier exemple le quotient partiel de 49 par 7 est 7.

 

 

La table indique que trois 211 vont dans 811 avec un reste de 163, ou symboliquement :

 

Continuons :

 

Maintenant, nous formons ce que l'on appelle la "table magique" qui ressemble à ceci initialement

 

Maintenant, nous écrivons le quotient partiel sur la première ligne :

 

 

Nous établissons la table en accord avec la règle suivante :

Cela paraît plus compliqué qu'il est. Illustrons-le en produisant une colonne :

 

 

Nous plaçons un 3 dans la deuxième ligne parceque 3 = 3 x 1 + 0. Nous plaçons un 1 dans la troisième ligne parceque 1 = 3 x 0 + 1.

 

Nous remplirons la table sans interruption :

 

Ainsi :