[PDF] Multiples Division euclidienne Congruence - Lycée dAdultes PDF 01_cours_multiples_division_euclidienne

25 jui 2018 · 4 2 Compatibilité avec la congruence TERMINALE S SPÉ L'algorithme suivant est basé sur le fait que si d divise N, alors N = kd donc le

Terminale S spécialité - Feuille d'exercices no 2 Division 4/ Si a ≡ b [n] et si b ≡ c [n], alors a ≡ c [n] (la relation de congruence est transitive) 5/ Si a ≡ b [n], alors b [ Lemme d'Euclide page 439 ,Maths Repère,Hachette] Preuve: Pour trouver le pgcd de tels nombres nous aurons besoin d'un algorithme plus puissant

[PDF] Multiples Division euclidienne Congruence - Lycée dAdultes

25 jui 2018 · 4 2 Compatibilité avec la congruence TERMINALE S SPÉ L'algorithme suivant est basé sur le fait que si d divise N, alors N = kd donc le

[PDF] Chapitre 20 Arithmétique - Maths-francefr

On va maintenant mettre en place un algorithme nous fournissant le PGCD de 1) On ajoute c aux deux membres de la première congruence et on ajoute b

[PDF] Cours de spécialité mathématiques - terminale S - Maths au lycée

SPÉCIALITÉ MATHÉMATIQUES Terminale S Congruence modulo n L' algorithme suivant, dû à Ératosthène de Cyrène (276-194 av J -C ), permet de

[PDF] Vdouine – Terminale maths expertes – Chapitre 1 – Arithmétique

Vdouine – Terminale maths expertes – Chapitre 1 – Arithmétique, PGCD et congruences Cours Cette propriété est à la base de l'algorithme d'Euclide

[PDF] Chapitre I : Divisibilité dans ℤ, division euclidienne, Congruences

Terminale S (Spécialité) euclidienne, Congruences 2015/ Cet algorithme demande l'entier N à l'utilisateur , affiche le nombre de diviseurs de N (grâce à la

[PDF] Cours darithmétique

parant les olympiades internationales de mathématiques 2 3 Algorithme d' Euclide étendu et théor`eme de Bézout 5 3 Exercices de « Congruences »

[PDF] Cours de spécialité mathématiques en TS - Mathzani

7 déc 2010 · Une méthode pour déterminer le PGCD de deux entiers est l'algorithme d'Euclide Page 12 8 I DIVISIBILITÉ ET CONGRUENCES DANS Z 3 2

[PDF] ARITHMETIQUE

Lise Jean-Claude - Cours d'arithmétique -Terminale S 1/16 ARITHMETIQUE Partie des mathématiques étudiant les propriétés élémentaires des nombres entiers Introduction : Le notion de congruence - Compatibilité avec les opérations usuelles Exemple : Calculons le PGCD de 64 et 48 en utilisant cet algorithme

[PDF] Mathématiques pour - Dunod

1 4 Congruences 11 TD – Le codage connaître et maîtriser les outils mathématiques nécessaires à une bonne pratique de la programmation Dans la partie Algorithmique appliquée, où les instructions et algorithmes sont exécutés en

DERNIÈRE IMPRESSION LE25 juin 2018 à 18:32

Multiples. Division euclidienne. Congruence

Table des matières

1 Avant propos2

2 Multiples et diviseurs dans Z2

2.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.3 Règles de divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.4 Exercices d"applications. . . . . . . . . . . . . . . . . . . . . . . . . 4

2.5 Opération sur les multiples. . . . . . . . . . . . . . . . . . . . . . . 5

3 La division euclidienne5

4 Congruence7

4.1 Entiers congrus modulo n. . . . . . . . . . . . . . . . . . . . . . . . 7

4.2 Compatibilité avec la congruence. . . . . . . . . . . . . . . . . . . . 8

4.3 Applications de la congruence. . . . . . . . . . . . . . . . . . . . . . 9

4.3.1 Reste. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.3.2 Divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

PAUL MILAN1TERMINALE S SPÉ

TABLE DES MATIÈRES

1 Avant propos

L"arithmétique concerne l"étude des entiers naturelsNou relatifsZ. ?Il est important de remarquer si la résolution se fait dansNou dansZ. ?Le mode de résolution dans les ensemblesNouZest différent de celui dans l"ensemble des réelsR.

Propriété 1 :Admise

1) Toute partie non vide deNadmet un plus petit élément.

2) Toute suite dansNstrictement décroissante est stationnaire au bout d"un

