EntréeNombres premiers entre eux 12. Nombres premiers entre eux : définition, exemples et propriétés
$p$ est appelé nombre premier s'il n'a que $2$ diviseurs : $1$ et lui-même.
Le diviseur d'un nombre naturel $a$ est un nombre naturel qui divise le nombre d'origine $a$ sans laisser de reste.
Exemple 1
Trouvez les diviseurs du nombre $6$.
Solution : Nous devons trouver tous les nombres par lesquels le nombre donné $6$ est divisible sans reste. Ce seront les nombres : 1,2,3 $, 6 $. Ainsi, le diviseur du nombre $6$ sera les nombres $1,2,3,6.$
Réponse : 1,2,3,6$.
Cela signifie que pour trouver les diviseurs d’un nombre, vous devez trouver tous entiers, dans lequel le donné est divisé sans reste. Il est facile de voir que le nombre $1$ sera un diviseur de n’importe quel nombre naturel.
Définition 2
Composite Ils appellent un nombre qui a d’autres diviseurs que lui-même et un.
Un exemple de nombre premier serait le nombre $13$, un exemple de nombre composé serait $14.$
Note 1
Le nombre $1$ n'a qu'un seul diviseur : le nombre lui-même, il n'est donc ni premier ni composite.
Nombres premiers entre eux
Définition 3
Nombres mutuellement premiers ce sont ceux dont le pgcd est égal à 1$. Cela signifie que pour savoir si les nombres sont relativement premiers, il faut trouver leur pgcd et le comparer avec 1$.
Premiers par paires
Définition 4
Si dans un ensemble de nombres deux nombres sont premiers entre eux, alors ces nombres sont appelés premier par paire. Pour deux nombres, les notions « coprime » et « copremier par paire » coïncident.
Exemple 2
8 $, 15 $ – pas simple, mais relativement simple.
$6, 8, 9$ sont des nombres premiers entre eux, mais pas des nombres premiers entre eux par paire.
8 $, 15, 49 $ sont relativement premiers par paire.
Comme nous le voyons, afin de déterminer si les nombres sont relativement premiers, il faut d’abord les factoriser en facteurs premiers. Faisons attention à la façon de procéder correctement.
Factorisation première
Par exemple, factorisons le nombre $180$ en facteurs premiers :
180$=2\cdot 2\cdot 3\cdot 3\cdot 5$
Utilisons la propriété des puissances, alors nous obtenons,
180$=2^2\cdot 3^2\cdot 5$
Cette notation de décomposition en facteurs premiers est dite canonique, c'est-à-dire pour factoriser un nombre sous forme canonique, il faut utiliser la propriété des puissances et représenter le nombre comme un produit de puissances avec pour des raisons différentes
Développement canonique d'un nombre naturel sous forme générale
Développement canonique d'un nombre naturel dans vue générale a la forme :
$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$
où $p_1,p_2\dots \dots .p_k$ sont des nombres premiers et les exposants sont des nombres naturels.
Représenter un nombre comme une décomposition canonique en ensembles premiers facilite la recherche du plus grand diviseur commun des nombres et agit comme une conséquence de la preuve ou de la définition des nombres premiers entre eux.
Exemple 3
Trouvez le plus grand diviseur commun des nombres 180$ et 240$.
Solution : Décomposons les nombres en ensembles simples en utilisant la décomposition canonique
180$=2\cdot 2\cdot 3\cdot 3\cdot 5$, puis 180$=2^2\cdot 3^2\cdot 5$
240 $ = 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, puis 240 $=2^4\cdot 3\cdot 5$
Trouvons maintenant le pgcd de ces nombres, pour cela on choisit des puissances de même base et de plus petit exposant, puis
$PGCD\(180;240)= 2^2\cdot 3\cdot 5=60$
Composons algorithme de recherche de GCD prenant en compte la factorisation canonique en facteurs premiers.
Pour trouver le plus grand diviseur commun de deux nombres par développement canonique, vous devez :
- factoriser les nombres en facteurs premiers sous forme canonique
- choisir des puissances de même base et avec le plus petit exposant des puissances incluses dans le développement de ces nombres
- Trouvez le produit des nombres trouvés à l’étape 2. Le nombre obtenu sera le plus grand diviseur commun souhaité.
Exemple 4
Déterminez si les nombres $195$ et $336$ sont des nombres premiers entre eux.
195$=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$PGCD\(195;336) =3\cdot 5=15$
Nous voyons que le pgcd de ces nombres est différent de $1$, ce qui signifie que les nombres ne sont pas relativement premiers. On voit aussi que chacun des nombres comprend des facteurs, en plus de 1$ et du nombre lui-même, ce qui signifie que les nombres ne seront pas premiers, mais seront composés.
Exemple 5
Déterminez si les nombres $39$ et $112$ sont des nombres premiers entre eux.
Solution : Utilisons la factorisation canonique :
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$PGCD\(39;112)=1$
On voit que le pgcd de ces nombres est égal à $1$, ce qui signifie que les nombres sont relativement premiers. On voit aussi que chacun des nombres comprend des facteurs, en plus de 1$ et du nombre lui-même, ce qui signifie que les nombres ne seront pas premiers, mais seront composés.
Exemple 6
Déterminez si les nombres $883$ et $997$ sont des nombres premiers entre eux.
Solution : Utilisons la factorisation canonique :
883$=1\cdot 883$
997$=1\cdot 997$
$PGCD\(883;997)=1$
On voit que le pgcd de ces nombres est égal à $1$, ce qui signifie que les nombres sont relativement premiers. On voit aussi que chaque nombre ne comprend que des facteurs égaux à 1$ et le nombre lui-même, ce qui signifie que les nombres seront premiers.
Les informations contenues dans cet article couvrent le sujet " nombres premiers entre eux" Tout d’abord, la définition de deux nombres premiers entre eux est donnée, ainsi que la définition de trois nombres premiers entre eux ou plus. Après cela, des exemples de nombres premiers entre eux sont donnés, et il est montré comment prouver que des nombres donnés sont premiers entre eux. Ce qui suit répertorie et prouve les propriétés de base des nombres premiers entre eux. Enfin, les nombres premiers par paire sont mentionnés car ils sont étroitement liés aux nombres premiers entre eux.
Navigation dans les pages.
Il existe souvent des tâches dans lesquelles vous devez prouver que des nombres entiers donnés sont premiers entre eux. La preuve se résume à calculer le plus grand diviseur commun des nombres donnés et à vérifier le pgcd pour voir s'il est égal à un. Il est également utile de regarder le tableau des nombres premiers avant de calculer PGCD : du coup les entiers d'origine sont premiers, et on sait que le plus grand commun diviseur des nombres premiers est égal à un. Regardons l'exemple de solution.
Exemple.
Montrer que les nombres 84 et 275 sont premiers entre eux.
Solution.
Évidemment, ces nombres ne sont pas premiers, on ne peut donc pas parler immédiatement du nombre premier relatif des nombres 84 et 275, et il faudra calculer le pgcd. Nous utilisons l'algorithme euclidien pour trouver GCD : 275=84·3+23, 84=23·3+15, 23=15·1+8, 15=8·1+7, 8=7·1+1, 7 =7 ·1, donc pgcd(84, 275)=1. Cela prouve que les nombres 84 et 275 sont premiers entre eux.
La définition des nombres premiers entre eux peut être étendue à trois nombres ou plus.
Définition.
Les entiers a 1 , a 2 , …, a k , k>2 sont appelés mutuellement premier, si le plus grand diviseur commun de ces nombres est égal à un.
De la définition énoncée, il s'ensuit que si un certain ensemble d'entiers a un diviseur commun positif autre qu'un, alors ces entiers ne sont pas premiers entre eux.
Donnons des exemples. Trois entiers −99, 17 et −27 sont premiers entre eux. Toute collection de nombres premiers constitue un ensemble de nombres premiers entre eux, par exemple 2, 3, 11, 19, 151, 293 et 677 sont des nombres premiers entre eux. Et les quatre nombres 12, −9, 900 et −72 ne sont pas premiers entre eux car ils ont un diviseur commun positif 3 autre que 1. Les nombres 17, 85 et 187 ne sont pas non plus premiers, puisque chacun d’eux est divisible par 17.
Il est généralement loin d’être évident que certains nombres soient relativement premiers, et ce fait doit être prouvé. Pour savoir si des nombres donnés sont premiers entre eux, vous devez trouver le plus grand diviseur commun de ces nombres et tirer une conclusion basée sur la définition des nombres premiers entre eux.
Exemple.
Les nombres 331, 463 et 733 sont-ils relativement premiers ?
Solution.
En regardant le tableau des nombres premiers, nous constaterons que chacun des nombres 331, 463 et 733 est premier. Par conséquent, ils ont un seul diviseur commun positif : un. Ainsi, les trois nombres 331, 463 et 733 sont des nombres relativement premiers.
Répondre:
Oui.
Exemple.
Montrer que les nombres −14 , 105 , −2 107 et −91 ne sont pas premiers entre eux.
Solution.
Pour prouver que ces nombres ne sont pas premiers, vous pouvez trouver leur pgcd et vous assurer qu’il n’est pas égal à un. C'est ce que nous ferons.
Puisque les diviseurs des entiers négatifs coïncident avec les diviseurs des entiers correspondants, alors PGCD(−14, 105, 2 107, −91)= PGCD(14, 105, 2 107, 91) . En ce qui concerne le contenu de l'article sur la recherche du plus grand diviseur commun de trois nombres ou plus, nous découvrons que PGCD(14, 105, 2 107, 91) = 7. Par conséquent, le plus grand commun diviseur des nombres d’origine est sept, ces nombres ne sont donc pas premiers entre eux.
Propriétés des nombres premiers
Les nombres premiers ont un certain nombre de propriétés. Regardons l'essentiel propriétés des nombres premiers entre eux.
Les nombres obtenus en divisant les entiers a et b par leur plus grand diviseur commun sont premiers entre eux, c'est-à-dire que a:PGCD(a, b) et b:PGCD(a, b) sont premiers entre eux.
Nous avons prouvé cette propriété en examinant les propriétés de GCD.
La propriété considérée des nombres premiers entre eux nous permet de trouver des paires de nombres premiers entre eux. Pour ce faire, il suffit de prendre deux entiers quelconques et de les diviser par le plus grand diviseur commun, les nombres résultants seront relativement premiers.
Pour que les entiers a et b soient premiers entre eux, il faut et il suffit qu'il existe des entiers u 0 et v 0 tels que au·u 0 +b·v 0 =1.
Montrons d'abord la nécessité.
Soit les nombres a et b relativement premiers. Alors, par la définition des nombres premiers entre eux, pgcd(a, b)=1. Et d'après les propriétés de GCD, nous savons que pour les entiers a et b, la relation de Bezout au·u 0 +b·v 0 =PGCD(a, b) est vraie. Par conséquent, au·u 0 +b·v 0 =1.
Reste à prouver la suffisance.
Soit l'égalité au·u 0 +b·v 0 =1. Puisque GCD(a, b) divise à la fois a et b, alors GCD(a, b), en raison des propriétés de divisibilité, doit diviser la somme au·u 0 +b·v 0, et donc l'unité. Et cela n’est possible que lorsque GCD(a, b)=1. Par conséquent, a et b sont des nombres relativement premiers.
Propriété suivante les nombres premiers entre eux sont les suivants : si les nombres a et b sont premiers entre eux et que le produit a·c est divisible par b, alors c est divisible par b.
En effet, puisque a et b sont premiers entre eux, alors d'après la propriété précédente nous avons l'égalité au·u 0 +b·v 0 =1. En multipliant les deux côtés de cette égalité par c, nous avons a·c·u 0 +b·c·v 0 =c. Le premier terme de la somme a·c·u 0 +b·c·v 0 est divisé par b, puisque a·c est divisé par b selon la condition, le deuxième terme de cette somme est également divisé par b, puisque l'un des facteurs est égal à b, donc la somme entière est divisée par b. Et puisque la somme a·c·u 0 + b·c·v 0 est égale à c, alors c est divisible par b.
Si les nombres a et b sont relativement premiers, alors pgcd(a c, b) = pgcd(c, b) .
Montrons, d'une part, que pgcd(a c, b) divise pgcd(c, b), et d'autre part, que pgcd(c, b) divise pgcd(a c, b), cela prouvera l'égalité GCD(a c, b) =PGCD(c,b) .
GCD(a c, b) divise à la fois a c et b, et puisque pgcd(a c, b) divise b, il divise également b c. C'est-à-dire que pgcd(a c, b) divise à la fois a c et b c, donc, en raison des propriétés du plus grand diviseur commun, il divise également pgcd(a c, b c), qui, selon les propriétés de pgcd, est égal à c PGCD(a, b)=c . Ainsi, pgcd(a c, b) divise à la fois b et c, donc divise également pgcd(c, b).
D'un autre côté, PGCD(c, b) divise à la fois c et b, et puisqu'il divise c, il divise également a·c. Ainsi, pgcd(c, b) divise à la fois a c et b, par conséquent, il divise également pgcd(a c, b).
Nous avons donc montré que pgcd(a c, b) et pgcd(c, b) se divisent mutuellement, ce qui signifie qu’ils sont égaux.
Si chacun des nombres a 1 , a 2 , …, a k est premier avec chacun des nombres b 1 , b 2 , …, b m (où k et m sont des nombres naturels), alors les produits a 1 · a 2 · … · a k et b 1 · b 2 ·…·b m sont des nombres premiers entre eux, en particulier, si a 1 =a 2 =…=a k =a et b 1 =b 2 =…=b m =b, alors a k et b m sont nombres premiers entre eux.
La propriété précédente des nombres premiers entre eux permet d’écrire une série d’égalités de la forme PGCD(une 1 · une 2 ·…·une k , b m)= PGCD(une 2 ·…·une k , b m)=…=PGCD(une k , b m)=1, où la dernière transition est possible, puisque a k et b m sont des nombres mutuellement premiers par condition. Donc, PGCD(une 1 · une 2 ·…·une k , b m)=1.
Maintenant, notant a 1 ·a 2 ·…·a k =A, nous avons
PGCD(b 1 ·b 2 ·…·b m , une 1 ·une 2 ·…·une k)= PGCD(b 1 · b 2 ·…·b m , A)=
=PGCD(b 2 ·…·b m , A)=… =PGCD(b m , A)=1
(la dernière transition est valide, du fait de la dernière égalité du paragraphe précédent). C'est ainsi que nous avons obtenu l'égalité PGCD(b 1 ·b 2 ·…·b m , une 1 ·une 2 ·…·une k)=1, ce qui prouve que les produits a 1 ·a 2 ·…·ak et b 1 ·b 2 ·…·b m sont des nombres premiers entre eux.
Ceci conclut notre examen des propriétés fondamentales des nombres premiers entre eux.
Nombres premiers par paires - définitions et exemples
Par les nombres premiers, on donne identifier des paires de nombres premiers.
Définition.
Les entiers a 1, a 2, …, a k, dont chacun est premier relativement à tous les autres, sont appelés nombres premiers par paire.
Donnons un exemple de nombres premiers par paire. Les nombres 14, 9, 17 et −25 sont premiers par paires, puisque les paires de nombres 14 et 9, 14 et 17, 14 et −25, 9 et 17, 9 et −25, 17 et −25 sont des nombres premiers entre eux. Nous notons ici que les nombres premiers par paire sont toujours premiers entre eux.
D’un autre côté, les nombres relativement premiers ne sont pas toujours premiers par paire, comme le confirme l’exemple suivant. Les nombres 8, 16, 5 et 15 ne sont pas premiers par paire, puisque les nombres 8 et 16 ne sont pas premiers entre eux. Cependant, les nombres 8, 16, 5 et 15 sont relativement premiers. Ainsi, 8, 16, 5 et 15 sont des nombres relativement premiers, mais pas premiers par paire.
Il faut surtout souligner la collection d'un certain nombre de nombres premiers. Ces nombres sont toujours à la fois premiers relativement et premiers par paires. Par exemple, 71, 443, 857, 991 sont tous deux des nombres premiers et premiers entre eux.
Il est également clair que lorsque nous parlons de environ deux entiers, alors pour eux les concepts de « premier par paire » et de « mutuellement premier » coïncident.
Bibliographie.
- Vilenkin N.Ya. et d'autres. 6e année : manuel pour les établissements d'enseignement général.
- Vinogradov I.M. Fondamentaux de la théorie des nombres.
- Mikhelovich Sh.H. La théorie du nombre.
- Kulikov L.Ya. et autres. Recueil de problèmes d'algèbre et de théorie des nombres : Didacticiel pour les étudiants en physique et en mathématiques. spécialités des instituts pédagogiques.
Définition1. Entiers a 1,a 2,…,ak sont appelés co-premiers si (a 1 ,a 2 ,…,ak) =1
Définition 2. Les entiers a 1,a 2,…,ak sont appelés premiers par paire si i,s (i, s = 1, 2, .. , k, is, (a i, a s) =1) .
Si les nombres satisfont à la définition 2, alors ils satisfont à la définition 1. L'énoncé inverse est généralement faux, par exemple : (15, 21, 19) = 1, mais (15, 21) = 3
Théorème (critère co-premier)
(une, b) = 1<=> x, y Z : hache + par = 1
Preuve:
Prouvons la nécessité. Soit (a, b) = 1. Ci-dessus nous avons montré que si d = (a, b), alors x, y Z : d = ax + by.
Parce que dans ce cas d =1, alors il y aura x, y Z (déterminé à partir de l'algorithme euclidien) : 1 = ax + bу.
Adéquation. Soit (*) ax + by = 1, prouvons que (a, b)=1. Supposons que (a, b) = d, alors du côté gauche de l'égalité (*)
(un / d ) & ( b/d ) => (ah + par) /d => (1/d) => (d=l) => (une, b) = 1.
§4. Nok d'entiers et ses propriétés.
Définition 1. Le commun multiple d'un ensemble fini d'entiers a 1,a 2,…,a k, différent de zéro, est un entier m divisible par tous les nombres a i (i=l, 2,…, k)
Définition 2. Un entier (m) est appelé le plus petit commun multiple des nombres a 1, a 2,...,ak, différent de zéro, si :
1 m - est leur multiple commun ;
2 (m) divise tout autre multiple commun de ces nombres.
Désignation : m = LCM (a 1,a 2,…,a k) ou m = [a 1,a 2,…,a k]
Exemple. Les nombres sont donnés : 2, 3, 4, 6, 12.
Les nombres 12, 24, 48, 96 sont des multiples communs des nombres 2, 3, 4, 6, 12. Le multiple le plus petit est le nombre 12. c'est-à-dire
Le LCM est déterminé de manière unique en fonction de l'ordre des facteurs. En effet, si l'on suppose que m 1 = [a, b] &m 2 = (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Il existe une relation entre le plus petit commun multiple et le plus grand commun diviseur de deux entiers, qui s'exprime par la formule : [a, b] = ab/(a, b) (dérivez-la vous-même)
Cette connexion nous permet d'affirmer que pour toute paire d'entiers autres que zéro, il existe leur plus petit commun multiple. En effet, (a, b) peut toujours être déduit sans ambiguïté de l'algorithme euclidien et par définition (a, b) 0, alors la fraction ab/(a, b) 0 sera déterminée de manière unique.
Le LCM de deux entiers est plus facilement calculé dans le cas où (a, b) = 1, alors [a, b] = ab/1 = a b
Par exemple, = 215/1 = 105, car (21, 5) = 1.
§5. Nombres premiers et leurs propriétés.
Définition 1. Un nombre naturel (p) est dit premier si p > 1 et n'a pas de nombre positif. diviseurs autres que 1 et p.
Définition 2. Un nombre naturel a > 1 qui a d'autres diviseurs positifs que 1 et lui-même est appelé composite.
De ces définitions, il résulte que l'ensemble des nombres naturels peut être divisé en trois classes :
a) nombres composés ;
b) les nombres premiers ;
c) unité.
Si a est composite, alors a = nq, où 1 Tache 1. Montrer que si aZ et p sont un nombre premier, alors (a, p) = 1 v (a / p) Preuve. Soit d = (a, p) =>
(a /d) & (p /d), car p est un nombre premier, alors il a deux diviseurs 1 et p. Si (a, p) = 1, alors a et p sont premiers entre eux, si (a, p) = p, alors (a/p). Tâche 2. Si le produit de plusieurs facteurs est divisible par p, alors au moins un des facteurs est divisible par p. Solution. Soit le produit (a 1,a 2, ...,
et k)/р, si tous a i ne sont pas divisibles par p, alors le produit sera premier avec p, donc un facteur est divisible par p. Tâche 3. Montrer que le plus petit diviseur non 1 d'un entier a>1 est un nombre premier. Preuve. Soient aZ et a un nombre composé (si a = p, alors l'énoncé est prouvé), alors a = a 1 q. Soit q le plus petit diviseur, montrons que ce sera un nombre premier. Si nous supposons que q est un nombre composé, alors q = q 1 k et a = a 1 q 1 k, car q1 Tâche 4. Montrer que le plus petit diviseur premier (p) d'un entier naturel (n) n'excède pas n. Preuve. Soit n = pn 1, et p< n 1
и р - простое. Тогда n
р 2
=>R.<n
. De cette affirmation, il s'ensuit que si un nombre naturel (n) n'est divisible par aucun nombre premier p n, alors n est premier, sinon il sera composé. Exemple 1. Découvrez si 137 est un nombre premier ? onze<137
<12. On note les facteurs premiers n'excédant pas 137 : 2, 3, 5, 7, 11. On vérifie que 137 n'est pas divisible par 2, 3, 5, 7, 11. Le nombre 137 est donc premier. Théorème d'Euclide. L'ensemble des nombres premiers est infini. Preuve. Supposons le contraire, soit p 1 ,p 2 , ...,
p k sont tous des nombres premiers, où p 1 = 2 et p k est le plus grand nombre premier. Composons un nombre naturel = p 1 p 2 ...
p à +1, car p i , alors il doit être composé, alors son plus petit diviseur sera premier (voir problème 3). Cependant, n'est divisible ni par p 1, ni par p 2,..., ni par p k, car 1 n’est divisible par aucun p I. Par conséquent, notre hypothèse selon laquelle l’ensemble des nombres premiers est fini était incorrecte. Cependant, il existe un théorème selon lequel les nombres premiers ne constituent qu’une petite partie des nombres naturels. Théorème de l'intervalle. Dans la série naturelle, il existe des intervalles arbitrairement longs qui ne contiennent pas un seul nombre premier. Preuve. Prenons un nombre naturel arbitraire (n) et créons une séquence de nombres naturels (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1). Dans cette séquence, chaque nombre suivant est supérieur de 1 au précédent, tous ces nombres sont composés, car ; chacun a plus de deux diviseurs (par exemple, le premier nombre est divisible par 1, par 2 et par lui-même). Comme n → ∞ nous obtenons un intervalle arbitrairement long composé uniquement de nombres composés. Le théorème d'Euclide et le théorème des intervalles indiquent la nature complexe de la distribution des nombres premiers dans la série naturelle. Théorème fondamental de l'arithmétique Tout nombre naturel n>1 peut être représenté de manière unique comme un produit de nombres premiers, à l'ordre des facteurs. Preuve. Montrons la possibilité de représentation : Soient nN et n>1, si n est un nombre premier, alors n = p et le théorème est prouvé. Si n est composite, alors son plus petit diviseur sera un nombre premier et n = p 1 n 1 , où n 1 Ensuite, nous argumentons de la même manière. Si n 1 est un nombre premier, alors le théorème est prouvé, si n 1 est un nombre composé, alors n 1 = p 2 n 2 , où n 2< n 1
и тогда n
= p 1 p 2 n 2
. На каком-то шаге получим n
= p 1 p 2
…p n
, где все p i
- простые числа. Montrons l'unicité de la décomposition : Supposons qu'il existe deux représentations différentes pour le nombre (n) : n = p 1 p 2 …p k , n = q 1 q 2 …q n et n>k. Nous obtenons alors que p 1 p 2 …p k = q 1 q 2 …q n (1). Le côté gauche de l'égalité (1) est divisible par p 1 , donc, par la propriété des nombres premiers (voir Problème 2), au moins un des facteurs du côté droit doit être divisible par p 1 . Soit (q 1 /p 1) => (q 1 =p 1). En divisant les deux côtés de l'égalité (1) par p 1, nous obtenons l'égalité p 2 p 3 …p k = q 2 q 3 …q n. En répétant le raisonnement précédent encore (k-1) fois, nous obtenons l'égalité 1 = q k +1 q k +2 …q n , car tout q i >1, alors cette égalité est impossible. Par conséquent, dans les deux expansions, le nombre de facteurs est le même (k=n) et les facteurs eux-mêmes sont les mêmes. Commentaire. Lors de la décomposition d'un nombre (n) en facteurs simples, certains d'entre eux peuvent être répétés. En désignant par les lettres 1 , 2 ,…, k la multiplicité de leur occurrence dans (n), on obtient le développement dit canonique du nombre (n) : Exemple 2. Développement canonique du nombre 588000 = 2 5 35 3 7 2 Corollaire 1. Si Exemple 3. Tous les diviseurs du nombre 720 = 2 4 3 2 5 sont obtenus si dans l'expression Les diviseurs requis seront égaux à : 1 ; 2 ; 4 ; 8 ; 16 ; 3 ; 6 ; 12 ; 24 ; 48 ; 9 ; 18 ; 36 ; 72 ; 144 ; 5 ; dix; 20 ; 40 ; 80 ; 15 ; trente; 60 ; 120 ; 240 ; 45 ; 90 ; 180 ; 360 ; 720. Corollaire 2. Si P 1 1 p 2 2 …p k k, où i = max( I , i). Exemple 4. Trouvez GCD(a, b) et LCM(a, b) en utilisant le développement canonique si (24,
42) = 23
= 6 $p$ est appelé nombre premier s'il n'a que $2$ diviseurs : $1$ et lui-même. Le diviseur d'un nombre naturel $a$ est un nombre naturel qui divise le nombre d'origine $a$ sans laisser de reste. Exemple 1 Trouvez les diviseurs du nombre $6$. Solution : Nous devons trouver tous les nombres par lesquels le nombre donné $6$ est divisible sans reste. Ce seront les nombres : 1,2,3 $, 6 $. Ainsi, le diviseur du nombre $6$ sera les nombres $1,2,3,6.$ Réponse : 1,2,3,6$. Cela signifie que pour trouver les diviseurs d'un nombre, vous devez trouver tous les nombres naturels par lesquels le nombre donné est divisible sans reste. Il est facile de voir que le nombre $1$ sera un diviseur de n’importe quel nombre naturel. Définition 2 Composite Ils appellent un nombre qui a d’autres diviseurs que lui-même et un. Un exemple de nombre premier serait le nombre $13$, un exemple de nombre composé serait $14.$ Note 1 Le nombre $1$ n'a qu'un seul diviseur : le nombre lui-même, il n'est donc ni premier ni composite. Définition 3 Nombres mutuellement premiers ce sont ceux dont le pgcd est égal à 1$. Cela signifie que pour savoir si les nombres sont relativement premiers, il faut trouver leur pgcd et le comparer avec 1$. Définition 4 Si dans un ensemble de nombres deux nombres sont premiers entre eux, alors ces nombres sont appelés premier par paire. Pour deux nombres, les notions « coprime » et « copremier par paire » coïncident. Exemple 2 8 $, 15 $ – pas simple, mais relativement simple. $6, 8, 9$ sont des nombres premiers entre eux, mais pas des nombres premiers entre eux par paire. 8 $, 15, 49 $ sont relativement premiers par paire. Comme nous le voyons, afin de déterminer si les nombres sont relativement premiers, il faut d’abord les factoriser en facteurs premiers. Faisons attention à la façon de procéder correctement. Par exemple, factorisons le nombre $180$ en facteurs premiers : 180$=2\cdot 2\cdot 3\cdot 3\cdot 5$ Utilisons la propriété des puissances, alors nous obtenons, 180$=2^2\cdot 3^2\cdot 5$ Cette notation de décomposition en facteurs premiers est dite canonique, c'est-à-dire pour factoriser un nombre sous forme canonique, il faut utiliser la propriété des puissances et représenter le nombre comme un produit de puissances avec des bases différentes Le développement canonique d'un nombre naturel sous forme générale a la forme : $m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$ où $p_1,p_2\dots \dots .p_k$ sont des nombres premiers et les exposants sont des nombres naturels. Représenter un nombre comme une décomposition canonique en ensembles premiers facilite la recherche du plus grand diviseur commun des nombres et agit comme une conséquence de la preuve ou de la définition des nombres premiers entre eux. Exemple 3 Trouvez le plus grand diviseur commun des nombres 180$ et 240$. Solution : Décomposons les nombres en ensembles simples en utilisant la décomposition canonique 180$=2\cdot 2\cdot 3\cdot 3\cdot 5$, puis 180$=2^2\cdot 3^2\cdot 5$ 240 $ = 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, puis 240 $=2^4\cdot 3\cdot 5$ Trouvons maintenant le pgcd de ces nombres, pour cela on choisit des puissances de même base et de plus petit exposant, puis $PGCD\(180;240)= 2^2\cdot 3\cdot 5=60$ Composons algorithme de recherche de GCD prenant en compte la factorisation canonique en facteurs premiers. Pour trouver le plus grand diviseur commun de deux nombres par développement canonique, vous devez : Exemple 4 Déterminez si les nombres $195$ et $336$ sont des nombres premiers entre eux. 195$=3\cdot 5\cdot 13$ $336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$ $PGCD\(195;336) =3\cdot 5=15$ Nous voyons que le pgcd de ces nombres est différent de $1$, ce qui signifie que les nombres ne sont pas relativement premiers. On voit aussi que chacun des nombres comprend des facteurs, en plus de 1$ et du nombre lui-même, ce qui signifie que les nombres ne seront pas premiers, mais seront composés. Exemple 5 Déterminez si les nombres $39$ et $112$ sont des nombres premiers entre eux. Solution : Utilisons la factorisation canonique : $112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$ $PGCD\(39;112)=1$ On voit que le pgcd de ces nombres est égal à $1$, ce qui signifie que les nombres sont relativement premiers. On voit aussi que chacun des nombres comprend des facteurs, en plus de 1$ et du nombre lui-même, ce qui signifie que les nombres ne seront pas premiers, mais seront composés. Exemple 6 Déterminez si les nombres $883$ et $997$ sont des nombres premiers entre eux. Solution : Utilisons la factorisation canonique : 883$=1\cdot 883$ 997$=1\cdot 997$ $PGCD\(883;997)=1$ On voit que le pgcd de ces nombres est égal à $1$, ce qui signifie que les nombres sont relativement premiers. On voit aussi que chaque nombre ne comprend que des facteurs égaux à 1$ et le nombre lui-même, ce qui signifie que les nombres seront premiers. Que sont les nombres premiers entre eux ? Définition des nombres premiers entre eux : Les nombres premiers sont des nombres entiers qui n'ont pas d'autre diviseur commun que un. Exemple de nombres premiers entre eux : 2 et 3 n’ont pas d’autres diviseurs communs que un. Autre exemple de nombres premiers entre eux : 3 et 7 n’ont pas d’autres facteurs communs que un. Autre exemple de nombres premiers entre eux : 11 et 13 n’ont pas d’autres facteurs communs qu’un. Nous pouvons maintenant répondre à la question de savoir ce que signifient les nombres premiers entre eux. Que signifient les nombres premiers entre eux ? Ce sont des entiers qui n’ont pas de diviseur commun autre qu’un. Chacune de ces paires est constituée de deux nombres relativement premiers. 11 et 15 Les diviseurs communs des nombres premiers entre eux n’en sont qu’un, comme il ressort de la définition des nombres premiers entre eux. Le plus grand diviseur commun des nombres premiers entre eux est un, comme il ressort de la définition des nombres premiers entre eux. Les nombres 3 et 13 sont-ils premiers entre eux ? Oui, car ils n’ont pas de diviseur commun sauf un. Les nombres 3 et 12 sont-ils premiers entre eux ? Non, car leurs diviseurs communs sont 1 et 3. Et selon la définition des nombres premiers entre eux, le diviseur commun ne devrait être qu'un. Les nombres 3 et 108 sont-ils premiers entre eux ? Non, car leurs diviseurs communs sont 1 et 3. Et selon la définition des nombres premiers entre eux, le diviseur commun ne devrait être qu'un. Les nombres 108 et 5 sont-ils premiers entre eux ? Oui, car ils n’ont pas de diviseur commun sauf un.
alors tous les diviseurs du nombre (n) ont la forme : 
où 0 je je (i = 1, 2,…,k).
au lieu de 1, 2, 3, indépendamment les uns des autres, nous substituerons les valeurs suivantes : 1 =0, 1, 2, 3, 4, 2 =0, 1, 2, 3 = 0, 1.
Et 
alors (a, b) = p 1 1 p 2 2 …p k k , où i = min( I , i)
Nombres premiers entre eux
Premiers par paires
Factorisation première
Développement canonique d'un nombre naturel sous forme générale
Définition des nombres premiers entre eux
Exemples de nombres premiers entre eux
Deux nombres premiers entre eux
15 et 16
16 et 23Diviseurs communs de nombres premiers entre eux
Le plus grand diviseur commun des nombres premiers
Les nombres sont-ils premiers entre eux ?