Utilisateur:Proz/Brouillon

PGCD de deux entiers naturels strictement positifs

Par définition le PGCD de deux entiers naturels a et b tous deux non nuls est le plus grand des diviseurs que a et b ont en commun : il existe toujours au moins un diviseur commun, qui est 1, et l'ensemble des diviseurs communs est borné par a et par b, donc il en existe bien un plus grand.

Par exemple, les diviseurs de 24 sont {1, 2, 3, 4, 6, 8, 12, 24} et ceux de 30 sont {1, 2, 3, 5, 6, 10, 15, 30}. Les diviseurs communs à 24 et 30 sont {1, 2, 3, 6}. C'est l'intersection des deux ensembles précédents.

Le plus grand de ces diviseurs communs, appelé plus grand commun diviseur, est 6, on écrira donc : pgcd(24, 30) = 6.

La recherche de diviseurs communs est utile pour simplifier une fraction. Le plus grand d'entre eux permet d'obtenir par simplification une fraction irréductible. Ainsi, puisque 24 et 30 ont pour PGCD 6, on peut simplifier la fraction

24/30 = 6 × 4/6 × 5 = 4/5.

Calcul du PGCD par l'algorithme d'Euclide

Si a > b, un diviseur commun à a et b est aussi un diviseur commun a a − b et b, et inversement. Donc :

pgcd(a, b) = pgcd(a − b, b).

Euclide utilise cette propriété dans le livre VII des Éléments pour calculer le PGCD de deux entiers.

Exemple :

Ainsi

pgcd(90, 24) = pgcd(90 − 24, 24) = pgcd(66, 24) = pgcd(66 − 24, 24) = pgcd(42, 24) = pgcd(42 − 24, 24) = pgcd(18, 24) = pgcd(18, 24 − 18) = pgcd(6, 18) = 6

car 6 est un diviseur de 18, c'est bien le plus grand diviseur de 6 et 18 et donc de 90 et 24.

À chaque soustraction la somme des deux nombres en jeu diminue : a − b + b < a + b (car b > 0), donc la suite des soustractions est forcément finie.

Chaque soustraction d'un nombre est répétée jusqu'à trouver un nombre inférieur à celui-ci, c'est-à-dire que l'algorithme d'Euclide réalise une suite de divisions euclidiennes. On obtient donc un algorithme essentiellement équivalent en prenant le reste par la division euclidienne, plutôt que la soustraction, d'un nombre par un autre. C'est la version devenue classique de l'algorithme d'Euclide. Sur l'exemple précédent on obtient :

Exemple :

Ainsi, pour cherche le PGCD de 90 par 24, on divise 90 par 24 :

90 = 3 × 24 + 18

PGCD (90, 24} = PGCD (24, 18}

On divise 24 par 18

24 = 18 + 6

PGCD (90, 24} = PGCD (24, 18} = PGCD (18, 6}

Comme 6 est un diviseur de 18, c'est bien le plus grand diviseur de 6 et 18, et donc de 90 et 24.

Définitions

Entiers naturels

Les langages informatiques coïncident tous sur les entiers naturels, a mod n est le reste de la division euclidienne de a par n supposé non nul.

Extension aux nombres entiers négatifs et aux nombres réels

La division euclidienne peut être étendue aux entiers relatifs, voire aux nombres réels, par exemple pour la mesure des angles en radian : le quotient est toujours un  nombre entier relatif, mais le reste est un nombre réel. En mathématiques un choix très courant pour assurer l'unicité du reste est d'imposer qu'il soit toujours positif ou nul. Soient donc deux  nombres réels, x et d, d≠ 0, cette première définition donne :

Définition 1 (reste positif). le quotient q et le reste r sont les seuls nombres réels vérifiant :

x = q×d + r, q , 0 ≤ r < |d|.

Un autre choix possible est de supposer que le reste est toujours de même signe que le diviseur :

Définition 2. (reste de même signe que le diviseur). le quotient q et le reste r sont les seuls nombres réels vérifiant :

x = q×d + r, q , r est entre 0 et d (si d > 0, 0 ≤ r < d, si d < 0, d < r ≤ 0).

Ces deux définitions coïncident quand le diviseur d est positif, cas où se restreignent souvent les mathématiciens. Elles assurent toutes deux une propriété supplémentaire de l'existence et l'unicité nécessaire pour la définition : le reste est un représentant unique d'une classe modulo n, c'est-à-dire que, en continuant à appeler x mod d le reste de la division de x par d :

x - y est un multiple de d si et seulement si x mod d = y mod d.

En informatique la définition 2 est utilisée plus couramment que la définition 1, mais une troisième définition est aussi utilisée qui, elle, ne vérifie pas la dernière propriété, et qui est donc moins satisfaisante d'un point de vue mathématique :

Définition 3. (reste de même signe que le dividende). le quotient q et le reste r sont les seuls nombres réels vérifiant :

x = q × d + r, q , 0 ≤ |r| < |d| et r est du signe de x.

Quand x mod n est choisie en adoptant la définition 3, on peut donc avoir :

9 mod 4 = 1 (9 = 2×4 + 1), -7 mod 4 = -3 (-7 = -1×4 - 3), pourtant 9 -(-7)= 4×4, c'est-à-dire que 9 et -7 sont dans la même classe modulo 4.

Par contre les définitions 1 et 2 donnent bien

9 mod 4 = -7 mod 4 = 1 (-7=-2×4 + 1).

Le quotient

λ(m×n) = ppcm(λ(m), λ(n)) si m et n premiers entre eux.

Proposition. — la fonction λ est définie par

• λ(p^r) = p^r - p^{r - 1}, pour p premier impair et r > 0, ou p = 2 et 0 < r ≤ 2 ;
• λ(2^r) = 2^{r - 2}, pour r > 2 ;
• λ(p₁^r₁ ... p_k^r_k ) = ppcm(λ(p₁^r₁), ... , λ( p_k^r_k)).

1/2φ(2^r)).

1/2φ(2^r)). − 1/2 , − a/b , − a/b²

( a/a² + b², –b/a² + b² ),

→u = (2,3) --→AB u= ----A→B = (4,8)

azez

le vecteur →u = (2,3) et autre chose de suffisamment long pour tester le passage à la ligne et l'espacement entre celles-ci, allez encore un peu, un peu plus, ça ne suffit pas ça va finir par aller

ℬ = ( →i, →j, →k)

→u = —A→B = (4,7)

3 3

Triangle rectangle :

• Angelo S. Di Domenico, A Property of Triangles Involving Area, vol. 87, Mathematical Association, 509 2003, 323-324 p. (lire en ligne)

Marc Fumaroli, « Classicisme français et culture italienne : réflexions sur l’échec de Théodore », Mélanges à la mémoire de Franco Simone, France et Italie dans la culture européenne II, Genève, Slatkine, 1981, p. 205–238. Étude reprise dans Héros et orateurs, « Théodore, vierge et martyre : ses sources italiennes et les raisons de son échec à Paris », p. 223–259.