Votre navigateur est obsolète et non sécurisé. Vous ne pouvez pas bénéficier de toutes les fonctionnalités de ce site. Pour une navigation optimale et sécurisée, merci de mettre à jour votre navigateur.
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=bq1+r1 avec `0<=r_1<|b|` et a=bq2+r2 avec `0<=r_2<|b|`

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

ainsi r1=r2 et on en déduit q1=q2

 

 

 

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 n0 donné

Si P(n0) est vraie  (initialisation)
et si, pour tout k`>=` n0 , 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 à n0

 

 

Exemple:

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

 

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

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

                    7(k+1)-1=7 `xx` 7k -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:

  1. a`-=` a (mod n)
  2. si a`-=` a' (mod n) alors a'`-=` a (mod n)
  3. si a`-=` b (mod n) et b`-=` c (mod n) alors a`-=` c (mod n)
  4. si a`-=` a' (mod n),  alors pour tout entier k, ka`-=` ka' (mod n)
  5. 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:

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

    ex1:
    Trouver le reste de la division euclidienne par 7 de 1998128
  2.  

  3.  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 p1 et n=p1xd1 avec 1<p1<n et 1<d1<n

                 Si d1 est premier c'est terminé: n=p1xd1

                 Si d1 non premier on réitère le processus: n= p1xp2xd2 avec p2 premier et 1<p2<d1, 1<d2<d1.... 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=bq1+r1, avec 0`lt=` r1`lt` b

Si r1`!=` 0, on divise b par r1:     b=r1q2+r2, avec 0`lt=` r2`lt` r1

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 rn est le dernier reste non nul obtenu, alors l'ensemble des diviseurs communs à a et à b est l'ensemble des diviseurs de rn

 

 

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 a1 et  a2 sont des diviseurs de b premiers entre eux alors a1a2 est aussi un diviseur de b
  • a est premier avec b `hArr` a est premier avec bn, 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: p1m et p2n 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)

This website was created with Yoctown for free.
You too, create a website and create awareness about your activity.