Scribd
Importer
5 vues1 page

Concepts clés de l'arithmétique

Le document traite des concepts fondamentaux de l'arithmétique, incluant la division euclidienne, la divisibilité, et les congruences. Il aborde également les nombres premiers, le PGCD et le PPCM, ainsi que des théorèmes importants comme celui de Bézout et de Gauss. Ces notions sont essentielles pour comprendre les propriétés des entiers et leurs relations.

Transféré par

Sitta Kiemtoré
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
5 vues1 page

Concepts clés de l'arithmétique

Le document traite des concepts fondamentaux de l'arithmétique, incluant la division euclidienne, la divisibilité, et les congruences. Il aborde également les nombres premiers, le PGCD et le PPCM, ainsi que des théorèmes importants comme celui de Bézout et de Gauss. Ces notions sont essentielles pour comprendre les propriétés des entiers et leurs relations.

Transféré par

Sitta Kiemtoré
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Arithmétique

Latex Templates pro

Division euclidienne
Soit a ∈ Z et b ∈ N∗ , il existe un unique couple (q, r) tel que a = bq + r avec 0 ≤ r < b
Vocabulaire : a est le dividende ; b le diviseur ; q le quotient et r le reste

Divisibilité dans Z Congruence dans Z


a divise b a et b ont même reste dans la division euclidienne par n
⇐⇒ b multiple de a ⇐⇒ a est congru à b modulo n
⇐⇒ il existe k ∈ Z tel que b = ka ⇐⇒ a − b est multiple de n
✧ Notation : a ≡ b (n)
✧ Notation : a/b ✧ Réflexivité : a ≡ a (n)
✧ Réflexivité : a/a ✧ Symétrie : a ≡ b (n) =⇒ b ≡ a (n)
( (
a/b a ≡ b (n)
✧ Transitivité : =⇒ a/c ✧ Transitivité : =⇒ a ≡ c (n)
b/c b ≡ c (n)
( (
a/b a ≡ b (n)
✧ Linéarité : =⇒ a/bu + cv ✧ Addition : =⇒ a + a′ ≡ b + b′ (n)
a/c a′ ≡ b′ (n)
✧ Lien avec les congruences : a/b ⇐⇒ b ≡ 0(a)
(
a ≡ b (n)
✧ Lien avec le PGCD : a/b ⇐⇒ P GCD(a, b) = a ✧ Multiplication : =⇒ aa′ ≡ bb′ (n)
a′ ≡ b′ (n)
✧ Puissance : a ≡ b (n) =⇒ ak ≡ bk (n)

Nombres premiers
Un entier p supérieur ou égal à 2 est premier si et seulement si il admet exactement deux diviseurs : 1 et lui-même
Théorème fondamental de l’arithmétique : tout entier naturel supérieur ou égal à 2 se décompose de manière unique à
l’ordre des facteurs près en produit de facteurs premiers : on note p = pα1 α2 αn
1 p2 . . . pn
√
Critère d’arrêt : si n n’admet pas de diviseur premier p tel que 2 ≤ p ≤ n alors n est premier

PGCD, PPCM
L’ensemble des diviseurs communs à a et b admet un plus grand élément noté PGCD(a, b)
L’ensemble
 des multiples communs  à a et b admet un plus petit élément noté PPCM(a, b)
α α
 a = p p ...p n
1 2 α  PGCD(a, b) = pm1 pm2 . . . pmn
1 2 n 1 2 n
✧ Si alors où mi = min(αi , βi ) et Mi = max(αi , βi )
 b = pβ1 pβ2 . . . pβn  PPCM(a, b) = pM1 pM2 . . . pMn
1 2 n 1 2 n

✧ PGCD(ka, kb) = kPGCD(a, b)


✧ Si a = bq + r, alors PGCD(a, b) = PGCD(b, r)
✧ Le PGCD de deux nombres non nuls est le dernier reste non nul de la suite des divisions de l’algorithme d’Euclide

Théorème de Bézout Théorème de Gauss


✧ PGCD(a, b) = 1
(
a/bc
⇐⇒ a et b sont premiers entre eux =⇒ a/c
PGCD(a, b) = 1
⇐⇒ il existe deux entiers u et v tels que au + bv = 1 Corollaires :
(
✧ Identité de Bézout : PGCD(a, b) = d a/c et b/c
✧ =⇒ ab/c
=⇒ il existe deux entiers u et v tels que au + bv = d PGCD(a, b) = 1
✧ Corollaire de Bézout : l’équation ax+by = c admet des
(
p premier
solutions entiers ⇐⇒ c est multiple de PGCD(a, b) ✧ =⇒ p/a ou p/b
p/ab

Vous aimerez peut-être aussi