Le plus petit multiple commun de nombres en ligne. Hochement et hochement de tête de deux nombres, algorithme euclidien

Poursuivons la conversation sur le plus petit commun multiple, que nous avons commencée dans la section « LCM - le plus petit commun multiple, définition, exemples ». Dans cette rubrique, nous examinerons les moyens de trouver le LCM pour trois nombres ou plus, et nous examinerons la question de savoir comment trouver le LCM d'un nombre négatif.

Yandex.RTB R-A-339285-1

Calcul du plus petit commun multiple (LCM) via GCD

Nous avons déjà établi la relation entre le plus petit commun multiple et le plus grand commun diviseur. Apprenons maintenant comment déterminer LCM via GCD. Voyons d’abord comment procéder pour les nombres positifs.

Définition 1

Vous pouvez trouver le plus petit commun multiple par le plus grand commun diviseur en utilisant la formule LCM (a, b) = a · b : PGCD (a, b).

Exemple 1

Vous devez trouver le LCM des nombres 126 et 70.

Solution

Prenons a = 126, b = 70. Remplaçons les valeurs dans la formule de calcul du plus petit commun multiple par le plus grand commun diviseur LCM (a, b) = a · b : PGCD (a, b) .

Trouve le pgcd des nombres 70 et 126. Pour cela nous avons besoin de l'algorithme euclidien : 126 = 70 1 + 56, 70 = 56 1 + 14, 56 = 14 4, donc PGCD (126 , 70) = 14 .

Calculons le LCM : LCD (126, 70) = 126 70 : PGCD (126, 70) = 126 70 : 14 = 630.

Répondre: LCM(126, 70) = 630.

Exemple 2

Trouvez les nombres 68 et 34.

Solution

PGCD dans dans ce cas Ce n’est pas difficile puisque 68 est divisible par 34. Calculons le plus petit commun multiple en utilisant la formule : LCM (68, 34) = 68 34 : PGCD (68, 34) = 68 34 : 34 = 68.

Répondre: LCM(68, 34) = 68.

Dans cet exemple, nous avons utilisé la règle pour trouver le plus petit commun multiple des entiers positifs a et b : si le premier nombre est divisible par le second, le LCM de ces nombres sera égal au premier nombre.

Trouver le LCM en factorisant les nombres en facteurs premiers

Examinons maintenant une méthode pour trouver le LCM, basée sur la factorisation des nombres en facteurs premiers.

Définition 2

Pour trouver le plus petit commun multiple, nous devons effectuer un certain nombre d’étapes simples :

• nous composons le produit de tous les facteurs premiers des nombres pour lesquels nous devons trouver le LCM ;
• nous excluons tous les facteurs premiers de leurs produits résultants ;
• le produit obtenu après élimination des facteurs premiers communs sera égal au LCM des nombres donnés.

Cette méthode de recherche du plus petit commun multiple est basée sur l'égalité LCM (a, b) = a · b : PGCD (a, b). Si vous regardez la formule, cela deviendra clair : le produit des nombres a et b est égal au produit de tous les facteurs qui participent à la décomposition de ces deux nombres. Dans ce cas, le pgcd de deux nombres est égal au produit de tous les facteurs premiers simultanément présents dans les factorisations des deux nombres donnés.

Exemple 3

Nous avons deux nombres 75 et 210. Nous pouvons les factoriser de la manière suivante : 75 = 3 5 5 Et 210 = 2 3 5 7. Si vous composez le produit de tous les facteurs des deux nombres d’origine, vous obtenez : 2 3 3 5 5 5 7.

Si l'on exclut les facteurs communs aux nombres 3 et 5, nous obtenons un produit de la forme suivante : 2 3 5 5 7 = 1050. Ce produit sera notre LCM pour les numéros 75 et 210.

Exemple 4

Trouver le LCM des nombres 441 Et 700 , en factorisant les deux nombres en facteurs premiers.

Solution

Trouvons tous les facteurs premiers des nombres donnés dans la condition :

441 147 49 7 1 3 3 7 7

700 350 175 35 7 1 2 2 5 5 7

Nous obtenons deux chaînes de nombres : 441 = 3 3 7 7 et 700 = 2 2 5 5 7.

Le produit de tous les facteurs ayant participé à la décomposition de ces nombres aura la forme : 2 2 3 3 5 5 7 7 7. Trouvons des facteurs communs. C'est le numéro 7. Excluons-le du produit total : 2 2 3 3 5 5 7 7. Il s'avère que NOC (441, 700) = 2 2 3 3 5 5 7 7 = 44 100.

