Hochement et hochement de tête de trois chiffres ou plus. Nod et nok de nombres - plus grand diviseur commun et plus petit commun multiple de plusieurs nombres Exemples de recherche de nod et nod

Plus grand diviseur commun

Définition 2

Si un nombre naturel a est divisible par un nombre naturel $b$, alors $b$ est appelé un diviseur de $a$ et $a$ est appelé un multiple de $b$.

Soit $a$ et $b$ des nombres naturels. Le nombre $c$ est appelé le diviseur commun de $a$ et de $b$.

L'ensemble des diviseurs communs des nombres $a$ et $b$ est fini, puisqu'aucun de ces diviseurs ne peut être supérieur à $a$. Cela signifie que parmi ces diviseurs, il y en a un plus grand, qui est appelé le plus grand diviseur commun des nombres $a$ et $b$ et est noté par les notations suivantes :

$PGCD\(a;b)\ ou \D\(a;b)$

Pour trouver le plus grand diviseur commun de deux nombres, il vous faut :

Trouvez le produit des nombres trouvés à l’étape 2. Le nombre obtenu sera le plus grand diviseur commun souhaité.

Exemple 1

Trouvez le pgcd des nombres $121$ et $132.$

242$=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Choisissez les nombres qui sont inclus dans l'expansion de ces nombres

242$=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Trouvez le produit des nombres trouvés à l’étape 2. Le nombre obtenu sera le plus grand diviseur commun souhaité.

$PGCD=2\cdot 11=22$

Exemple 2

Trouvez le pgcd des monômes $63$ et $81$.

Nous trouverons selon l'algorithme présenté. Pour ce faire :

Factorisons les nombres en facteurs premiers

63$=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Nous sélectionnons les nombres qui sont inclus dans l'expansion de ces nombres

63$=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Trouvons le produit des nombres trouvés à l'étape 2. Le nombre résultant sera le plus grand diviseur commun souhaité.

$PGCD=3\cdot 3=9$

Vous pouvez trouver le pgcd de deux nombres d’une autre manière, en utilisant un ensemble de diviseurs de nombres.

Exemple 3

Trouvez le pgcd des nombres 48$ et 60$.

Solution:

Trouvons l'ensemble des diviseurs du nombre $48$ : $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Trouvons maintenant l'ensemble des diviseurs du nombre $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$ $

Trouvons l'intersection de ces ensembles : $\left$(\rm 1,2,3,4,6,12)\right$$ - cet ensemble déterminera l'ensemble des diviseurs communs des nombres $48$ et $60 $. L'élément le plus important de cet ensemble sera le nombre $12$. Cela signifie que le plus grand diviseur commun des nombres 48$ et 60$ est 12$.

Définition du NPL

Définition 3

Multiples communs de nombres naturels$a$ et $b$ sont un nombre naturel qui est un multiple de $a$ et de $b$.

Les multiples communs de nombres sont des nombres divisibles par les nombres d'origine sans reste. Par exemple, pour les nombres 25$ et 50$, les multiples communs seront les nombres 50,100,150,200$, etc.

Le plus petit commun multiple sera appelé plus petit commun multiple et sera noté LCM$(a;b)$ ou K$(a;b).$

Pour trouver le LCM de deux nombres, vous devez :

Factoriser les nombres en facteurs premiers
Notez les facteurs qui font partie du premier nombre et ajoutez-y les facteurs qui font partie du second et ne font pas partie du premier.

Exemple 4

Trouvez le LCM des nombres 99$ et 77$.

Nous trouverons selon l'algorithme présenté. Pour ça

Factoriser les nombres en facteurs premiers

99$=3\cdot 3\cdot 11$

Notez les facteurs inclus dans le premier

ajoutez-y des multiplicateurs qui font partie du second et ne font pas partie du premier

Trouvez le produit des nombres trouvés à l'étape 2. Le nombre résultant sera le plus petit commun multiple souhaité

$NOK=3\cdot 3\cdot 11\cdot 7=693$

