ENT arithmétique1 .pdf



Nom original: ENT-arithmétique1.pdf
Titre: BASES
Auteur: Friedelmeyer

Ce document au format PDF 1.5 a été généré par Acrobat PDFMaker 10.1 pour PowerPoint / Acrobat Distiller 10.1.3 (Windows), et a été envoyé sur fichier-pdf.fr le 17/10/2012 à 18:50, depuis l'adresse IP 81.56.x.x. La présente page de téléchargement du fichier a été vue 1057 fois.
Taille du document: 177 Ko (15 pages).
Confidentialité: fichier public


Aperçu du document


s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Ensembles de référence:



divisibilité
Démonstration



On parle d'arithmétique entière lorsque l'on
travaille dans l'ensemble IN des entiers
'naturels' ou Z des entiers relatifs

Soit d un diviseur d'un entier n
Par définition, il existe k tel que n=kd
Comme n,d>0, k>0 donc k≥1
Comme k≥1, kd≥d donc n≥d ou d≤n

Divisibilité dans IN



Définition:

Si n et d sont deux entiers, on dit que d est
un diviseur de n si il existe un entier k tel
que n=k x d.
On dit aussi que n est divisible par d ou que
n est un multiple de d
On note d| n(d divise n)

Divisibilité dans Z



On étend la définition aux entiers relatifs en
disant que si d|n, alors
d|(-n) ; (-d) | n ; (-d) | (-n)

Théorèmes (dans Z)



1) Si a | b et b| c alors a | c
2) Si a | b et a | c alors
pour tout m et n entiers
a | mb + nc

Propriétés:

Tout diviseur de n est compris entre 1 et n
Tout entier a donc un nombre fini de
diviseurs
Exemples
Comme 56 = 7 x 8 on peut dire que
7 est un diviseur de 56
8 est un diviseur de 56
56 est un multiple de 7, ou de 8
Comme 56 = 14 x 4 on a également
14 et 4 sont des diviseurs de 56
56 est un multiple de 4, de 14…

Preuves



a | b  il existe k tel que b = ka
b | c  il existe k' tel que c = k'b
donc c = k'(ka) = (k'k) a soit a | c
a | b  il existe k tel que b = ka
a | c  il existe k' tel que c = k'a
donc mb+nc = mka+nk'a = (mk+nk')a
soit a | mb+nc

1

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Division Euclidienne (dans IN ou Z)
On appelle division euclidienne la division
entière avec reste



Définition/Théorème

Quels que soient a et b entiers, il existe un
unique couple d'entiers naturels q et r tels
que a=bq+r, avec 0 ≤ r < |b|
q est le quotient de a par b
r est le reste de la division de a par b
On dit aussi que q est la partie entière de
a/b
Exemple
Division euclidienne de 17 par 8:

En 17 il y a 2 fois 8, 2x8=16, 17-16=1
donc
17=8x2+1
2 est le quotient de 17 par 8, 1 est le reste
Division euclidienne de -94 par 7:

En 94 il y a 13 fois 7, 13x7=91, 94-91=3
donc
94=7x13+3, -94=-7x13-3 ne marche pas
On rajoute et on enlève 7
-94 = -7x14-3+7=7x(-14)+4
-14 est le quotient de 94 par 7, +4 est le
reste

Division entière
Démonstration (a,b naturels)



Unicité

Supposons l'existence de deux solutions
(q,r) et (q',r'). Alors
a=bq+r=bq'+r' soit
b(q-q')=(r'-r)
r-r' est donc un multiple de b
Or 0 ≤ r < b et 0 ≤ r' < b
donc –b < r-r' < b
Le seul multiple de b vérifiant cette
condition est r-r'=0 soit r=r' et q=q'.
Existence

On considère tous les multiples de b (k x b)
inférieurs à a. Il y en a au moins 1 (0) et il
n'y en a pas une infinité car si
k.b ≤ a, k ≤ b/a
Donc il y en a un plus grand que les autres,
que j'appelle q.
Alors qb ≤ a < (q+1)b
En posant r = a-qb, on a bien
a = qb+r
qb ≤ a  a-qb ≥0 soit r ≥ 0
a < qb+b  a-qb < b soit r <b
2

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Déterminer q