Répondre: LOC(441, 700) = 44 100.

Donnons une autre formulation de la méthode pour trouver le LCM en décomposant les nombres en facteurs premiers.

Définition 3

Auparavant, nous excluions du nombre total les facteurs communs aux deux nombres. Maintenant, nous allons procéder différemment :

• Factorisons les deux nombres en facteurs premiers :
• ajouter au produit des facteurs premiers du premier nombre les facteurs manquants du deuxième nombre ;
• on obtient le produit, qui sera le LCM souhaité de deux nombres.

Exemple 5

Revenons aux nombres 75 et 210, pour lesquels nous avons déjà recherché le LCM dans un des exemples précédents. Décomposons-les en facteurs simples : 75 = 3 5 5 Et 210 = 2 3 5 7. Au produit des facteurs 3, 5 et 5 les nombres 75 ajoutent les facteurs manquants 2 Et 7 numéros 210. On obtient : 2 · 3 · 5 · 5 · 7 . Il s'agit du LCM des nombres 75 et 210.

Exemple 6

Il faut calculer le LCM des nombres 84 et 648.

Solution

Factorisons les chiffres de la condition en facteurs simples : 84 = 2 2 3 7 Et 648 = 2 2 2 3 3 3 3. Ajoutons au produit les facteurs 2, 2, 3 et 7 nombres 84 facteurs manquants 2, 3, 3 et
3 numéros 648. Nous obtenons le produit 2 2 2 3 3 3 3 7 = 4536. Il s'agit du plus petit commun multiple de 84 et 648.

Répondre: LCM(84, 648) = 4 536.

Trouver le LCM de trois nombres ou plus

Quel que soit le nombre de nombres auxquels nous avons affaire, l'algorithme de nos actions sera toujours le même : nous trouverons séquentiellement le LCM de deux nombres. Il existe un théorème pour ce cas.

Théorème 1

Supposons que nous ayons des entiers une 1 , une 2 , … , une k. CNP mk ces nombres sont trouvés en calculant séquentiellement m 2 = LCM (a 1, a 2), m 3 = LCM (m 2, a 3), ..., m k = LCM (m k − 1, a k).

Voyons maintenant comment le théorème peut être appliqué pour résoudre des problèmes spécifiques.

Exemple 7

Vous devez calculer le plus petit commun multiple de quatre nombres 140, 9, 54 et 250 .

Solution

Introduisons la notation : a 1 = 140, a 2 = 9, a 3 = 54, a 4 = 250.

Commençons par calculer m 2 = LCM (a 1 , a 2) = LCM (140, 9). Appliquons l'algorithme euclidien pour calculer le PGCD des nombres 140 et 9 : 140 = 9 15 + 5, 9 = 5 1 + 4, 5 = 4 1 + 1, 4 = 1 4. On obtient : PGCD (140, 9) = 1, PGCD (140, 9) = 140 · 9 : PGCD (140, 9) = 140 · 9 : 1 = 1 260. Par conséquent, m 2 = 1 260.

Calculons maintenant en utilisant le même algorithme m 3 = LCM (m 2 , a 3) = LCM (1 260, 54). Lors des calculs on obtient m 3 = 3 780.

Il suffit de calculer m 4 = LCM (m 3 , a 4) = LCM (3 780, 250). Nous suivons le même algorithme. On obtient m 4 = 94 500.

Le LCM des quatre nombres de l’exemple de condition est 94 500.

Répondre: CNP (140, 9, 54, 250) = 94 500.

Comme vous pouvez le constater, les calculs sont simples, mais assez laborieux. Pour gagner du temps, vous pouvez procéder autrement.

Définition 4

Nous vous proposons l'algorithme d'actions suivant :

• nous décomposons tous les nombres en facteurs premiers ;
• au produit des facteurs du premier nombre on ajoute les facteurs manquants du produit du deuxième nombre ;
• au produit obtenu à l'étape précédente on ajoute les facteurs manquants du troisième nombre, etc. ;
• le produit résultant sera le plus petit commun multiple de tous les nombres de la condition.

Exemple 8

Vous devez trouver le LCM de cinq nombres 84, 6, 48, 7, 143.

Solution