certain rang.

2 Multiples et diviseurs dansZ

2.1 Définition

Définition 1 :Soitaetbdeux entiers relatifs.

aest un multiple deb, si et seulement si, il existe un entier relatifktel que : a=kb,k?Z

3 autres formulations sont possibles :

aest divisible par

bbest un diviseur deabdivisea

Exemples :

54 est un multiple de 3 car 54=18×3

-5 divise 45 car 45= (-9)×(-5)

2.2 Propriétés

0 est multiple de tout entier.

1 divise tout entier.

Siaest un multiple debet sia?=0 alors :|a|?|b|. Siadivisebet sibdiviseaalorsa=boua=-bavecaetbnon nuls.

2.3 Règles de divisibilité

Toutes les règles de divisibilité peuvent être démontrées par la congruence que l"on verra dans la suite de ce chapitre.

PAUL MILAN2TERMINALE S SPÉ

2. MULTIPLES ET DIVISEURS DANS Z

Règle 1 :Par une terminaison : 2, 5, 10, 25, 4

Un entier est divisible par 2 s"il se termine par 0, 2, 4, 6, 8. Un entier est divisible par 5 s"il se termine par 0 ou 5. Un entier est divisible par 10 s"il se termine par 0. Un entier est divisible par 25 s"il se termine par 00, 25, 50, 75. Un entier est divisible par 4 si le nombre formé par les 2 derniers chiffres est divisible par 4.

1 932est divisible par4car32est divisible par4,

par contre1 714ne l"est pas car14n"est pas divisible par4

Règle 2 :Par somme de ses chiffres : 3 et 9

Un entier est divisible par 3 (respectivement par 9) si la sommede ses chiffres est divisible par 3 (respectivement par 9).

8 232est divisible par3car :

8+2+3+5=15et15est divisible par3

4 365est divisible par9car :

4+3+6+5=18et18est divisible par9

Règle 3 :Par différence de ses chiffres : 11 Un entier de trois chiffres est divisible par 11 si la somme des chiffres extrêmes est égale à celui du milieu.

451est divisible par11car :4+1=5. On a alors451=11×41

D"une façon généraleun entier est divisiblepar 11 si ladifférence entre la somme des chiffres de rangs pairs et la somme des chiffres de rangs impairs est divisible par 11.

6 457est divisible par11car :

(7+4)-(5+6) =11-11=0et0est divisible par11

4 939est divisible par 11 car :

(9+9)-(3+4) =18-7=11et11est divisible par11

Application :

Trouver tous les diviseurs des nombres suivants : 20, 36 et 120 Grâce aux règles de divisibilité, on montre facilement que :

1) Les diviseurs de 20 sont : 1, 2, 4, 5, 10, 20

2) Les diviseurs de 36 sont : 1, 2, 3, 4, 6, 9, 12, 18, 36

3) Les diviseurs de 120 sont : 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120

PAUL MILAN3TERMINALE S SPÉ

TABLE DES MATIÈRES

Algorithme :Déterminer un algorithme qui donne l"ensemble de diviseur d"un entier naturel donné. L"algorithme suivant est basé sur le fait que siddiviseN, alorsN=kddonc le quotientkest aussi un diviseur deN. Lorsque l"on trouve un diviseur deN, on en trouve un second.

Par exemple avec 120 :

diviseurdquotientk 1120
260
340
430
524
620
815
1012

La première colonne s"arrête lorsque le

diviseurdest supérieur à⎷

N. On peut

donc écrire le programme suivant, en utilisant deux listesL1etL2qui corres- pondent aux deux colonnes du tableau.

Onfusionneensuitelesdeuxlistespour

n"en faire qu"une seuleL1.

Variables :N,K,Ientiers

1,L2listes

Entrées et initialisation

LireN

0→K

1→I

Effacer les listesL1etL2

Traitement

tant queI?⎷Nfaire siE?NI? =NIalors

K+1→K

I→L1(K)

I→L2(K)

fin

I+1→I

fin pourIde 1 àKfaire

L2(K-I+1)→L1(K+I)

fin

Sorties :AfficherL1

2.4 Exercices d"applications

1) Déterminer tous les couples d"entiers naturels tels que :x2-2xy=15

2) Déterminer tous les entiers relatifsntels que(n-3)divisen+5

1) On cherche à mettre le terme de droite en facteur de façon à faire apparaître

des diviseurs de 15. En factorisant, on trouve :x(x-2y) =15 Commexetysont des entiers naturels, on a la relation suivante :x?x-2y.