Compiler des listes de diviseurs de nombres est souvent une tâche très laborieuse. Il existe un moyen de trouver GCD appelé algorithme euclidien.

Énoncés sur lesquels est basé l'algorithme euclidien :

Si $a$ et $b$ sont des nombres naturels et $a\vdots b$, alors $D(a;b)=b$

Si $a$ et $b$ sont des nombres naturels tels que $b

En utilisant $D(a;b)= D(a-b;b)$, on peut réduire successivement les nombres considérés jusqu'à atteindre une paire de nombres telle que l'un d'eux soit divisible par l'autre. Ensuite, le plus petit de ces nombres sera le plus grand diviseur commun souhaité pour les nombres $a$ et $b$.

Propriétés de GCD et LCM

Tout multiple commun de $a$ et $b$ est divisible par K$(a;b)$
Si $a\vdots b$ , alors К$(a;b)=a$

Si K$(a;b)=k$ et $m$ est un nombre naturel, alors K$(am;bm)=km$

Si $d$ est un diviseur commun pour $a$ et $b$, alors K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Si $a\vdots c$ et $b\vdots c$ , alors $\frac(ab)(c)$ est le multiple commun de $a$ et $b$

Pour tout nombre naturel $a$ et $b$, l'égalité est vraie

$D(a;b)\cdot К(a;b)=ab$

Tout diviseur commun des nombres $a$ et $b$ est un diviseur du nombre $D(a;b)$

Cet article est consacré à la question de la recherche du plus grand diviseur commun. Tout d'abord, nous expliquerons ce que c'est et donnerons plusieurs exemples, présenterons les définitions du plus grand diviseur commun de 2, 3 nombres ou plus, après quoi nous nous attarderons sur les propriétés générales de ce concept et les prouverons.

Quels sont les diviseurs communs

Pour comprendre ce qu’est le plus grand diviseur commun, nous formulons d’abord ce qu’est généralement un diviseur commun pour les entiers.

Dans l’article sur les multiples et diviseurs, nous avons dit qu’un entier a toujours plusieurs diviseurs. On s'intéresse ici aux diviseurs d'un certain nombre d'entiers à la fois, notamment ceux communs (identiques) à tous. Écrivons la définition de base.

Définition 1

Le diviseur commun de plusieurs entiers est un nombre qui peut être un diviseur de chaque nombre de l'ensemble spécifié.

Exemple 1

Voici des exemples d'un tel diviseur : trois sera un diviseur commun pour les nombres - 12 et 9, puisque les égalités 9 = 3 · 3 et − 12 = 3 · (− 4) sont vraies. Les nombres 3 et - 12 ont d'autres facteurs communs, tels que 1, − 1 et − 3. Prenons un autre exemple. Les quatre entiers 3, − 11, − 8 et 19 auront deux facteurs communs : 1 et - 1.

Connaissant les propriétés de divisibilité, on peut dire que tout entier peut être divisé par un et moins un, ce qui signifie que tout ensemble d'entiers aura déjà au moins deux diviseurs communs.

Notez également que si nous avons un diviseur commun b pour plusieurs nombres, alors les mêmes nombres peuvent être divisés par le nombre opposé, c'est-à-dire par - b. En principe, nous ne pouvons prendre que des diviseurs positifs, alors tous les diviseurs communs seront également supérieurs à 0. Cette approche peut également être utilisée, mais les nombres négatifs ne doivent pas être complètement ignorés.

Quel est le plus grand commun diviseur (PGCD)

Selon les propriétés de divisibilité, si b est un diviseur d'un entier a qui n'est pas égal à 0, alors le module de b ne peut pas être supérieur au module de a, donc tout nombre non égal à 0 a un nombre fini de diviseurs. Cela signifie que le nombre de diviseurs communs de plusieurs entiers, dont au moins un est différent de zéro, sera également fini, et parmi leur ensemble entier on pourra toujours sélectionner le plus grand nombre (nous avons déjà parlé de la notion de plus grand et plus petit entier, nous vous conseillons de répéter ce matériel).