Factorisons les cinq nombres en facteurs premiers : 84 = 2 2 3 7, 6 = 2 3, 48 = 2 2 2 2 3, 7, 143 = 11 13. Les nombres premiers, qui sont le nombre 7, ne peuvent pas être pris en compte dans les facteurs premiers. Ces nombres coïncident avec leur décomposition en facteurs premiers.

Prenons maintenant le produit des facteurs premiers 2, 2, 3 et 7 du nombre 84 et ajoutons-y les facteurs manquants du deuxième nombre. Nous avons décomposé le nombre 6 en 2 et 3. Ces facteurs sont déjà dans le produit du premier nombre. Nous les omettons donc.

Nous continuons à ajouter les multiplicateurs manquants. Passons au nombre 48, du produit des facteurs premiers duquel on prend 2 et 2. Ensuite, on additionne le facteur premier de 7 du quatrième nombre et les facteurs de 11 et 13 du cinquième. On obtient : 2 2 2 2 3 7 11 13 = 48 048. Il s’agit du plus petit commun multiple des cinq nombres originaux.

Répondre: LCM(84, 6, 48, 7, 143) = 48 048.

Trouver le plus petit commun multiple de nombres négatifs

Afin de trouver le plus petit commun multiple de nombres négatifs, ces nombres doivent d'abord être remplacés par des nombres de signe opposé, puis les calculs doivent être effectués à l'aide des algorithmes ci-dessus.

Exemple 9

LCM (54, − 34) = LCM (54, 34) et LCM (− 622, − 46, − 54, − 888) = LCM (622, 46, 54, 888).

De telles actions sont autorisées car si nous acceptons cela un Et − un– les nombres opposés,
alors l'ensemble des multiples d'un nombre un correspond à l'ensemble des multiples d'un nombre − un.

Exemple 10

Il faut calculer le LCM des nombres négatifs − 145 Et − 45 .

Solution

Remplaçons les chiffres − 145 Et − 45 à leurs homologues 145 Et 45 . Maintenant, en utilisant l'algorithme, nous calculons le LCM (145, 45) = 145 · 45 : PGCD (145, 45) = 145 · 45 : 5 = 1 305, après avoir préalablement déterminé le PGCD à l'aide de l'algorithme euclidien.

On obtient que le LCM des nombres est − 145 et − 45 est égal 1 305 .

Répondre: LCM (− 145, − 45) = 1 305.

Si vous remarquez une erreur dans le texte, veuillez la surligner et appuyer sur Ctrl+Entrée

Le plus grand commun diviseur et le plus petit commun multiple sont des concepts arithmétiques clés qui facilitent le travail avec les fractions. LCM et sont le plus souvent utilisés pour trouver le dénominateur commun de plusieurs fractions.

Concepts de base

Le diviseur d'un entier X est un autre entier Y par lequel X est divisé sans laisser de reste. Par exemple, le diviseur de 4 est 2 et 36 est 4, 6, 9. Un multiple d'un entier X est un nombre Y divisible par X sans reste. Par exemple, 3 est un multiple de 15 et 6 est un multiple de 12.

Pour toute paire de nombres, nous pouvons trouver leurs diviseurs et multiples communs. Par exemple, pour 6 et 9, le commun multiple est 18 et le commun diviseur est 3. Évidemment, les paires peuvent avoir plusieurs diviseurs et multiples, donc les calculs utilisent le plus grand diviseur GCD et le plus petit multiple LCM.

Le plus petit diviseur n’a aucun sens puisque pour tout nombre, il vaut toujours un. Le plus grand multiple n’a également aucun sens, puisque la séquence des multiples va vers l’infini.

Trouver pgcd

Il existe de nombreuses méthodes pour trouver le plus grand diviseur commun, dont les plus connues sont :

• recherche séquentielle de diviseurs, sélection des diviseurs communs pour une paire et recherche du plus grand d'entre eux ;
• décomposition des nombres en facteurs indivisibles ;
• Algorithme euclidien ;
• algorithme binaire.

Aujourd'hui, dans les établissements d'enseignement, les méthodes les plus populaires sont la décomposition en facteurs premiers et l'algorithme euclidien. Ce dernier, à son tour, est utilisé lors de la résolution d'équations diophantiennes : la recherche de GCD est nécessaire pour vérifier l'équation pour la possibilité de résolution en nombres entiers.

Trouver le CNO