De plus les diviseurs de 15 sont :D15={1,3,5,15}

Les décompositions possibles sont donc :

?x=15 x-2y=1ou?x=5 x-2y=3 ?x=15 y=15-1

2=7ou???x=5

y=5-32=1 On obtient alors les couples solutions :(15,7)et(5,1)

2) Si(n-3)divise(n+5)alors il existe un entierktel que :n+5=k(n-3)

On cherche à factoriser par(n-3)en faisant ressortir ce terme à gauche :

PAUL MILAN4TERMINALE S SPÉ

3. LA DIVISION EUCLIDIENNE

(n-3) +8=k(n-3) k(n-3)-(n-3) =8 (n-3)(k-1) =8 donc(n-3)est un diviseur de 8. L"ensemble des diviseurs de 8 dansZest : D

8={-8,-4,-2,-1,1,2,4,8}

On a donc le tableau suivant correspondant aux valeurs possiblesden: n-3-8-4-2-11248 n-5-11245711

2.5 Opération sur les multiples

Théorème 1 :Soit trois entiers relatifsa,betc. Siadivisebetcalorsadiviseb+c,b-cou toute combinaison linéaire deb et dec:αb+βc.

ROCDémonstration :

On sait queadivisebetc, donc il existe deux entiers relatifsketk?tels que : b=kaetc=k?a On a alors :b+c= (k+k?)a,b-c= (k-k?)aetαb+βc= (αk+βk?)a

Doncadiviseb+c,b-cetαb+βc

Application :kétant un entier naturel, on posea=9k+2 etb=12k+1. Quels peuvent être les diviseurs positifs communs àaetb?

Soitdun diviseur commun àaetb.

Commeddiviseaetb, il divisec=4a-3b, soit

c=4(9k+2)-3(12k+1) =36k+8-36k-3=5 doncddivise 5. Comme 5 n"a que 2 diviseurs positifs 1 et 5, on a alorsd=1 et d=5 Les diviseurs positifs possibles communs àaetbsont : 1 et 5.

3 La division euclidienne

Définition 2 :Soitaun entier relatif etbun entier naturel non nul. On appelle division euclidienne deaparb, l"opération qui au couple(a;b) associe le couple(q;r)tel que : a=bq+ravec 0?rPAUL MILAN5TERMINALE S SPÉ
TABLE DES MATIÈRES

Exemples :
La division euclidienne de 114 par 8 : 114=8×14+2
La division de-17 par 3 :-17=3×(-6) +1

Application :

1) Trouver tous les entiers qui divisés par 5 donne un quotient égal à 3 fois le
reste.
2) Lorsqu"on diviseaparb, le reste est 8 et lorsqu"on divise 2aparb, le reste est

5. Déterminer le diviseurb.

1) Soital"entier cherché. On diviseapar 5, on a alors :
a=5q+ravec 0?r<5
Commeq=3r, on a :a=15r+r=16ravec 0?r<5
On trouve toutes les valeurs deaen faisant varierrde 0 à 4 compris, on a alors l"ensemble solution suivant :
S={0,16,32,48,64}

2) Écrivons les deux divisions, en notantqetq?les quotients respectifs :
?a=bq+8 avecb>8
2a=bq?+5 avecb>5
En multipliant la première division par 2 et en égalisant avec la deuxième, on obtient :
2bq+16=bq?+5 avecb>8
b(2q-q?) =-11 b(q?-2q) =11 best donc un diviseur positif non nul de 11, supérieur à 8, donc :b=11
Algorithme :On peut proposer l"algo-
rithme suivant, pour la division eucli- dienne, par soustractions successives :
Variables :a,b,q,rentiers

Entrées et initialisation

Lirea,b

0→q

Traitement
sia?0alors tant quea?bfaire a-b→a q+1→q fin sinon tant quea<0faire a+b→a q-1→q fin fin a→r
Sorties :Afficher "le quotient est",
q
Afficher "le reste est",r

PAUL MILAN6TERMINALE S SPÉ

4. CONGRUENCE

4 Congruence

4.1 Entiers congrus modulon
Définition 3 :Soitnun entier naturel (n?2),aetbdeux entiers relatifs. On dit que deux entiersaetbsont congrus modulonsi, et seulement si,aet bont même reste par la division euclidienne parn. On note alors : a≡bmodnoua≡b(n)
Exemples :

1) 57≡15(7)car : 57=7×8+1 et 15=7×2+1