Dans d’autres discussions, nous supposerons qu’au moins un des nombres pour lesquels nous devons trouver le plus grand diviseur commun sera différent de 0. S'ils sont tous égaux à 0, alors leur diviseur peut être n'importe quel nombre entier, et comme il y en a une infinité, on ne peut pas choisir le plus grand. En d’autres termes, il est impossible de trouver le plus grand diviseur commun pour un ensemble de nombres égal à 0.

Passons à la formulation de la définition principale.

Définition 2

Le plus grand commun diviseur de plusieurs nombres est le plus grand nombre entier qui divise tous ces nombres.

À l'écrit, le plus grand diviseur commun est le plus souvent désigné par l'abréviation PGCD. Pour deux nombres, cela peut s'écrire pgcd (a, b).

Exemple 2

Quel est un exemple de pgcd pour deux entiers ? Par exemple, pour 6 et - 15, ce serait 3. Justifions cela. On note d'abord tous les diviseurs de six : ± 6, ± 3, ± 1, puis tous les diviseurs de quinze : ± 15, ± 5, ± 3 et ± 1. Après cela, nous choisissons les plus communs : ce sont − 3, − 1, 1 et 3. Parmi ceux-ci, vous devez choisir le plus grand nombre. Ce sera 3.

Pour trois nombres ou plus, la détermination du plus grand facteur commun sera presque la même.

Définition 3

Le plus grand diviseur commun de trois nombres ou plus sera le plus grand nombre entier qui divisera tous ces nombres en même temps.

Pour les nombres a 1, a 2, …, an, il est pratique de désigner le diviseur par PGCD (a 1, a 2, …, an). La valeur du diviseur lui-même s'écrit sous la forme PGCD (a 1, a 2, ..., a n) = b.

Exemple 3

Voici des exemples du plus grand commun diviseur de plusieurs entiers : 12, - 8, 52, 16. Il sera égal à quatre, ce qui signifie qu'on peut écrire que PGCD (12, - 8, 52, 16) = 4.

Vous pouvez vérifier l'exactitude de cette affirmation en notant tous les diviseurs de ces nombres, puis en choisissant le plus grand d'entre eux.

Dans la pratique, il arrive souvent que le plus grand diviseur commun soit égal à l'un des nombres. Cela se produit lorsque tous les autres nombres peuvent être divisés par un nombre donné (dans le premier paragraphe de l'article, nous avons fourni une preuve de cette affirmation).

Exemple 4

Ainsi, le plus grand diviseur commun des nombres 60, 15 et - 45 est 15, puisque quinze est divisible non seulement par 60 et - 45, mais aussi par lui-même, et il n'y a pas de plus grand diviseur pour tous ces nombres.

Un cas particulier est celui des nombres premiers entre eux. Ce sont des entiers dont le plus grand commun diviseur est 1.

Propriétés de base de GCD et de l'algorithme euclidien

Le plus grand commun diviseur possède certaines propriétés caractéristiques. Formulons-les sous forme de théorèmes et prouvons chacun d'eux.

Notez que ces propriétés sont formulées pour des entiers supérieurs à zéro, et nous ne considérerons que les diviseurs positifs.

Définition 4

Les nombres a et b ont un plus grand diviseur commun égal à pgcd pour b et a, c'est-à-dire pgcd (a, b) = pgcd (b, a). Inverser les nombres n’affecte pas le résultat final.

Cette propriété découle de la définition même de GCD et n’a pas besoin de preuve.

Définition 5

Si le nombre a peut être divisé par le nombre b, alors l'ensemble des diviseurs communs de ces deux nombres sera similaire à l'ensemble des diviseurs du nombre b, c'est-à-dire pgcd (a, b) = b.

Prouvons cette affirmation.

Preuve 1