Le multiple le plus petit commun est également déterminé par énumération séquentielle ou factorisation en facteurs indivisibles. De plus, il est facile de trouver le LCM si le plus grand diviseur a déjà été déterminé. Pour les nombres X et Y, le LCM et le GCD sont liés par la relation suivante :

LCD(X,Y) = X × Y / PGCD(X,Y).

Par exemple, si GCM(15,18) = 3, alors LCM(15,18) = 15 × 18 / 3 = 90. L'exemple le plus évident d'utilisation de LCM consiste à trouver le dénominateur commun, qui est le plus petit commun multiple de fractions données.

Nombres premiers entre eux

Si une paire de nombres n’a pas de diviseur commun, alors une telle paire est appelée premier entre eux. Le pgcd de ces paires est toujours égal à un, et sur la base de la relation entre les diviseurs et les multiples, le pgcd des paires premières entre elles est égal à leur produit. Par exemple, les nombres 25 et 28 sont relativement premiers, car ils n'ont pas de diviseur commun, et LCM(25, 28) = 700, ce qui correspond à leur produit. Deux nombres indivisibles seront toujours premiers relativement.

Diviseur commun et calculateur multiple

À l'aide de notre calculatrice, vous pouvez calculer GCD et LCM pour un nombre arbitraire de nombres parmi lesquels choisir. Les tâches de calcul des diviseurs communs et des multiples se trouvent en arithmétique de 5e et 6e années, mais GCD et LCM sont des concepts clés en mathématiques et sont utilisés en théorie des nombres, en planimétrie et en algèbre communicative.

Exemples concrets

Dénominateur commun des fractions

Le plus petit commun multiple est utilisé pour trouver le dénominateur commun de plusieurs fractions. Disons que dans un problème arithmétique, vous devez additionner 5 fractions :

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Pour additionner des fractions, l'expression doit être réduite à un dénominateur commun, ce qui se réduit au problème de trouver le LCM. Pour ce faire, sélectionnez 5 nombres dans la calculatrice et saisissez les valeurs des dénominateurs dans les cellules appropriées. Le programme calculera le LCM (8, 9, 12, 15, 18) = 360. Vous devez maintenant calculer des facteurs supplémentaires pour chaque fraction, qui sont définis comme le rapport du LCM au dénominateur. Les multiplicateurs supplémentaires ressembleraient donc à :

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

Après cela, nous multiplions toutes les fractions par le facteur supplémentaire correspondant et obtenons :

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Nous pouvons facilement additionner ces fractions et obtenir le résultat 159/360. Nous réduisons la fraction de 3 et voyons la réponse finale - 53/120.

Résolution d'équations diophantiennes linéaires

Les équations diophantiennes linéaires sont des expressions de la forme ax + by = d. Si le rapport d / pgcd(a, b) est un nombre entier, alors l'équation peut être résolue en nombres entiers. Vérifions quelques équations pour voir si elles ont une solution entière. Vérifions d'abord l'équation 150x + 8y = 37. À l'aide d'une calculatrice, nous trouvons PGCD (150,8) = 2. Divisons 37/2 = 18,5. Le nombre n’est pas un nombre entier, donc l’équation n’a pas de racines entières.

Vérifions l'équation 1320x + 1760y = 10120. Utilisez une calculatrice pour trouver PGCD(1320, 1760) = 440. Divisons 10120/440 = 23. En conséquence, nous obtenons un nombre entier, par conséquent, l'équation diophantienne peut être résolue en coefficients entiers. .

Conclusion

GCD et LCM jouent un rôle important dans la théorie des nombres, et les concepts eux-mêmes sont largement utilisés dans une grande variété de domaines mathématiques. Utilisez notre calculatrice pour calculer les plus grands diviseurs et les plus petits multiples d'un nombre quelconque de nombres.

Examinons trois façons de trouver le plus petit commun multiple.

Recherche par factorisation

La première méthode consiste à trouver le plus petit commun multiple en factorisant les nombres donnés en facteurs premiers.

Disons que nous devons trouver le LCM des nombres : 99, 30 et 28. Pour ce faire, factorisons chacun de ces nombres en facteurs premiers :

Pour que le nombre souhaité soit divisible par 99, 30 et 28, il faut et suffisant qu'il comprenne tous les facteurs premiers de ces diviseurs. Pour ce faire, nous devons prendre tous les facteurs premiers de ces nombres au plus grand degré possible et les multiplier entre eux :