2) Un nombre est congru à son reste modulonpar la division euclidienne parn.

3) six≡0(2), alorsxest pair et six≡1(2),xest impair
Propriétés :Comme la congruence est une relation d"équivalence, elle est :
1) Réflexive :a≡a(n)

2) Symétrique : sia≡b(n)alorsb≡a(n)

3) Transitive : sia≡b(n)etb≡c(n)alorsa≡c(n)
Remarque :comme nous allons le voir dans les exemples suivants, la notion de congruence prend tout son intérêt, dès lors qu"on s"intéresse seulement au reste, pour une propriété donnée. Par exemple, lorsqu"on s"intéresse au jour de la semaine d"une date donnée, on travaillera modulo 7. Théorème 2 :Soitnun entier naturel (n?2),aetbdeux entiers relatifs. a≡b(n)?a-b≡0(n) Démonstration :Comme il s"agit d"une équivalence, il faut démontrer la pro- priété dans les deux sens.
Dans le sens?
On sait donc quea≡b(n). Il existe doncq,q?, etrtel que : a=nq+retb=nq?+ravec 0?rOn en tire :a-b=n(q-q?) Donca-best un multiple den, donc son reste par la division parnest nul, donc :a-b≡0(n)
PAUL MILAN7TERMINALE S SPÉ

TABLE DES MATIÈRES

Dans le sens?(réciproquement)
On sait donc quea-b≡0(n). Il existektel que :a-b=kn(1) Si l"on effectue la division deaparn, on a :a=nq+r(2)
De (1) et (2), on obtient :
nq+r-b=kn -b=kn-nq-r b= (q-k)n+r
On en déduit donc :a≡b(n)

4.2 Compatibilité avec la congruence
Théorème 3 :Soitnun entier naturel(n?2),a,b,c,ddes entiers relatifs vérifiant : a≡b(n)etc≡d(n)
La congruence est compatible :

1) avec l"addition :a+c≡b+d(n)

2) avec la multiplication :ac≡bd(n)

3) avec les puissances :?k?Nak≡bk(n)

ROCDémonstration :

1)Compatibilité avec l"addition.On sait que :a≡b(n)etc≡d(n), donc(a-b)et(c-d)sont des multiples
den. Il existe donc deux entiers relatifsketk?tels que : a-b=knetc-d=k?n En additionnant ces deux égalités, on obtient : a-b+c-d=kn+k?n (a+c)-(b+d) = (k+k?)n Donc(a+c)-(b-d)est un multiple den, donc d"après le théorème 2, on obtient : a+c≡b+d(n)
2)Compatibilité avec la multiplication.On sait que :a≡b(n)etc≡d(n), donc, il existe deux entiers relatifsketk?
tels que : a=b+knetc=d+k?n En multipliant ces deux égalités, on obtient : ac= (b+kn)(d+k?n) ac=bd+k?bn+kdn+kk?n2 ac=bd+ (k?b+kd+kk?n)n ac-bd= (k?b+kd+kk?n)n
PAUL MILAN8TERMINALE S SPÉ

4. CONGRUENCE
Donc(ac-bd)est un multiple den, donc d"après le théorème 2, on a : ac≡bd(n)
3)Compatibilité avec les puissances.On prouve cette compatibilité par récurrence surk, à l"aide de la compatibilité
avec la multiplication. Nous en confions la preuve au lecteur.
4.3 Applications de la congruence

4.3.1 Reste
Déterminer les restes successifs dans la division par 7 des nombres suivants : 50

100, 100, 1003, 50100+100100.

1) Reste de 50100par la division par 7.
on a : 50

100≡1100≡1(7)

Le reste est 1.

2) Reste de 100 par la division par 7.

100=50×2, comme 50≡1(7), d"après la compatibilité avec la multiplica-
tion, on a :
100≡2(7)

Le reste est 2.

3) Reste de 100

3par la division par 7
Comme 100≡2(7), d"après la compatibilité avec les puissances, on a : 100

3≡23≡8≡1(7)
le reste est 1.
4) Reste de 50

100+100100par la division par 7
100

100=1003×33+1=?1003?33×100, donc d"après la compatibilité avec les
puissances et la multiplication, on a : 100

100≡133×2≡2(7)
Par compatibilité avec l"addition, on a alors : 50

100+100100≡1+2≡3(7)

Le reste est 3.

PAUL MILAN9TERMINALE S SPÉ

TABLE DES MATIÈRES

4.3.2 Divisibilité