Si les nombres a et b ont des diviseurs communs, alors l’un ou l’autre peut être divisé par eux. En même temps, si a est un multiple de b, alors tout diviseur de b sera également un diviseur de a, puisque la divisibilité a une propriété telle que la transitivité. Cela signifie que tout diviseur b sera commun aux nombres a et b. Cela prouve que si nous pouvons diviser a par b, alors l’ensemble de tous les diviseurs des deux nombres coïncidera avec l’ensemble des diviseurs d’un nombre b. Et puisque le plus grand diviseur de tout nombre est ce nombre lui-même, alors le plus grand diviseur commun des nombres a et b sera également égal à b, c'est-à-dire PGCD (une , b) = b . Si a = b, alors pgcd (a, b) = pgcd (a, a) = pgcd (b, b) = a = b, par exemple, pgcd (132, 132) = 132.

Grâce à cette propriété, nous pouvons trouver le plus grand commun diviseur de deux nombres si l’un d’eux peut être divisé par l’autre. Ce diviseur est égal à l'un de ces deux nombres par lequel le deuxième nombre peut être divisé. Par exemple, pgcd (8, 24) = 8, puisque 24 est un multiple de huit.

Définition 6 Preuve 2

Essayons de prouver cette propriété. Nous avons initialement l'égalité a = b q + c, et tout diviseur commun de a et b divisera également c, ce qui s'explique par la propriété de divisibilité correspondante. Par conséquent, tout diviseur commun de b et c divisera a. Cela signifie que l'ensemble des diviseurs communs a et b coïncidera avec l'ensemble des diviseurs b et c, y compris le plus grand d'entre eux, ce qui signifie que l'égalité pgcd (a, b) = pgcd (b, c) est vraie.

Définition 7

La propriété suivante est appelée algorithme euclidien. Avec son aide, vous pouvez calculer le plus grand diviseur commun de deux nombres, ainsi que prouver d'autres propriétés de GCD.

Avant de formuler la propriété, nous vous conseillons de répéter le théorème que nous avons prouvé dans l'article sur la division avec reste. Selon lui, le nombre divisible a peut être représenté par b · q + r, b étant ici un diviseur, q étant un nombre entier (également appelé quotient incomplet) et r étant un reste qui satisfait à la condition 0 ≤ r ≤ b.

Disons que nous avons deux entiers supérieurs à 0, pour lesquels les égalités suivantes seront vraies :

une = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Ces égalités prennent fin lorsque rk + 1 devient égal à 0. Cela arrivera certainement, puisque la séquence b > r 1 > r 2 > r 3, ... est une série d'entiers décroissants, qui ne peut en inclure qu'un nombre fini. Cela signifie que rk est le plus grand diviseur commun de a et b, c'est-à-dire rk = pgcd (a, b).

Tout d’abord, nous devons prouver que rk est le diviseur commun des nombres a et b, et ensuite que rk n’est pas simplement un diviseur, mais plutôt le plus grand diviseur commun de deux nombres donnés.

Regardons la liste des égalités ci-dessus, de bas en haut. D'après la dernière égalité,
rk − 1 peut être divisé par rk . Sur la base de ce fait, ainsi que de la propriété prouvée antérieurement du plus grand diviseur commun, on peut affirmer que rk − 2 peut être divisé par rk , puisque
rk − 1 est divisé par rk et rk est divisé par rk .

La troisième égalité ci-dessous nous permet de conclure que rk − 3 peut être divisé par rk , etc. La deuxième en partant du bas est que b est divisible par rk , et la première est que a est divisible par rk . De tout cela nous concluons que rk est le diviseur commun de a et b.

Montrons maintenant que rk = GCD (a , b) . Que faut-il faire pour cela ? Montrer que tout diviseur commun de a et b divisera rk. Notons-le r 0 .

Regardons la même liste d'égalités, mais de haut en bas. Sur la base de la propriété précédente, nous pouvons conclure que r 1 est divisible par r 0, ce qui signifie que, selon la deuxième égalité, r 2 est divisé par r 0. On parcourt toutes les égalités et de la dernière on conclut que rk est divisible par r 0 . Par conséquent, rk = pgcd (a , b) .