2 2 3 2 5 7 11 = 13 860

Ainsi, LCM (99, 30, 28) = 13 860. Aucun autre nombre inférieur à 13 860 n’est divisible par 99, 30 ou 28.

Pour trouver le plus petit commun multiple de nombres donnés, vous les intégrez à leurs facteurs premiers, puis prenez chaque facteur premier avec le plus grand exposant dans lequel il apparaît et multipliez ces facteurs ensemble.

Puisque les nombres relativement premiers n’ont pas de facteurs premiers communs, leur plus petit commun multiple est égal au produit de ces nombres. Par exemple, trois nombres : 20, 49 et 33 sont premiers entre eux. C'est pourquoi

LCM (20, 49, 33) = 20 49 33 = 32 340.

La même chose doit être faite pour trouver le plus petit commun multiple de différents nombres premiers. Par exemple, LCM (3, 7, 11) = 3 7 11 = 231.

Recherche par sélection

La deuxième méthode consiste à trouver le plus petit commun multiple par sélection.

Exemple 1. Lorsque le plus grand des nombres donnés est divisé par un autre nombre donné, alors le LCM de ces nombres est égal au plus grand d'entre eux. Par exemple, étant donné quatre nombres : 60, 30, 10 et 6. Chacun d'eux est divisible par 60, donc :

LCM(60, 30, 10, 6) = 60

Dans d'autres cas, pour trouver le plus petit commun multiple, la procédure suivante est utilisée :

1. Déterminez le plus grand nombre parmi les nombres donnés.
2. Ensuite, nous trouvons les nombres qui sont des multiples du plus grand nombre, en le multipliant par des nombres naturels dans l'ordre croissant et en vérifiant si le produit obtenu est divisible par les nombres donnés restants.

Exemple 2. Étant donné trois nombres 24, 3 et 18. Nous déterminons le plus grand d'entre eux - c'est le nombre 24. Ensuite, nous trouvons les nombres multiples de 24, en vérifiant si chacun d'eux est divisible par 18 et 3 :

24 · 1 = 24 - divisible par 3, mais non divisible par 18.

24 · 2 = 48 - divisible par 3, mais non divisible par 18.

24 · 3 = 72 - divisible par 3 et 18.

Ainsi, LCM (24, 3, 18) = 72.

Recherche en trouvant séquentiellement le LCM

La troisième méthode consiste à trouver le multiple le plus petit commun en trouvant séquentiellement le LCM.

Le LCM de deux nombres donnés est égal au produit de ces nombres divisé par leur plus grand diviseur commun.

Exemple 1. Trouvez le LCM de deux nombres donnés : 12 et 8. Déterminez leur plus grand diviseur commun : PGCD (12, 8) = 4. Multipliez ces nombres :

Nous divisons le produit par leur pgcd :

Ainsi, LCM (12, 8) = 24.

Pour trouver le LCM de trois nombres ou plus, utilisez la procédure suivante :

1. Tout d’abord, trouvez le LCM de deux de ces nombres.
2. Ensuite, LCM du plus petit commun multiple trouvé et du troisième nombre donné.
3. Ensuite, le LCM du plus petit commun multiple résultant et du quatrième nombre, etc.
4. Ainsi, la recherche du LCM se poursuit tant qu’il y a des chiffres.

Exemple 2. Trouvons le LCM de trois nombres donnés : 12, 8 et 9. Nous avons déjà trouvé le LCM des nombres 12 et 8 dans l'exemple précédent (c'est le nombre 24). Il reste à trouver le plus petit commun multiple du nombre 24 et du troisième nombre donné - 9. Déterminer leur plus grand commun diviseur : PGCD (24, 9) = 3. Multiplier le LCM par le nombre 9 :

Nous divisons le produit par leur pgcd :

Ainsi, LCM (12, 8, 9) = 72.

Pour comprendre comment calculer le LCM, vous devez d’abord déterminer la signification du terme « multiple ».

Un multiple de A est un nombre naturel divisible par A sans reste. Ainsi, les nombres multiples de 5 peuvent être considérés comme 15, 20, 25, etc.

Il peut y avoir un nombre limité de diviseurs d’un nombre particulier, mais il existe un nombre infini de multiples.

Un multiple commun de nombres naturels est un nombre qui est divisible par eux sans laisser de reste.

Comment trouver le plus petit commun multiple de nombres