Avec a et b, on calcule a/b
la partie entière du résultat est q
On peut aussi utiliser la fonction Partie Entière :
E(x) en notation mathématique
IPart(a/b) ou partEnt(a/b) sur TI (MATH/num)
Int(a/b) sur Casio (menu OPTN/num)
ENT(a/b) sur Excel
Attention, sur calculatrice, les négatifs
donnent de mauvaises valeurs

Déterminer r



Une fois que l'on a q, on a r=a-qb
MOD(a,b) sur Excel
exercices : n°19p26

Méthode



valeurs possibles de b

On sait que la division de 1399 par b a pour
reste 340. Quel est le diviseur b ?
1387 = bq+340
bq = 1399-340 = 1059
Les diviseurs de 1059 sont
1,1059,3,353
Or le reste doit être inférieur à b, donc b≥340
Il reste donc 1059 ou 353
Soit 1387=1059x1+340
ou 1387 = 353x3+340

A la calculatrice
Conséquences



dans une division euclidienne de a par b
r = 0 si et seulement si a divise b
Tout intervalle de la forme ]N-b;N] (N entier
quelconque) contient un et un seul multiple de
b
Preuve

Si l'on a deux diviseurs d et d', on a
bd = N+k (0≤k<b)
bd' = N+k' (0≤k<b). Supposons k≥k'
soit bd-bd' = b(d-d') = N+k-N-k' = k-k'
donc 0≤b(d-d')<b, soit d-d'=0, d=d', k=k'
Application importante

tout entier N s'écrit sous la forme
2n ou 2n+1
en effet, ]N-2;N]={N-1,N} contient un seul
multiple de 2, soit N-1=2n, soit N=2n
tout entier s'écrit sous la forme 3n, 3n+1
ou 3n+2
en effet, ]N-3;N]={N-2,N-1,N} contient un
seul multiple de 3, soit N-2=3n, soit N-1=3n,
soit N=3n.

3

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Factoriser



On sait que la division de n par 5 a pour reste
3. Montrer que 2n2-n est un multiple de 5

Méthodes classiques
un algorithme donnant tous les diviseurs
d'un nombre donné


Demander a
POUR compteur VARIANT de 1 A racine(a)
SI a/compteur = ENT(a/compteur)
ALORS
afficher compteur
afficher a/compteur
FIN SI
FIN POUR

Traduction

Il existe k tel que n=5k+3
Développement, factorisation

2n2-n=2(5k+3)2-(5k+3)
=50k2+60k+18-5k-3=50k2+55k+15
=5(10k2+11k+3) qui est bien multiple de 5

Tester les cas possibles



Quels sont les restes possibles de la division
par 6 de k2 ?
Les valeurs possibles de k peuvent s'écrire
6n, 6n+1,6n+2,6n+3,6n+4,6n+5

(6n)2=36n2=6(6n2), le reste est nul
(6n+1)2=36n2+12n+1=6(6n2+2n)+1,
le reste est 1
(6n+2)2=36n2+24n+4=6(6n2+4n)+4,
le reste est 4
(6n+3)2=36n2+36n+9=6(6n2+6n+1)+3,
le reste est 3
(6n+4)2=36n2+48n+16=6(6n2+8n+2)+4,
le reste est 4
(6n+5)2=36n2+60n+25=6(6n2+10n+4)+1,
le reste est 1
Les restes sont donc 0,1,3 ou 4

un algorithme donnant tous les multiples
d'un entier a, inférieurs à une borne M


Demander a, demander M
A) compteur 0
B) TANT QUE a * compteur < M
c) afficher a * compteur
d) compteur  compteur+1
FIN TANT QUE
Trace avec a=19, M=60

étape

compteur

affichage

A

0

B,C,D

1

19

B,C,D

2

38

B,C,D

3

57