Montrer que :?n?N, 3n+3-44n+2est divisible par 11
On a : 3n+3=3n×33=27×3n, or 27≡5(11), donc d"après la compatibilité avec la multiplication, on a ?n?N, 3n+3≡5×3n(11)
On a : 4

4n+2=?44?n×42, or 42≡5(11)donc 44≡52≡3(11), donc :
?n?N, 44n+2≡3n×5(11)
On en déduit donc :
3 n+3-44n+2≡0(11)
La proposition est donc vérifiée?x?N.

PAUL MILAN10TERMINALE S SPÉ
quotesdbs_dbs45.pdfusesText_45

× if you Get No preview available Click on (Next PDF) Next PDF

[PDF] [PDF] Multiples Division euclidienne Congruence - Lycée dAdultes

DERNIÈRE IMPRESSION LE25 juin 2018 à 18:32

Multiples. Division euclidienne. Congruence

Table des matières

1 Avant propos2

2 Multiples et diviseurs dans Z2

2.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.3 Règles de divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.4 Exercices d"applications. . . . . . . . . . . . . . . . . . . . . . . . . 4

2.5 Opération sur les multiples. . . . . . . . . . . . . . . . . . . . . . . 5

3 La division euclidienne5

4 Congruence7

4.1 Entiers congrus modulo n. . . . . . . . . . . . . . . . . . . . . . . . 7

4.2 Compatibilité avec la congruence. . . . . . . . . . . . . . . . . . . . 8

4.3 Applications de la congruence. . . . . . . . . . . . . . . . . . . . . . 9

4.3.1 Reste. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.3.2 Divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

PAUL MILAN1TERMINALE S SPÉ

TABLE DES MATIÈRES

1 Avant propos

Propriété 1 :Admise

1) Toute partie non vide deNadmet un plus petit élément.

2) Toute suite dansNstrictement décroissante est stationnaire au bout d"un

2 Multiples et diviseurs dansZ

2.1 Définition

Définition 1 :Soitaetbdeux entiers relatifs.

3 autres formulations sont possibles :

aest divisible par

Exemples :

54 est un multiple de 3 car 54=18×3

-5 divise 45 car 45= (-9)×(-5)

2.2 Propriétés

0 est multiple de tout entier.

1 divise tout entier.

2.3 Règles de divisibilité

PAUL MILAN2TERMINALE S SPÉ

2. MULTIPLES ET DIVISEURS DANS Z

Règle 1 :Par une terminaison : 2, 5, 10, 25, 4

1 932est divisible par4car32est divisible par4,

Règle 2 :Par somme de ses chiffres : 3 et 9

8 232est divisible par3car :

8+2+3+5=15et15est divisible par3

4 365est divisible par9car :

4+3+6+5=18et18est divisible par9

451est divisible par11car :4+1=5. On a alors451=11×41

6 457est divisible par11car :

4 939est divisible par 11 car :

Application :

1) Les diviseurs de 20 sont : 1, 2, 4, 5, 10, 20

2) Les diviseurs de 36 sont : 1, 2, 3, 4, 6, 9, 12, 18, 36

3) Les diviseurs de 120 sont : 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120

PAUL MILAN3TERMINALE S SPÉ

TABLE DES MATIÈRES

Par exemple avec 120 :

La première colonne s"arrête lorsque le

N. On peut

Onfusionneensuitelesdeuxlistespour

Variables :N,K,Ientiers

1,L2listes

Entrées et initialisation

0→K

1→I

Effacer les listesL1etL2

Traitement

K+1→K

I→L1(K)

I→L2(K)

I+1→I

L2(K-I+1)→L1(K+I)

Sorties :AfficherL1

2.4 Exercices d"applications

1) Déterminer tous les couples d"entiers naturels tels que :x2-2xy=15

2) Déterminer tous les entiers relatifsntels que(n-3)divisen+5

1) On cherche à mettre le terme de droite en facteur de façon à faire apparaître

De plus les diviseurs de 15 sont :D15={1,3,5,15}

Les décompositions possibles sont donc :

2=7ou???x=5

2) Si(n-3)divise(n+5)alors il existe un entierktel que :n+5=k(n-3)

PAUL MILAN4TERMINALE S SPÉ

aest divisible par

54 est un multiple de 3 car 54=18×3

-5 divise 45 car 45= (-9)×(-5)

0 est multiple de tout entier.

1 divise tout entier.

La division de-17 par 3 :-17=3×(-6) +1

Dans le sens?

Dans le sens?(réciproquement)