[PDF] 1 Divisibilité, nombres premiers, division euclidienne et congruences PDF 9782729877835

contrôles corrigés 5 1 Divisibilité, nombres premiers, division euclidienne et congruences résumés de cours exercices 1 Divisibilité, nombres premiers

Corrigés en vidéo avec le cours sur jaicompris com Apprendre `a A l'aide des congruences, quel est le dernier chiffre dans l'écriture décimale de 32015 ? Déterminer un On admet le crit`ere de divisibilité par 7 suivant : Pour savoir si un

[PDF] Divisibilité et congruences - PanaMaths

Les exercices du livre corrigés dans ce document sont les suivants : Page 445 : N°1, 5 Divisibilité et congruence Corrigés d'exercices / Version d'août 2012

[PDF] Exercices sur les congruences Exercice 1 Déterminer les

Exercice 2 Compléter la table de congruence suivante modulo 5 N 0 Corrigé Exercice 1 1) 2) 3) Exercice 2 N 0 1 2 3 4 2N² 0 2 3 3 2 Le suivant : N

[PDF] Divisibilité et congruences (f)

Licence FONDNATEXP, UE Maths 305 CORRIGÉ Divisibilité et congruences (f) Exercice f 1 (1) On a x3 +1= x3 − (−1)3 = (x + 1)(x2 − x + 1) donc x + 1 divise

[PDF] Corrigé, terminale S, spé-maths - Plus De Bonnes Notes

27 nov 2017 · 17 Corrigé, terminale S, spé-maths Divisibilité, division euclidienne, congruence ENONCE CORRECTION REDIGEE DETAILLEE Exercice 1

[PDF] 1 Divisibilité, nombres premiers, division euclidienne et congruences

contrôles corrigés 5 1 Divisibilité, nombres premiers, division euclidienne et congruences résumés de cours exercices 1 Divisibilité, nombres premiers

[PDF] DIVISIBILITÉ ET CONGRUENCES - maths et tiques

Définition : Soit a et b deux entiers relatifs a divise b s'il existe un entier relatif k tel que b = ka On dit également : - a est un diviseur de b, - b est divisible par a,

[PDF] Corrigé des exercices dentrainement congruences

Terminale 05-06 Spécialité Corrigé des exercices d'entrainement congruences On dresse un tableau des restes dans la congruence modulo 6 : n 0 1 2 3 4 5

[PDF] (Congruences )

Arithmétique : Corrigé Feuille 4 (Congruences ) Exercice 1 Calculons le reste de 78 divisé par 6 i e on cherche 0 ≤ x < 6 tel que 78 ≡ x [6] Modulo 6, on a :

[PDF] Mathématiques pour - Dunod

1 2 Divisibilité des entiers 8 1 3 Nombres premiers 8 1 4 Congruences 11 TD – Le codage affine 13 Exercices corrigés 16 Chapitre 2 • Suites numériques

51. Divisibilité, nombres premiers, division euclidienne et congruencesrésumés de cours

exercices

1Divisibilité, nombres

premiers, division euclidienne et congruences

DIVISIBILITÉ DANS Z

Définition

Soient a et b deux entiers relatifs. On dit que a divise b (ou que a est un diviseur de b, ou que b est un multiple de a) lorsqu'il existe un entier k tel que bka= (a divise b se note alors a/b).

Exemples

15 divise 45 puisque :

45 3 15=×.

48 est un multiple de 12 puisque :

48 4 12=×.

Propriétés

1. a/b a/b a/ b a/ b .

2. Tout diviseur positif a de b (avec

b0) vérifie : 1ab.

3. Tout entier positif (non nul) a un nombre fini de diviseurs.

Exemple

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 sont les diviseurs positifs de 60 (il en

possède douze).

Propriétés

Si a/b et b/c alors a/c.

Si a/b et a/c alors a/ bu cv+ pour tous entiers u et v (et en parti- culier : a/b c+ et a/b c).

Exemples

15 divise 30 et 30 divise 120 donc 15 divise 120.

12 divise 24 et 12 divise 60 donc 12 divise 228 (puisque

228 2 24 3 60=×+×

NOMBRES PREMIERS

Définition

Soit p un entier strictement positif. On dit que p est premier lorsqu'il ne possède que deux diviseurs : 1 et lui-même (c'est-à-dire p).

Exemples

2, 3, 5, 7, 11, 13, 19, 23, 29 sont tous des nombres premiers (2 est le seul

nombre premier pair). Attention : l'entier 1 n'est pas un nombre premier !

61. Divisibilité, nombres premiers, division euclidienne et congruences

Définition

Un nombre strictement positif, différent de 1, qui n'est pas premier est dit composé.

Théorème fondamental de l'Arithmétique

Tout nombre entier supérieur strictement à 1 admet au moins un diviseur premier.

Propriétés

1. Tout nombre composé n admet un diviseur premier inférieur ou égal à

2. Si aucun des entiers compris entre 2 et

n ne divise n, alors n est premier.

L'algorithme qui teste si un nombre est premier