4

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Définition
un nombre premier est un nombre entier
naturel, supérieur ou égal à 2, n’ayant que
deux diviseurs: 1 et lui même.



Nombres premiers
Algorithme



DEMANDER n>2
POUR d variant de 2 à n-1
SI d divise n
Afficher 'pas premier'
FIN du programme
FIN SI
Afficher n ’est premier'

Par exemple

101, 599, 32971, 999983
Définition
Un nombre qui n'est pas premier est
composé

Exemple



Le problème fondamental en arithmétique
est de savoir si un nombre N donné est
premier ou composé.
La définition très simple, donne un
algorithme également très simple, il suffit
de regarder pour tous les nombres allant de
2 à N-1, s'ils divisent ou non N.
Cet algorithme est malheureusement très
long puisqu'il demande N-2 tests et
opérations

5

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Algorithmes
Donc il a un diviseur premier : Pi
Or la division euclidienne de N par Pi donne 1
comme reste
Ce qui est absurde, donc N n'existe pas, cad
qu'il n'y a pas de limites aux nombres
premiers.

Propriétés



1) Soit n naturel; le plus petit diviseur de n
supérieur à 2 est premier
2) Tout entier naturel composé n admet un
diviseur premier inférieur ou égal à n
Par contraposée

2') Si n n'est divisible par aucun entier entre 2
et n, alors n est premier
3) Il existe une infinité de nombres premiers
(Euclide, IIIème av JC)

Amélioration 1 (p17 pour TI/Casio)



DEMANDER n>2
POUR d variant de 2 à n
SI d divise n
Afficher 'pas premier'
Afficher 'diviseur:',d
FIN du programme
FIN SI
Afficher n ’est premier'

Preuves



1) Soit p le plus petit diviseur de n tq 2≤p≤n
Si 2≤d<p divise p, alors d divise n et d est plus
petit que p. C'est absurde.
2) Soit n composé, il existe donc p et k tels
que n = p.k, donc p|n et k|n
Si p> n et k> n, alors p.k > n ce qui est
absurde car p.k=n. Donc p≤ n ou k≤ n.

Exemple



2') est la contraposée de 2
3) Si P1, P2, … , Pk sont les seuls nombres
premiers
Alors N=P1.P2.P3. … …Pk+1 est composé car il
est plus grand que tous les Pi

6

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

L'algorithme précédent fournit un diviseur d
d'un nombre composé n
Que se passe-t-il si on recommence avec
n/d ?
Exemple
On part avec n = 1519050  n
d = 2, on calcule n/2 = 759525  n
d = 3, on calcule n/3 = 253175  n
d = 5, on calcule n/5 = 50635  n
d = 5, on calcule n/5 = 10127  n
d = 13; on calcule n/13 = 779  n
d = 19, on calcule n/19 = 41  n
d=41, on calcule n/41 = 1  n
C'est finit

Conséquences
Algorithme (p18 pour casio, TI)



Demander n (>2)
Poser d=2
TANT QUE n>1
Si d divise n,
afficher d
remplacer n par n/d
Sinon
Augmenter d de 1
Fin SI
FIN TANT-QUE

On obtient au final :
n = 2x3x5x5x13x19x41
Quel algorithme a-t-on suivi ?

7

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Décomposition en facteurs premiers



Décomposition en premiers
Traduction mathématique



théorème fondamental de l'arithmétique :

Il existe une unique façon d'écrire n sous la
forme

Tout entier naturel strictement supérieur à
1 est premier OU peut être écrit comme
un produit de nombres premiers d'une
unique façon, à l'ordre près des facteurs.
L'algorithme vu précédemment est donc justifié et
donne une méthode de recherche de cette
décomposition







n  p1 1  p2 2  p3 3 ... pk

k

Les pi étant premiers, croissants, et les i
supérieurs à 1.

Conséquence



Le nombre d divise n si et seulement si les
exposants de pi dans la décomposition de n
sont supérieurs ou égaux à ceux de d.

Preuve



