Arithmétique

Difficulté: 4.7/20 facile

Division euclidienne dans N

a,b ≠0 donnés il existe k,r unique tels que a = kb+r avec 0 ≤ r < b
On note a|b pour dire ka = b càd b divisé par a donne un reste nul.
a|b
¤ a divise b, a est un diviseur de b, ka = b
¤ b est un multiple de a, b est divisible par a

Définition un nombre premier (dans N)

p est un nombre premier s'il n'a que 2 diviseurs: { 1,p }
Rem: 1 n'est pas un nombre premier , car il a un seul diviseur, 2 et le seul nombre premier pair. ex: des nombres premiers : 2, 3, 5, 7, 11.....

Voici quelques resultats

Si n n'est pas premier alors il possède au moins un diviseur premier p

Le plus grand diviseur premier p de n vérifie p≤ √n

L'ensemble des nombres premiers est infini

Tout nombre non premier n se décompose en produit des nombres premiers de façon unique: n = p^aq^br^c... avec p,q,r premiers. par ex: n=2³3²7²

soit:p (premier) et p|ab ⇒ p|a ou p|b

soit:p (premier) et p|aⁿ ⇒ p|a

a|b et b|c ⇒ a|c

Le nombre de diviseurs de n: µ=(a+1)(b+1)(c+1)... par ex: µ=(3+1)(2+1)=12

Les diviseurs de n: div(n)=les termes de ce produit (1+p+p²...+p^a)(1+q+q²...+q^b)(1+r+r²...+r^c)... par ex:
(1+2+2²+2³)(1+3+3²)={ 1,2,4,8,3,6,12,24,9,18,36,72 }

La somme des diviseurs de n: s=(p^a+1)-1)/(a-1) . (q^b+1-1)/(b-1) . (r^c+1-1)/(c-1) par ex:n=2³3² ⇒ s=(2⁴-1)/(2-1) . (3³-1)/(3-1)

Le produit des diviseurs de n: w²=n^µ

On note (a,b) le pgcd de a,b = le plus grand commun diviseur de a,b. Si (a,b)=1 on dit que a et b sont premiers entre eux. et ppcm(a,b)= le plus petit commun multiple de a,b par ex:

a=2³3²
b=2²3⁴5³

(a,b)=2²3² (commun et petit puissance)
ppcm(a,b)=2³3⁴5³ (tout et plus grand puissance)

Théorème de Bezout ♥
(a,b)=1 ⇔ ∃ u,v ∈Z tq ua+vb = 1

Théorème de Gauss ♥
a|bc et (a,b)=1 ⇒ a|c

Encore quelques resultats

• (a,b)=1 et (a,c)=1 ⇒ (a,bc)=1
• (a,b)=1 ⇒ (a,bⁿ)=1 donc aussi (aⁿ,bⁿ)=1
• ab=cⁿ et (a,b)=1 ⇒ a,b de la forme a=uⁿ et b=vⁿ ♥ , ceci provient de l'unicité de la décomposition en facteurs premiers

Congruent modulo

On dit que a est congru à b modulo n s'ils ont le même reste. et on note
a = b (mod n)
Donc
a = 0 (mod n) ⇒ a = kn ⇒ n|a

Les propriétés:
a = b (mod n) et a' = b' (mod n) ⇒ a + a' = b + b' (mod n) on peut faire la somme
a = b (mod n) et a' = b' (mod n) ⇒ aa' = bb' (mod n) on peut les multiplier
ca = cb (mod n) n'implique pas a = b (mod n) , pas de simplification , c n'est pas forcement inversible. Si (c,n) = 1 alors on peut le simplifier
ab = 0 (mod n) n'implique pas a = 0 (mod n) ou b = 0 (mod n) Z/nZ n'est pas intégre (il contient des diviseurs de zéro par exp : 2.3 = 0 (mod 6) )

Théorème Fermat ♣
soit p premier , alors on a toujours
a^p = a (mod p)
p|(a^p - a )
a^p - a = kp

Théorème chinois ♣
x = a (mod u)
x = b (mod v)

si (u,v) = 1 (ru+sv = 1) alors on a au mois une solution x = rua+svb (mod uv)

Indicateur d'Euler Φ(n)

Φ(n) = le nombre d'entier, inférieur à n et premier avec n
Propriétés:

• p premier Φ(p) = p-1
• p premier Φ(p^k) = p^k(p-1) ,Φ(p) est pair si p ≠ 2
• (a,b)=1 Φ(ab) = Φ(a)Φ(b)
• Φ(n) = n Π_p(1 - 1/p) où produit sur les p dans la décomposition de n
• n = Π _d|n Φ(d) produit sur des diviseurs de n

[1] 2

Accueil

DMJ: 15/01/2025