L'algorithme ci-dessous permet de tester si un entier est premier. Il utilise la propriété précédente (propriété 2.).

Propriété

Il y a une infinité de nombres premiers (Euclide (325-265 av. J.-C.)). Théorème de décomposition en facteurs premiers Tout entier n strictement supérieur à 2 se décompose de manière unique (à l'ordre près) en produit de facteurs premiers, c'est-à-dire que pour tout contrôlescorrigés

71. Divisibilité, nombres premiers, division euclidienne et congruences

résumés de cours exercices résumés de cours exercices n, il existe des nombres premiers 1 p, 2 p, ... r p et des entiers non nuls 1 k, 2 k, ... r k tels que

12 rkk k12 r

n p p ...p=.

Exemples

1. On a :

360 2 3 5=××.

2. On a :

45 2

952560 2 3 5 7=×××.

Remarques

1. Pour trouver la décomposition en facteurs premiers d'un entier, on

divise autant de fois qu'il est possible par 2, puis par 3, 5, 7, etc.

2. L'instruction ifactor() (sous Xcas) permet d'obtenir la décomposition

en facteurs premiers d'un entier.

Propriété

a divise b si et seulement si les facteurs premiers intervenant dans la décomposition de a interviennent dans la décomposition de b avec un exposant inférieur. Ainsi tous les diviseurs de l'entier

12 rkk k12 r

n p p ...p= sont de la forme 12 r 12 r n p p ...p avec 11 0k , 22
0k , rr 0k .

Exemples

1. 2

60 2 3 5=×× divise

323

9000 2 3 5=××.

2. 22

252 2 3 7=×× divise

45 2

952560 2 3 5 7=×××.

Propriété

Le nombre de diviseurs positifs de l'entier

12 rkk k12 r

n p p ...p= est égal au produit ()()()12 r k 1 k 1 ... k 1++ +.

Exemple

60 2 3 5=×× possède

()()()211111 32212+++=××= diviseurs stric- tement positifs (c'est vrai, on l'a déjà vu, il s'agit de : 1, 2, 3, 4, 5, 6, 10,

12, 15, 20, 30, 60).

DIVISION EUCLIDIENNE

Définition (dans N)

Soient a et b deux entiers positifs

()b0. Il existe un unique entier q (quotient) positif et un unique entier r (reste) positif vérifiant abqr=+et

0rb<. Effectuer la division euclidienne de a par b consiste à trouver

ces nombres q et r. q s'appelle le quotient et r le reste dans la division euclidienne de a par b.

Exemple

La division euclidienne de :

a57= par b15= donne : 57 15 3 12=×+ (q3= et r12=).

81. Divisibilité, nombres premiers, division euclidienne et congruences

a 349= par b25= donne : 349 25 13 24=×+ (q13= et r24=).

Remarque

L'instruction iquorem() (sous Xcas) permet d'avoir le quotient q et le reste r d'une division euclidienne.

Propriété

Dans la division euclidienne

abqr=+, on a : aqEb= où E désigne la partie entière (" floor » sous Algobox) et rabq=.

Algorithme de la division euclidienne

Voici l'algorithme de division euclidienne (dans N) de a par b :

Définition (dans Z)

Soient a et b deux entiers relatifs

()b0. Il existe un unique entier q relatif et un unique entier r positif vérifiant : abqr=+et 0rb<.

Exemples

La division euclidienne de :

a49= par b4= donne : 49 4 13 3=×+ (q13= et r3=). a28= par b3= donne : ()28 3 10 2=×+ (q10= et r2=). a34= par b5= donne : ()34 5 6 4=×+ (q6= et r4=).

Propriété

b/a r 0= (dans la division euclidienne abqr=+). contrôlescorrigés

91. Divisibilité, nombres premiers, division euclidienne et congruences

résumés de cours exercices résumés de cours exercices

Propriétés

Parmi k entiers consécutifs, l'un est multiple de k. Plus précisément,

1. L'un des 2 entiers (consécutifs) n ou

n1+ est divisible par 2.

2. L'un des 3 entiers (consécutifs) n,

n1+, n2+ est divisible par 3.

3. L'un des 4 entiers (consécutifs) n,

n1+, n2+, n3+ est divisible par

4. Etc.

Propriétés

1. Tout entier n est nécessairement de la forme

2k ou 2k 1+, avec k

entier.

2. Tout entier n est nécessairement de la forme

3k ou 3k 1+ ou 3k 2+,

avec k entier

3. Tout entier n est nécessairement de la forme

4k ou 4k 1+ ou 4k 2+,

4k 3+, avec k entier. Etc.

CONGRUENCES

Définition

Soient a et b deux entiers relatifs et n un entier strictement positif. On dit que a est congru à b modulo n lorsque ab est un multiple de n (ou lorsque n divise ab).

Notation

Lorsque a est congru à b modulo n, on écrit : abn.

Exemples

512 car 51 est un multiple de 2.

16 1 3 car 16 1 est un multiple de 3.

De même

17 1 4,

60 0 4,

81 1 4,

15 0 5,

17 2 5,

25 1 6,

35 5 6,

27 6 7,

49 0 7 ,

73 3 7,

155 11 12,

etc.

Propriété

Modulo n, a est toujours congru à son reste r dans la division euclidienne de a par n.

Exemples

17 5 3 2=×+ donc :

17 2 5.

255 7 36 3=×+ donc :

255 3 7.

1079 11 98 1=×+ donc :

1079 1 11.

42 14 3 0=×+ donc :

42 0 14 (14 divise 42).

101. Divisibilité, nombres premiers, division euclidienne et congruences

Algorithme (calculant le reste modulo n d'un entier a) L'algorithme suivant calcule le reste r modulo n d'un entier a (positif). On utilise a%n, qui désigne le reste modulo n de l'entier a.

Propriétés

Soit n un entier strictement positif.

1. aan. 2. Si abn et bcn alors acn. 3. a0n n/a. 4. Si abn et abn alors aa bbn++. 5. Si abn alors pour tout entier k, ka kb n. 6. Si abn et abn alors aa bbn××. 7. Si abn, alors pour tout entier p de N, pp abn.

Exemple

514 donc pour tout entier n0,

nn n

5114 5104 .

Ainsi pour tout entier

n0, 4 divise n 51.

Propriétés (critères de divisibilité)

Les critères qui suivent sont des applications directes des congruences :

1. Un entier est pair si son chiffre des unités est pair (comme 28 ou 300).

2. Un entier est divisible par 3 si la somme de ses chiffres l'est (comme

627).

3. Un entier est divisible par 4 si ses deux derniers chiffres forment un

entier qui l'est (comme 3132).

4. Un entier est divisible par 5 si son chiffre des unités est 0 ou 5 (comme

70 ou 155).

5. Un entier est divisible par 9 si la somme de ses chiffres l'est (comme

927).
contrôlescorrigés

111. Divisibilité, nombres premiers, division euclidienne et congruences

résumés de cours exercices résumés de cours exercices

Raisonnement par disjonction de cas

quotesdbs_dbs1.pdfusesText_1

[PDF] [PDF] 1 Divisibilité, nombres premiers, division euclidienne et congruences

51. Divisibilité, nombres premiers, division euclidienne et congruencesrésumés de cours

1Divisibilité, nombres

DIVISIBILITÉ DANS Z

Définition

Exemples

15 divise 45 puisque :

45 3 15=×.

48 est un multiple de 12 puisque :

48 4 12=×.

Propriétés

2. Tout diviseur positif a de b (avec

3. Tout entier positif (non nul) a un nombre fini de diviseurs.

Exemple

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 sont les diviseurs positifs de 60 (il en

Propriétés

Si a/b et b/c alors a/c.

Exemples

15 divise 30 et 30 divise 120 donc 15 divise 120.

12 divise 24 et 12 divise 60 donc 12 divise 228 (puisque

228 2 24 3 60=×+×

NOMBRES PREMIERS

Définition

Exemples

2, 3, 5, 7, 11, 13, 19, 23, 29 sont tous des nombres premiers (2 est le seul

61. Divisibilité, nombres premiers, division euclidienne et congruences

Définition

Théorème fondamental de l'Arithmétique

Propriétés

1. Tout nombre composé n admet un diviseur premier inférieur ou égal à

2. Si aucun des entiers compris entre 2 et

L'algorithme qui teste si un nombre est premier

Propriété

71. Divisibilité, nombres premiers, division euclidienne et congruences

12 rkk k12 r

Exemples

1. On a :

360 2 3 5=××.

2. On a :

952560 2 3 5 7=×××.

Remarques

1. Pour trouver la décomposition en facteurs premiers d'un entier, on

2. L'instruction ifactor() (sous Xcas) permet d'obtenir la décomposition

Propriété

12 rkk k12 r

Exemples

60 2 3 5=×× divise

9000 2 3 5=××.

252 2 3 7=×× divise

952560 2 3 5 7=×××.

Propriété

Le nombre de diviseurs positifs de l'entier

12 rkk k12 r

Exemple

60 2 3 5=×× possède

12, 15, 20, 30, 60).

DIVISION EUCLIDIENNE

Définition (dans N)

Soient a et b deux entiers positifs

0rb<. Effectuer la division euclidienne de a par b consiste à trouver

Exemple

La division euclidienne de :

81. Divisibilité, nombres premiers, division euclidienne et congruences

Remarque

Propriété

Dans la division euclidienne

Algorithme de la division euclidienne

Définition (dans Z)

Soient a et b deux entiers relatifs

Exemples

La division euclidienne de :

Propriété

91. Divisibilité, nombres premiers, division euclidienne et congruences

Propriétés

1. L'un des 2 entiers (consécutifs) n ou

2. L'un des 3 entiers (consécutifs) n,

3. L'un des 4 entiers (consécutifs) n,

4. Etc.

Propriétés

1. Tout entier n est nécessairement de la forme