sleca

Le site

SPE-Arithmétique

Divisibilité dans `ZZ`

b et a sont deux entiers
b divise a si, et seulement si, il existe un entier k tel que a=b
on dit alors: b est un diviseur de a
a est un multiple de b

Propriétés:

1, -1 ,a, -a sont des diviseurs de a
si a divise b et b divise a, alors a=b ou a=-b
si d divise a et b, alors d divise a+b, a-b, ka+k'b où ket k' sont des entiers
si b divise a, alors tout diviseur de b est un diviseur de a et tout multiple de a est un multiple de b

Division euclidienne dans `ZZ`

soit a un entier et b un entier non nul;
alors il existe un entier q unique et un entier naturel r unique tels que:

a=bq+r, avec `0<= r< |b|`

q est le quotient et r est le reste de la division euclidienne de a par b.

démonstration de l'unicité:

par l'absurde si a=bq₁+r₁ avec `0<=r_1<|b|` et a=bq₂+r₂ avec `0<=r_2<|b|`

alors on a: `{(-|b|<=r_1-r_2<|b|),(r_1-r_2=b(q_2-q_1)):}`
donc r₁-r₂=0 car 0 est le seul multiple de b strictement compris entre -|b| et |b|

ainsi r₁=r₂ et on en déduit q₁=q₂

Raisonnement par récurrence

Théorème:

Soit P(n) une proposition dépendant d'un entier naturel n supérieur ou égal à un entier naturel n₀ donné

Si P(n₀) est vraie (initialisation)
et si, pour tout k`>=` n₀ , P(k) vraie `rArr` P(k+1) vraie (hérédité)

alors la proposition est vraie pour tout entier naturel n supérieur ou égal à n₀

Exemple:

Démontrer que pour tout entier naturel n, 7ⁿ-1 est multiple de 6

solution:
1) initialisation: c'est vrai pour n=0: 7⁰-1=0
2) hérédité: on suppose 7^k-1 multiple de 6 donc 7^k=6q+1 pour q entier (H)

on doit montrer 7^(k+1)-1 multiple de 6

7^(k+1)-1=7 `xx` 7^k -1= 7(6q+1)-1= 7`xx` 6q +6= 6(7q+1) et 7q+1 est un entier donc 7^(k+1)-1 est un multiple de 6
3) Conclusion: la propriété est vraie pour n=0 et est héréditaire donc elle est vraie pour tout entier naturel n

Congruences dans `ZZ`

Définition:

Soit n un entier naturel supérieur ou égal à 2.

Deux entiers a et a' sont dits congrus modulo n
ssi a et a' ont même reste dans la division euclidienne par n.
ssi a-a' est un multiple de n

Notation: a `-=` a' (mod n)

Propriétés:

a`-=` a (mod n)
si a`-=` a' (mod n) alors a'`-=` a (mod n)
si a`-=` b (mod n) et b`-=` c (mod n) alors a`-=` c (mod n)
si a`-=` a' (mod n), alors pour tout entier k, ka`-=` ka' (mod n)
si a `-=` a' (mod n) et b `-=` b' (mod n) alors:
               a+b`-=` a'+b' (mod n)
               aa'`-=` bb' (mod n)
               ka+k'b`-=` ka'+k'b' (mod n) pour tous les entiers k et k'

Applications:

Restes dans la division par n des puissances d'un entier

ex1:
Trouver le reste de la division euclidienne par 7 de 1998¹²⁸

Règles de divisibilité

Nombres premiers

On travaillera uniquement ici avec des entiers naturels

un entier naturel p est dit premier ssi il possède exactement deux diviseurs dans `NN`

Tout entier naturel n non premier et différent de 1 admet au moins un diviseur premier
Conséquence: le plus petit diviseur de n strictement supérieur à 1 est premier

Reconnaitre un nombre premier:
- soit n>1; n est premier ssi il n'admet aucun diviseur premier inférieur ou égal à `sqrt(n)`
- utilisation du crible d'Eratosthène

Théorème:
L'ensemble des nombres premiers est infini

Démonstration: par l'absurde
           On suppose qu'il existe un nombre fini d'entiers premiers
           Soit p le plus grand d'entre eux
           On pose N=p!+1
           pour tout n`<=` p on a N`-=` 1 (mod n) donc N n'est divisible par aucun entier inférieur ou égal à p
           Si N est premier on a une contradiction car N>p
           Si N n'est pas premier alors il admet un diviseur premier inférieur ou égal à p ce qui est exclu

On en déduit que l'hypothèse est fausse et donc qu'il y a une infinité de nombres premiers