Après avoir considéré cette propriété, nous concluons que l'ensemble des diviseurs communs a et b est similaire à l'ensemble des diviseurs PGCD de ces nombres. Cette affirmation, qui est une conséquence de l'algorithme d'Euclide, nous permettra de calculer tous les diviseurs communs de deux nombres donnés.

Passons à d'autres propriétés.

Définition 8

Si a et b sont des entiers non égaux à 0, alors il doit y avoir deux autres entiers u 0 et v 0 pour lesquels l'égalité PGCD (a, b) = a · u 0 + b · v 0 sera valable.

L'égalité donnée dans l'énoncé de propriété est une représentation linéaire du plus grand diviseur commun de a et b. C'est ce qu'on appelle la relation de Bezout, et les nombres u 0 et v 0 sont appelés coefficients de Bezout.

Preuve 3

Montrons cette propriété. Écrivons la séquence d'égalités à l'aide de l'algorithme euclidien :

La première égalité nous dit que r 1 = a − b · q 1 . Notons 1 = s 1 et − q 1 = t 1 et réécrivons cette égalité sous la forme r 1 = s 1 · a + t 1 · b. Ici les nombres s 1 et t 1 seront des nombres entiers. La deuxième égalité nous permet de conclure que r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · q 2) b . Notons − s 1 · q 2 = s 2 et 1 − t 1 · q 2 = t 2 et réécrivons l'égalité sous la forme r 2 = s 2 · a + t 2 · b, où s 2 et t 2 seront également entiers. En effet, la somme des nombres entiers, leur produit et leur différence sont également des nombres entiers. De la même manière, nous obtenons de la troisième égalité r 3 = s 3 · a + t 3 · b, de la suivante r 4 = s 4 · a + t 4 · b, etc. En fin de compte, nous concluons que rk = s k · a + t k · b pour les entiers s k et t k . Puisque rk = PGCD (a, b), on note sk = u 0 et t k = v 0. En conséquence, nous pouvons obtenir une représentation linéaire de PGCD sous la forme requise : PGCD (a, b) = a · u 0 + b · v 0.

Définition 9

GCD (m a, m b) = m GCD (a, b) pour toute valeur naturelle de m.

Preuve 4

Cette propriété peut être justifiée comme suit. Multiplions les deux côtés de chaque égalité dans l'algorithme euclidien par le nombre m et obtenons que PGCD (m · a, m · b) = m · rk, et rk est PGCD (a, b). Cela signifie pgcd (m a, m b) = m pgcd (a, b). C'est cette propriété du plus grand diviseur commun qui est utilisée lors de la recherche du PGCD à l'aide de la méthode de factorisation.

Définition 10