Par récurrence :
C'est vrai pour n=2, qui est premier
Supposons que c'est vrai pour tous les entiers
inférieurs à k-1, et montrons le pour k:
Si k est premier, c'est bon
Si k n'est pas premier :
il a un diviseur premier p < k
k=p x d, et d < k donc d ≤k-1
Donc d est premier ou s'écrit comme
produit de nombres premiers (hypothèse de
récurrence) : d=d1xd2x…xdm

Exemple



On a vu 1519050 = 2x3x52x13x19x41
Les diviseurs de 1519050 sont donc
2a1x3a2x5a3x13a4x19a5x41a6
avec a1, a2, a4, a5, a6 ≤ 1
et a3≤2
On peut en déduire qu'il y en a exactement

2 x 2 x 3 x 2 x 2 x 2 = 96

Donc k = pxd1xd2x…xdm
8

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Définition



Congruences
Exemples



Soit p > 1 un entier. On dit que l'entier a est
congru modulo p à l'entier b si a - b est un
multiple de p

Notation



Déterminer les affirmations exactes dans la
liste suivante :
17 Ξ 42 (5)

17Ξ-18(5)

175 Ξ 2 (7)

15 Ξ 3 (7)

544Ξ4 (10)

151 Ξ 1 (2)

2464Ξ1(2)

25Ξ43(17)

100Ξ1 (11)

1000Ξ10(11)

1000Ξ-1(11)

7852Ξ1 (4)

On note alors a Ξ b (p)

Exemple



17 Ξ 8 (3),
23 Ξ 2 (3),
23 Ξ -1 (3).

Remarque



a est un multiple de b ssi a Ξ 0 (b)

Définition 2



Quels sont les nombres congrus à 5 modulo 17



On a a Ξ b (p) ssi a et b ont le même reste r
dans la division euclidienne par p, en ce cas a
et b sont tous deux congrus à r modulo p.

Propriétés
La relation de congruence modulo p est
compatible avec les opérations algébriques
usuelles :


Si a Ξ b (m) et c Ξ d (m), alors
a + c Ξ b + d (m)
ac Ξ bd (m)
ak Ξ bk (m) (pour k entier quelconque)
n.a Ξ n.b (m) (pour n entier quelconque)
9

Chapitre I – arithmétique entière
Propriétés (suite)



méthodes


Méthodes

Si a Ξ b (m) et b Ξ c (m) alors a Ξ c (m)

Résoudre 2x+3 Ξ 5 (6)
2x+3 Ξ 5 (6)
<=> 2x Ξ 2 (6)
Sachant que x (6) prend les valeurs

on dit que la relation de congruence est
transitive


Preuves des propriétés