Décomposition en produit de facteurs premiers

Tout entier naturel n , n>1, se décompose en un produit de facteurs premiers et cette décomposition est unique à l'ordre des facteurs près.

Démonstration de l'existence: (on admettra l'unicité)

soit n`>=` 2
Si n est premier sa décomposition est n=n...
Si n non premier il admet au moins un diviseur premier p₁ et n=p₁xd₁ avec 1<p₁<n et 1<d₁<n

Si d₁ est premier c'est terminé: n=p₁xd₁

Si d₁ non premier on réitère le processus: n= p₁xp₂xd₂ avec p₂ premier et 1<p₂<d_1,1<d₂<d₁.... on continue ainsi jusqu'à ce que le dernier quotient obtenu soit 1

Les nombres premiers obtenus ne sont pas nécessairement distincts, on peut donc regrouper ceux qui sont égaux et on obtient une expression de la forme:
`n= p_(1)^(alpha_(1))p_2^(alpha_(2))...p_k^(alpha_(k))`

le nombre de diviseurs de n est alors `(alpha_1+1)(alpha_2+1)...(alpha_k+1)`

Ex2:

Algorithme d'Euclide

Soit a et b deux entiers naturels tels que a>b

On divise a par b: a=bq₁+r₁, avec 0`lt=` r₁`lt` b

Si r₁`!=` 0, on divise b par r₁: b=r₁q₂+r₂, avec 0`lt=` r₂`lt` r₁

Si r2`!=` 0, on divise r1 par r2: r1=r2q3+r3, avec 0`lt=` r3`lt` r2

on poursuit le processus jusqu'à l'obtention d'un reste nul.

Si r_n est le dernier reste non nul obtenu, alors l'ensemble des diviseurs communs à a et à b est l'ensemble des diviseurs de r_n

PGCD de deux entiers

Le PGCD de deux entiers naturels non nuls a et b est l'unique entier naturel `delta` tel que:

1) `delta` divise a et `delta` divise b

2) pour tout entier naturel non nul d, si d divise a et b alors d`lt=delta`

Remarques: si b est un diviseur de a alors PGCD(a,b)=b

si b n'est pas un diviseur de a, alors PGCD(a,b)=rn, dernier reste non nul de
l'algorithme d'Euclide appliqué à a et b

                  pour calculer le PGCD de a et b on peut effectuer le produit des facteurs premiers
                communs à a et à b, chacun étant affecté du plus petit exposant avec lequel il
                figure dans ces décompositions

Propriétés: a, b, k étant des entiers naturels non nuls:

l'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de PGCD(a,b)
PGCD(ka, kb)=k PGCD(a,b)
si k divise a et k divise b PGCD(`a/k` ,` b/k` )=`1/k` PGCD(a,b)
il existe de entiers relatifs u et v tels que au+bv=PGCD(a,b)

Nombres premiers entre eux

Deux entiers naturels a et b sont premiers entre eux si et seulement si PGCD(a,b)=1

Propriétés: a, b `delta` étant des entiers naturels non nuls:

PGCD(a,b) =`delta` `hArr` ` a/delta` et `b/delta` sont premiers entre eux
théorème de Bezout:

a et b sont premiers entre eux `hArr` il existe des entiers relatifs u et v tels que au+bv=1

Théorème de Gauss

a,b,c étant trois entiers naturels non nuls,
si a divise le produit bc et si a est premier avec b, alors a divise c

Propriétés:

si a₁ et a₂ sont des diviseurs de b premiers entre eux alors a₁a₂ est aussi un diviseur de b
a est premier avec b `hArr` a est premier avec bⁿ, où n est un entier naturel non nul
si p1 et p2 sont des nombres premiers distincts, alors pour tous entiers naturels m et n non nuls on a: p₁^m et p₂ⁿ sont premiers entre eux.

PPCM de deux entiers

Le PPCM de deux entiers naturels non nuls a et b est le plus petit multiple srictement positif m commun à a et b

L'ensemble des multiples communs à a et b est l'ensemble des multiples de m=PPCM(a;b)

Démonstration:

Il est immédiat que tout multiple de m est un multiple commun à a et b...

Supposons M multiple commun à a et b

La division euclidienne de M par m donne M=mq+r avec `0lt=rltm`

donc r=M-mq et on a: a|r et b|r

donc r est un multiple commun à a et b qui est strictement inférieur à m; on en déduit r=0

donc M=mq et M est un multiple de m

PPCM(a; b)xPGCD(a; b)=ab

Démonstration:

PPCM(ka ;kb)=k PPCM(a;b)