Si les nombres a et b ont un diviseur commun p, alors pgcd (a : p, b : p) = pgcd (a, b) : p. Dans le cas où p = GCD (a, b) on obtient GCD (a : GCD (a, b), b : GCD (a, b) = 1, donc les nombres a : GCD (a, b) et b : GCD (a , b) sont relativement premiers.

Puisque a = p (a : p) et b = p (b : p), alors, sur la base de la propriété précédente, nous pouvons créer des égalités de la forme pgcd (a, b) = pgcd (p (a : p), p · (b: p)) = p · GCD (a: p , b: p) , parmi lesquels il y aura une preuve de cette propriété. Nous utilisons cette affirmation lorsque nous réduisons des fractions ordinaires à une forme irréductible.

Définition 11

Le plus grand diviseur commun de a 1, a 2, …, a k sera le nombre d k, qui peut être trouvé en calculant séquentiellement GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3 , PGCD (ré 3 , une 4) = ré 4 , … , PGCD (ré k - 1 , une k) = ré k .

Cette propriété est utile pour trouver le plus grand diviseur commun de trois nombres ou plus. En l'utilisant, vous pouvez réduire cette action à des opérations avec deux nombres. Sa base est un corollaire de l'algorithme euclidien : si l'ensemble des diviseurs communs a 1, a 2 et a 3 coïncide avec l'ensemble d 2 et a 3, alors il coïncidera également avec les diviseurs d 3. Les diviseurs des nombres a 1, a 2, a 3 et a 4 coïncideront avec les diviseurs de d 3, ce qui signifie qu'ils coïncideront également avec les diviseurs de d 4, etc. Au final, on obtient que les diviseurs communs des nombres a 1, a 2, ..., a k coïncideront avec les diviseurs d k, et puisque le plus grand diviseur du nombre d k sera ce nombre lui-même, alors PGCD (a 1, une 2, ..., une k) = d k.

C'est tout ce que nous aimerions vous dire sur les propriétés du plus grand diviseur commun.

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

Résolvons le problème. Nous avons deux types de cookies. Certains sont au chocolat et d'autres sont nature. Il y en a 48 au chocolat et 36 nature. Vous devez faire le maximum de cadeaux possible avec ces cookies et vous devez tous les utiliser.

Tout d'abord, notons tous les diviseurs de chacun de ces deux nombres, puisque ces deux nombres doivent être divisibles par le nombre de cadeaux.

Nous obtenons,

48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Trouvons parmi les diviseurs communs que possèdent le premier et le deuxième nombres.

Les facteurs communs seront : 1, 2, 3, 4, 6, 12.

Le plus grand commun diviseur de tous est le nombre 12. Ce nombre est appelé le plus grand commun diviseur des nombres 36 et 48.

Sur la base des résultats obtenus, nous pouvons conclure que 12 cadeaux peuvent être faits à partir de tous les cookies. Un de ces cadeaux contiendra 4 biscuits au chocolat et 3 biscuits ordinaires.

Trouver le plus grand diviseur commun

Le plus grand nombre naturel qui divise deux nombres a et b sans reste est appelé le plus grand commun diviseur de ces nombres.

Parfois, l'abréviation GCD est utilisée pour raccourcir l'entrée.

Certaines paires de nombres ont un comme plus grand diviseur commun. Ces numéros sont appelés nombres premiers entre eux. Par exemple, les nombres 24 et 35 ont GCD =1.

Comment trouver le plus grand diviseur commun

Pour trouver le plus grand diviseur commun, il n’est pas nécessaire d’écrire tous les diviseurs des nombres donnés.

Vous pouvez le faire différemment. Tout d’abord, factorisez les deux nombres en facteurs premiers.

48 = 2*2*2*2*3,
36 = 2*2*3*3.

Maintenant, parmi les facteurs inclus dans le développement du premier nombre, nous allons rayer tous ceux qui ne sont pas inclus dans le développement du deuxième nombre. Dans notre cas, ce sont deux deux.

48 = 2*2*2*2*3 ,
36 = 2*2*3 *3.

Les facteurs restants sont 2, 2 et 3. Leur produit est 12. Ce nombre sera le plus grand diviseur commun des nombres 48 et 36.

Cette règle peut être étendue au cas de trois, quatre, etc. Nombres.

Schéma général pour trouver le plus grand diviseur commun

1. Divisez les nombres en facteurs premiers.
2. Parmi les facteurs inclus dans le développement d'un de ces nombres, rayez ceux qui ne sont pas inclus dans le développement d'autres nombres.
3. Calculez le produit des facteurs restants.

Chapitre 1. Nombres naturels

1.6. Plus grand commun diviseur et plus petit commun multiple

Plus tôt, nous avons nommé les diviseurs de nombres. Essayons maintenant de factoriser les nombres composés en facteurs premiers.

Définition

Factoriser un nombre en facteurs premiers signifie le représenter comme un produit égal de nombres premiers.

La décomposition en facteurs premiers des nombres ressemblera à ceci :
; .
La décomposition en facteurs premiers des nombres , , peut être représentée sous une autre forme :

198	2	2574	2	255	3
	3	1287	3		5
	3		3		17
	11		11
			13

Maintenant, je vais écrire ça sur une ligne
.

Très bien! Tu es juste un génie.

Je ne comprends toujours pas comment tu as deviné si vite que le nombre est divisible par ?

Et c'est simple. J'ai utilisé le test de divisibilité par . Faisons attention au fait que dans les œuvres que vous venez d'enregistrer, le numéro est répété.

Définition

Le nombre par lequel chacun de ces nombres est divisé est appelé le diviseur commun de ces nombres.

Ceux. dans notre cas, le nombre est le diviseur commun ?

Oui, c'est ce que je voulais dire. Et si nous prenons les nombres et , alors, comme vous pouvez le voir, ils ont trois diviseurs communs : , et (sans compter ).

Je ne comprends pas?...

Définition

Le plus grand diviseur commun de ces nombres est appelé leur plus grand diviseur commun et est abrégé en PGCD.

Vous devez vous rappeler que GCD joue un rôle important en mathématiques.

Je vois déjà qu’en mathématiques tous les concepts jouent un grand rôle. Et comment se souvenir de tous ? Comment trouver ce GCD ?

Ne vous inquiétez pas, ils deviendront mémorables avec le temps si vous les utilisez régulièrement.
Alors continuons. Pour trouver PGCD plusieurs nombres, vous pouvez les factoriser en facteurs premiers, écrire leurs facteurs premiers communs et multiplier.

C'est bien. Mais il existe des nombres qui n’ont pas d’autre diviseur commun que un ! Par exemple, et , et .

Oui, vous avez bien remarqué.

Définition

Les nombres qui n'ont pas de diviseur commun (sauf un) sont appelés relativement premiers.

Alors qu’est-ce que cela signifie : tous les nombres premiers seront également relativement premiers ?

Et dans ce cas, vous avez raison ! Cependant, nous devons encore considérer un concept tel que le plus petit commun multiple du LCM.

Définition

Le nombre divisible par chacun de ces nombres est appelé le commun multiple de ces nombres.

Ainsi, pour les nombres et le commun multiple sera chacun des nombres : , , , , LCM.

Bien joué. Selon vous, quel sera le LCM des nombres premiers entre eux ?

Je vais le découvrir maintenant. Ils n’ont pas de diviseur commun autre que l’unité, et donc leur produit est leur LCM !

C'est tout simplement incroyable ! Quelle belle conclusion.
Et à la fin de nos recherches, j'ai envie de vous dire comment trouver le LOC s'il n'est pas évident.

Dans ce cas, ces nombres sont décomposés en facteurs premiers. Ensuite, tous les facteurs sont écrits à partir du plus grand nombre et les facteurs manquants issus des développements des nombres restants leur sont ajoutés.

Oui, je suis satisfait, j'ai aimé.

Cet article concerne trouver le plus grand diviseur commun (PGCD) deux nombres ou plus. Tout d'abord, regardons l'algorithme d'Euclide ; il vous permet de trouver le pgcd de deux nombres. Après cela, nous nous concentrerons sur une méthode qui nous permet de calculer le pgcd des nombres comme le produit de leurs facteurs premiers communs. Ensuite, nous chercherons à trouver le plus grand diviseur commun de trois nombres ou plus, et donnerons également des exemples de calcul du pgcd de nombres négatifs.

Navigation dans les pages.

Algorithme euclidien pour trouver GCD

A noter que si nous nous étions tournés dès le début vers le tableau des nombres premiers, nous aurions découvert que les nombres 661 et 113 sont des nombres premiers, à partir desquels nous pourrions immédiatement dire que leur plus grand diviseur commun est 1.

Répondre:

PGCD(661, 113)=1 .

Trouver GCD en factorisant les nombres en facteurs premiers

Considérons une autre façon de trouver GCD. Le plus grand diviseur commun peut être trouvé en factorisant les nombres en facteurs premiers. Formulons une règle : Le pgcd de deux entiers positifs a et b est égal au produit de tous les facteurs premiers communs trouvés dans les factorisations premières des nombres a et b..

Donnons un exemple pour expliquer la règle permettant de trouver GCD. Connaissons les décompositions des nombres 220 et 600 en facteurs premiers, ils ont la forme 220=2·2·5·11 et 600=2·2·2·3·5·5. Les facteurs premiers communs impliqués dans la factorisation des nombres 220 et 600 sont 2, 2 et 5. Par conséquent, pgcd(220, 600)=2·2·5=20.

Ainsi, si nous factorisons les nombres a et b en facteurs premiers et trouvons le produit de tous leurs facteurs communs, alors nous trouverons le plus grand diviseur commun des nombres a et b.

Considérons un exemple de recherche de GCD selon la règle indiquée.

Exemple.

Trouvez le plus grand diviseur commun des nombres 72 et 96.

Solution.

Factorisons les nombres 72 et 96 en facteurs premiers :

Autrement dit, 72=2·2·2·3·3 et 96=2·2·2·2·2·3. Les facteurs premiers communs sont 2, 2, 2 et 3. Ainsi, pgcd(72, 96)=2·2·2·3=24.

Répondre:

PGCD(72, 96)=24 .

En conclusion de ce paragraphe, nous notons que la validité de la règle ci-dessus pour trouver GCD découle de la propriété du plus grand commun diviseur, qui stipule que PGCD(m une 1 , m b 1)=m PGCD(une 1 , b 1), où m est un entier positif.

Trouver le pgcd de trois nombres ou plus

La recherche du plus grand diviseur commun de trois nombres ou plus peut être réduite à la recherche séquentielle du pgcd de deux nombres. Nous l'avons mentionné lors de l'étude des propriétés de GCD. Là, nous avons formulé et prouvé le théorème : le plus grand diviseur commun de plusieurs nombres a 1, a 2, ..., a k est égal au nombre d k, qui se trouve en calculant séquentiellement PGCD(a 1, a 2)=d 2 , PGCD(d 2, a 3) =d 3, PGCD(d 3, a 4)=d 4,..., PGCD(d k-1, a k)=d k.

Voyons à quoi ressemble le processus de recherche du pgcd de plusieurs nombres en regardant la solution de l'exemple.

Exemple.

Trouvez le plus grand commun diviseur de quatre nombres 78, 294, 570 et 36.

Solution.

Dans cet exemple, un 1 =78, un 2 =294, un 3 =570, un 4 =36.

Tout d'abord, à l'aide de l'algorithme euclidien, nous déterminons le plus grand diviseur commun d 2 des deux premiers nombres 78 et 294. En divisant, on obtient les égalités 294 = 78 3 + 60 ; 78=60·1+18 ; 60=18·3+6 et 18=6·3. Ainsi, d 2 =PGCD(78, 294)=6.

Maintenant calculons ré 3 =PGCD(d 2, une 3)=PGCD(6, 570). Appliquons à nouveau l'algorithme euclidien : 570=6·95, donc d 3 = PGCD(6, 570)=6.

Reste à calculer ré 4 =PGCD(d 3, une 4)=PGCD(6, 36). Puisque 36 est divisible par 6, alors d 4 = PGCD(6, 36) = 6.

Ainsi, le plus grand diviseur commun des quatre nombres donnés est d 4 =6, c'est-à-dire pgcd(78, 294, 570, 36)=6.

Répondre:

PGCD(78, 294, 570, 36)=6 .

La factorisation des nombres en facteurs premiers vous permet également de calculer le pgcd de trois nombres ou plus. Dans ce cas, le plus grand diviseur commun est le produit de tous les facteurs premiers communs des nombres donnés.

Exemple.

Calculez le pgcd des nombres de l'exemple précédent en utilisant leurs factorisations premières.

Solution.

Factorisons les nombres 78, 294, 570 et 36 en facteurs premiers, nous obtenons 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2 ·3· 3. Les facteurs premiers communs à ces quatre nombres sont les nombres 2 et 3. Ainsi, PGCD(78, 294, 570, 36)=2·3=6.