Le plus petit commun multiple (LCM) des nombres (deux, trois ou plus) est le plus petit nombre naturel divisible par tous ces nombres.

Pour trouver le LOC, vous pouvez utiliser plusieurs méthodes.

Pour les petits nombres, il est pratique d'écrire tous les multiples de ces nombres sur une ligne jusqu'à ce que vous trouviez quelque chose de commun entre eux. Les multiples sont désignés par la lettre majuscule K.

Par exemple, les multiples de 4 peuvent s’écrire ainsi :

K(4) = (8,12, 16, 20, 24, ...)

K (6) = (12, 18, 24, ...)

Ainsi, vous voyez que le plus petit commun multiple des nombres 4 et 6 est le nombre 24. Cette notation se fait comme suit :

LCM(4, 6) = 24

Si les nombres sont grands, trouvez le commun multiple de trois nombres ou plus, il est alors préférable d'utiliser une autre méthode de calcul du LCM.

Pour terminer la tâche, vous devez factoriser les nombres donnés en facteurs premiers.

Vous devez d'abord écrire la décomposition du plus grand nombre sur une ligne, et en dessous - le reste.

La décomposition de chaque nombre peut contenir un nombre différent de facteurs.

Par exemple, factorisons les nombres 50 et 20 en facteurs premiers.

Dans l'expansion du plus petit nombre, vous devez mettre en évidence les facteurs qui manquent dans l'expansion du premier plus grand nombre, puis les y ajouter. Dans l’exemple présenté, il manque un deux.

Vous pouvez maintenant calculer le plus petit commun multiple de 20 et 50.

LCM(20, 50) = 2 * 5 * 5 * 2 = 100

Ainsi, le produit des facteurs premiers du plus grand nombre et des facteurs du deuxième nombre qui n'ont pas été inclus dans le développement du plus grand nombre sera le plus petit commun multiple.

Pour trouver le LCM de trois nombres ou plus, vous devez tous les factoriser en facteurs premiers, comme dans le cas précédent.

A titre d'exemple, vous pouvez trouver le plus petit commun multiple des nombres 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

Ainsi, seuls deux deux du développement de seize n'ont pas été inclus dans la factorisation d'un plus grand nombre (un est dans le développement de vingt-quatre).

Il faut donc les ajouter à l’expansion d’un plus grand nombre.

LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

Il existe des cas particuliers pour déterminer le plus petit commun multiple. Ainsi, si l'un des nombres peut être divisé sans reste par un autre, alors le plus grand de ces nombres sera le plus petit commun multiple.

Par exemple, le LCM de douze et vingt-quatre est vingt-quatre.

S'il est nécessaire de trouver le plus petit commun multiple de nombres premiers qui n'ont pas de diviseurs identiques, alors leur LCM sera égal à leur produit.

Par exemple, LCM (10, 11) = 110.

Deuxième numéro : b=

Séparateur de milliers Sans séparateur d'espace "´

Résultat:

Plus grand diviseur commun pgcd ( un,b)=6

Plus petit commun multiple de LCM ( un,b)=468

Le plus grand nombre naturel pouvant être divisé sans reste par les nombres a et b s'appelle plus grand diviseur commun(PGCD) de ces nombres. Noté pgcd(a,b), (a,b), pgcd(a,b) ou hcf(a,b).

Le plus petit commun multiple Le LCM de deux entiers a et b est le plus petit nombre naturel divisible par a et b sans reste. Noté LCM(a,b), ou lcm(a,b).

Les entiers a et b sont appelés mutuellement premier, s'ils n'ont pas de diviseurs communs autres que +1 et −1.

Plus grand diviseur commun

Soit deux nombres positifs un 1 et un 2 1). Il faut trouver le diviseur commun de ces nombres, c'est-à-dire trouver un tel numéro λ , qui divise les nombres un 1 et un 2 en même temps. Décrivons l'algorithme.

1) Dans cet article, le mot nombre sera compris comme un nombre entier.

Laisser un 1 ≥ un 2 et laissez

Où m 1 , un 3 sont des nombres entiers, un 3 <un 2 (reste de la division un 1 par un 2 devrait être moins un 2).

