L'arithmétique est l'étude des entiers , on travaille dans N ou Z, bien que N soit assez simple mais ses propriétées, et les problèmes que posent par les entiers sont souvent
très difficiles à résoudre...
C'est le paradis des mathématiques ....
L' Arithmétique dans Z
Division euclidienne dans N
a,b ≠0 donnés il existe k,r unique tels que a=kb+r avec 0 ≤ r < bOn 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 = paqbrc... avec p,q,r premiers. par ex: n=2332
- soit:p (premier) et p|ab ⇒ p|a ou p|b
- soit:p (premier) et p|an ⇒ 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+p2...+pa)(1+q+q2...+qb)(1+r+r2...+rc)...
par ex:
(1+2+22+23)(1+3+32)={ 1,2,4,8,3,6,12,24,9,18,36,72 } - La somme des diviseurs de n: s=(pa+1)-1)/(a-1) . (qb+1-1)/(b-1) . (rc+1-1)/(c-1) par ex:n=2332 ⇒ s=(24-1)/(2-1) . (33-1)/(3-1)
- Le produit des diviseurs de n: w²=nµ
On note (a,b)=pgcd(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 [a,b]=ppcm(a,b)= le plus petit commun multiple de a,b par ex:
a=2332
b=223453
(a,b)=2232 (commun et petit puissance)
[a,b]=ppcm(a,b)=233453 (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
- pgcd(a,b).ppcm(a,b)=(a,b)[a,b]=ab
- (a,b)=1 et (a,c)=1 ⇒ (a,bc)=1
- (a,b)=1 ⇒ (a,bn)=1 donc aussi (an,bn)=1
- ab=cn et (a,b)=1 ⇒ a,b de la forme a=un et b=vn ♥ , 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 notea ≡ b (mod n) ou a = b [n] ou 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
ap = a (mod p)
p|(ap - a )
ap - a = kp
Théorème chinois ♣
x = a (mod u)
x = b (mod v)
si (u,v)=1 c'est-à-dire (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 nPropriétés:
- p premier Φ(p)=p-1
- p premier Φ(pk)=pk(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