Si a Ξ b (m) et c Ξ d (m), alors
a-b est un multiple de m, ainsi que d-c
donc a-b=km et d-c=k'm
Alors
(a+d)-(b+c)=(k-k')m donc a+d Ξ b+c (m)

x

0

1

2

3

4

5

2x

0

2

4

0

2

4

les solutions sont x=1+6k, x=4+6k
Détermination du reste de 17n dans la
division euclidienne par 5.
17 Ξ 2 (5)
donc 17n Ξ 2n (5)
On constate :

ad – bc = (km+b)(k'm+c)-bc
= kk'm2+ckm+bk'm=m(kk'm+ck+bk')
donc ad-bc est un multiple de m soit
ad Ξ bc (m)
a0 Ξ b0, a1 Ξ b1 donc c'est vrai pour k=1
Si c'est vrai pour k, soit ak Ξ bk, alors, comme
a Ξ b, ak+1 Ξ bk+1, donc c'est vrai à l'ordre k+1
D'après le principe de récurrence, c'est vrai
pour tout k

Suite

Si a Ξ b (m) et b Ξ c (m), alors a-b=km et

b-c=k'm, donc
a-c=a-b-(c-b)=km-k'm=(k-k')m soit a Ξ c (m)

n

0

1

2

3

4

5

n (4)

0

1

2

3

0

1

2n

1

2

4

8

16

32

2n (5)

1

2

4

3

1

2

Soit, si n Ξ 0 (4), 2n Ξ 1 (5)
si n Ξ 1 (4), 2n Ξ 2 (5)
si n Ξ 2 (4), 2n Ξ 4 (5)
si n Ξ 3 (4), 2n Ξ 3 (5)

Chapitre I – arithmétique entière
preuve : par disjonction

si n Ξ 0 (4), n=4k,
donc 2n=24k=(24)k =16k Ξ1k (5)
donc 17n Ξ 1 (5)
si n Ξ 1 (4) n=4k+1,
donc 2n=24k+1=2x(24)k =2x16k Ξ2x1k (5)
donc 17n Ξ 2 (5)
si n Ξ 2 (4) n=4k+2,
donc 2n=24k+2=22x(24)k =4x16k Ξ4x1k (5)
donc 17n Ξ 4 (5)
si n Ξ 2 (4) n=4k+3,
donc 2n=24k+3=23x(24)k =8x16k Ξ3x1k (5)
donc 17n Ξ 3 (5)


Application : critères de divisibilité
Rappel
Si n est un entier, n s'écrit de façon unique
sous la forme a0x1+a1x10+a2x100+..+anx10n
= a0x100+a1x101+a2x102+..+anx10n
On note n = anan-1…a2a1a0
et on utilise
i n

n   ai 10
i 0

i

critères de divisibilité
Alors :
Si a0 Ξ 0 (2) <=> n Ξ 0 (2)

ie : n est divisible par 2 si et seulement
est pair
Si a0 Ξ 0 (5) <=> n Ξ 0 (5)
ie : n est divisible par 5 si et seulement
l'est aussi
Si a0+a1+…+an Ξ 0 (3) <=> n Ξ 0 (3)
ie : n est divisible par 3 si et seulement
somme des ai est un multiple de 3
Si a0+a1+…+an Ξ 0 (9) <=> n Ξ 0 (9)
ie : n est divisible par 9 si et seulement
somme des ai est un multiple de 9

si a0

si a0

si la

si la

Preuves
On utilise les congruences de 10 :
10 Ξ 0 (2) donc
i n

in

n   ai  10  a0  10 ai 10i 1  a0 (2)
i

i 0
de même
pour 5
10 Ξ 1 (3) donc
i n

i 1

i n

n   ai  10   ai  1i  a0  a1  ...an (3)
i

i 0

i 0

de même 10 Ξ 1 (9)
i n

i n

n   ai  10   ai  1i  a0  a1  ...an (9)
i

i 0

i 0

Chapitre I – arithmétique entière

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Plus grand commun diviseur (PGCD)



Si a et b sont deux entiers relatifs, on appelle
PGCD de a et b, noté PGCD(a; b) ou a ^ b, le
plus grand des diviseurs communs à a et b
On convient de plus que PGCD(a; b)=0 si
a=b=0.

Plus petit multiple commun (PPCM)

PGCD et PPCM
Exemples



558 = 2x3x3x31 = 2x3231
648 = 2x2x2x3x3x3 = 23x33
10164 = 2x2x3x7x11x11 = 22x3x7x112

PGCD de 24 et 36 :



Les diviseurs de 24 sont
1;2;3;4;6;8;12;24
Les diviseurs de 36 sont
1;2;3;4;6;9;12;18;36
Le plus grand diviseur commun est 12
On a donc 24 ^ 36 = PGCD(24;36)=12



Si a et b sont deux entiers relatifs, on appelle
PPCM de a et b, noté PPCM(a; b) ou a V b, le
plus petit des multiples strictement positifs de
a et b
On convient de plus que PPCM(a; b)=0 si a=0
ou b=0.

Nombre premiers entre eux

PPCM de 24 et 36





Les multiples de 24 sont
0;24;48;72;96…
Ceux de 36 sont
0;36;72;108;144…
le plus petit non nul est 72
On a donc 24 V 36 = 72
Remarque : on constate, et cela sera toujours vrai
que 24 x 36 = 864 et que 12 x 72 = 864

On dit que a et b sont premiers entre eux ssi
PGCD(a; b) = 1, c'est-à-dire lorsque leurs
seuls diviseurs communs sont 1 et -1.

Théorème



Quels que soient a et b positifs, on a :
PGCD(a,b) x PPCM (a,b) = axb
On en déduit que PPCM(a,b)=ab/PGCD(a,b)
13

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Algorithme d'Euclide



On dispose depuis plus de 2000 ans d'un
algorithme efficace pour le calcul du pgcd.
Celui-ci repose sur la remarque suivante :
Soient a et b deux nombres positifs
Si dans une division Euclidienne on a
a = bq+r (avec r<b donc !) alors
PGCD(a,b) = PGCD(b,r)
Comme r<b, on se ramène donc à un couple
(b,r) d'entiers plus petit et on recommence
jusqu'à ce que le reste soit nul. Le pgcd est
alors LE DERNIER RESTE NON NUL

Exemple : PGCD de 143 et 77

Algorithme d'Euclide
Mise en place de l'algorithme



a

b

r

q

5283

4095

1188

1

4095

1188

531

3

1188

531

126

2

531

126

27

4

126

27

18

4

27

18

9

1

18

9

0

2



143 = 77x1+66
77 = 66x1 + 11
66 = 6x11 + 0
le PGCD de 143 et 77 et donc 11

Exemple : PGCD de 120 et 23



120 = 5x23+5
23 = 4x5+3
5=1x3+2
3=1x2+1
2=2x1+0
Le PGCD de 120 et 23 est donc 1
Ces nombres sont premiers entre eux

On a donc l'algorithme suivant :

//En entrée deux nombres a et b
//En sortie le PGCD de a et b
//Variable auxiliaire : r:reste de a par b
Demander a et b
TANT QUE b ≠ 0
ra%b
ab
br
FIN TANT QUE
pgcd  a
14

s.friedelmeyer@ac-toulouse.fr , le 17/10/2012

Chapitre I – arithmétique entière

Traduction en Javascool



int PGCD(int a,int b) {
//Cette fonction prend en entrée deux
entiers a et b entiers
//Et renvoie leur PGCD
//var auxiliaire : r reste de a par b
//Si a ou b sont nuls, on renvoie 0
if(a==0 && b==0) return 0;
int r;
while(b!=0) {
r=a%b;
a=b;
b=r;
}
return a;
}

Algorithme pour le PPCM
L'algorithme pour le PPCM utilise
simplement le fait que
PPCM(a,b)=ab/PGCD(a,b) si a et b non
nuls. On a donc, en Javascool



int PPCM (int a,int b) {
//Cette fonction prend en entrée deux
entiers a et b entiers
//Et renvoie leur PPPCM
//Si a ou b sont nuls, on renvoie 0
if(a==0 || b==0) return 0;
return a*b/PGCD(a,b);
}

Applications
Quelques applications algorithmiques



Opérations sur les fractions

Pour simplifier une fraction a/b, il faut diviser a
et b par leur PGCD :
Le pgcd de 1255 et 520 est
donc
Pour additionner deux fractions a/b et c/d, le
dénominateur commun est le PPCM de b et d
de même pour les soustraire
Le PGCD de 55 et 175 est
Le PPCM de 55 et 175 est
Donc

On peut donc envisager les fonctions
nécessaires pour implémenter une calculatrice
fonctionnant avec les fractions (voir TP n°8)
Simplification des radicaux

La décomposition en facteur premiers d'un
nombre entier permet de simplifier facilement
son écriture radicale (racine carrée):
Comme 200 = 23x52=2x22x52, on a
200 = 2x 22x 52=2x5x 2=10 2.
L'algorithme consiste donc en la recherche des
facteurs à la puissance 2 ou plus.

15




Télécharger le fichier (PDF)

ENT-arithmétique1.pdf (PDF, 177 Ko)

Télécharger
Formats alternatifs: ZIP







Documents similaires


ent arithmetique1
60
cours arithmetique dans n copie
cours arithmetique specialite maths terminale 14
ent pgcd
arithmetique 3eme 1