Supposons que λ divise un 1 et un 2 alors λ divise m 1 un 2 et λ divise un 1 −m 1 un 2 =un 3 (Énoncé 2 de l'article « Divisibilité des nombres. Test de divisibilité »). Il s’ensuit que tout diviseur commun un 1 et un 2 est le diviseur commun un 2 et un 3. L’inverse est également vrai si λ diviseur commun un 2 et un 3 alors m 1 un 2 et un 1 =m 1 un 2 +un 3 est également divisible par λ . Donc le diviseur commun un 2 et un 3 est aussi un diviseur commun un 1 et un 2. Parce que un 3 <un 2 ≤un 1, alors on peut dire que la solution au problème de trouver le diviseur commun des nombres un 1 et un 2 réduit au problème plus simple de trouver le diviseur commun des nombres un 2 et un 3 .

Si un 3 ≠0, alors on peut diviser un 2 sur un 3. Alors

,

Où m 1 et un 4 sont des nombres entiers, ( un 4 reste de la division un 2 sur un 3 (un 4 <un 3)). Par un raisonnement similaire, nous arrivons à la conclusion que les diviseurs communs des nombres un 3 et un 4 coïncide avec les diviseurs communs des nombres un 2 et un 3, et aussi avec des diviseurs communs un 1 et un 2. Parce que un 1 , un 2 , un 3 , un 4, ... sont des nombres qui diminuent constamment, et comme il existe un nombre fini d'entiers entre un 2 et 0, puis à un moment donné n, reste de la division un n sur un n+1 sera égal à zéro ( un n+2 =0).

.

Tout diviseur commun λ Nombres un 1 et un 2 est aussi un diviseur de nombres un 2 et un 3 , un 3 et un 4 , .... un n et un n+1 . L'inverse est également vrai, les diviseurs communs des nombres un n et un n+1 sont aussi des diviseurs de nombres un n−1 et un n , .... , un 2 et un 3 , un 1 et un 2. Mais le diviseur commun des nombres un n et un n+1 est un nombre un n+1 , parce que un n et un n+1 sont divisibles par un n+1 (rappelez-vous que un n+2 =0). Ainsi un n+1 est aussi un diviseur de nombres un 1 et un 2 .

Notez que le numéro un n+1 est le plus grand diviseur des nombres un n et un n+1 , puisque le plus grand diviseur un n+1 est lui-même un n+1 . Si un n+1 peut être représenté comme un produit d'entiers, alors ces nombres sont également des diviseurs communs de nombres un 1 et un 2. Nombre un n+1 est appelé plus grand diviseur commun Nombres un 1 et un 2 .

Nombres un 1 et un 2 peut être un nombre positif ou négatif. Si l'un des nombres est égal à zéro, alors le plus grand diviseur commun de ces nombres sera égal à la valeur absolue de l'autre nombre. Le plus grand diviseur commun de zéros n’est pas défini.

L'algorithme ci-dessus s'appelle Algorithme euclidien trouver le plus grand diviseur commun de deux nombres entiers.

Un exemple de recherche du plus grand diviseur commun de deux nombres

Trouvez le plus grand diviseur commun de deux nombres 630 et 434.

• Étape 1. Divisez le nombre 630 par 434. Le reste est 196.
• Étape 2. Divisez le nombre 434 par 196. Le reste est 42.
• Étape 3. Divisez le nombre 196 par 42. Le reste est 28.
• Étape 4. Divisez le nombre 42 par 28. Le reste est 14.
• Étape 5. Divisez le nombre 28 par 14. Le reste est 0.

À l'étape 5, le reste de la division est 0. Par conséquent, le plus grand diviseur commun des nombres 630 et 434 est 14. Notez que les nombres 2 et 7 sont également des diviseurs des nombres 630 et 434.

Nombres premiers entre eux

Définition 1. Soit le plus grand diviseur commun des nombres un 1 et un 2 est égal à un. Ensuite, ces numéros sont appelés nombres premiers entre eux, n'ayant pas de diviseur commun.

Théorème 1. Si un 1 et un 2 nombres premiers entre eux, et λ un nombre, puis tout diviseur commun de nombres λa 1 et un 2 est aussi un diviseur commun des nombres λ Et un 2 .

Preuve. Considérons l'algorithme euclidien pour trouver le plus grand diviseur commun des nombres un 1 et un 2 (voir ci-dessus).

.

Des conditions du théorème, il s'ensuit que le plus grand diviseur commun des nombres un 1 et un 2 et donc un n et un n+1 vaut 1. C'est-à-dire un n+1 =1.

Multiplions toutes ces égalités par λ , Alors

.

Soit le diviseur commun un 1 λ Et un 2 oui δ . Alors δ est inclus comme multiplicateur dans un 1 λ , m 1 un 2 λ et dans un 1 λ -m 1 un 2 λ =un 3 λ (voir "Divisibilité des nombres", Énoncé 2). Suivant δ est inclus comme multiplicateur dans un 2 λ Et m 2 un 3 λ , et est donc inclus comme facteur dans un 2 λ -m 2 un 3 λ =un 4 λ .

En raisonnant ainsi, nous sommes convaincus que δ est inclus comme multiplicateur dans un n−1 λ Et m n−1 un n λ , et donc dans un n−1 λ −m n−1 un n λ =un n+1 λ . Parce que un n+1 =1, alors δ est inclus comme multiplicateur dans λ . Donc le nombre δ est le diviseur commun des nombres λ Et un 2 .

Considérons des cas particuliers du théorème 1.

Conséquence 1. Laisser un Et c Les nombres premiers sont relativement b. Puis leur produit ca est un nombre premier par rapport à b.

Vraiment. D'après le théorème 1 ca Et b ont les mêmes diviseurs communs que c Et b. Mais les chiffres c Et b relativement simple, c'est-à-dire avoir un seul diviseur commun 1. Alors ca Et b ont également un seul diviseur commun 1. Par conséquent ca Et b mutuellement simples.

Conséquence 2. Laisser un Et b nombres premiers entre eux et laissez b divise eak. Alors b divise et k.

Vraiment. De la condition d'approbation eak Et b avoir un diviseur commun b. En vertu du théorème 1, b doit être un diviseur commun b Et k. Ainsi b divise k.

Le corollaire 1 peut être généralisé.

Conséquence 3. 1. Laissez les chiffres un 1 , un 2 , un 3 , ..., un m sont premiers par rapport au nombre b. Alors un 1 un 2 , un 1 un 2 · un 3 , ..., un 1 un 2 un 3 ··· un m, le produit de ces nombres est premier par rapport au nombre b.

2. Ayons deux rangées de nombres

de telle sorte que chaque nombre de la première série est premier dans le rapport de chaque nombre de la deuxième série. Ensuite le produit

Vous devez trouver des nombres divisibles par chacun de ces nombres.

Si un nombre est divisible par un 1, alors il a la forme sa 1 où s un certain nombre. Si q est le plus grand commun diviseur des nombres un 1 et un 2, alors

Où s 1 est un entier. Alors

est multiples de nombres les moins courants un 1 et un 2 .

un 1 et un 2 sont relativement premiers, donc le plus petit commun multiple des nombres un 1 et un 2:

Nous devons trouver le plus petit commun multiple de ces nombres.

De ce qui précède, il s'ensuit que tout multiple de nombres un 1 , un 2 , un 3 doit être un multiple de nombres ε Et un 3 et retour. Soit le plus petit commun multiple des nombres ε Et un 3 oui ε 1. Ensuite, des multiples de nombres un 1 , un 2 , un 3 , un 4 doit être un multiple de nombres ε 1 et un 4. Soit le plus petit commun multiple des nombres ε 1 et un 4 oui ε 2. Ainsi, nous avons découvert que tous les multiples de nombres un 1 , un 2 , un 3 ,...,un m coïncide avec des multiples d'un certain nombre ε n, qui est appelé le plus petit commun multiple des nombres donnés.

Dans le cas particulier où les nombres un 1 , un 2 , un 3 ,...,un m sont relativement premiers, alors le plus petit commun multiple des nombres un 1 , un 2, comme représenté ci-dessus, a la forme (3). Ensuite, puisque un 3 premiers par rapport aux nombres un 1 , un 2 alors un 3 nombre premier un 1 · un 2 (Corollaire 1). Signifie le plus petit commun multiple des nombres un 1 ,un 2 ,un 3 est un nombre un 1 · un 2 · un 3. En raisonnant de la même manière, nous arrivons aux affirmations suivantes.

Déclaration 1. Le plus petit commun multiple des nombres premiers un 1 , un 2 , un 3 ,...,un m est égal à leur produit un 1 · un 2 · un 3 ··· un m.

Déclaration 2. Tout nombre divisible par chacun des nombres premiers entre eux un 1 , un 2 , un 3 ,...,un m est également divisible par leur produit un 1 · un 2 · un 3 ··· un m.