[PDF] Arithmétique — 12 Dec 2017 Cours MPSI-

View - Download Arithmétique —

Previous PDF

Next PDF

Arithm´etique

MPSI Prytan´ee National Militaire

Pascal Delahaye

12 d´ecembre 2017

1 La division euclidienne.

Th´eor`eme Fondamental 1 :Division euclidienne

Soient deux entiersa?Zetb?N?.

Alors :?! (q, r)?Z×Ntels que :

L"entierqest appel´e lequotientetrest appel´e lerestede la division euclidienne deaparb.

Preuve 1 :On d´emontre quea=bq+ravec?q?Z

r?[[0,b-1]]???q=?ab? r=a-bq.

Dessin

Division euclidienne1

Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

Remarque1.

1. Effectuer la division euclidienne deaparbsignifie d´eterminer les entiersqetrtels que?a=bq+r

2. En Python :a//bdonne le quotient eta%bdonne le reste de la DE de a par b.

D´ecomposition d"un entier dans une baseb?Navecb≥2 Tout entiern?Nse d´ecompose de fa¸con unique sous la forme : n=a0b0+a1b1+a2b2+···+apbpavecp?Net?k?[[0,p]], ak?[[0,b-1]] Les valeursa0, a1, ..., apsont obtenues par des divisions euclidiennes successives parb.

Le nombrenest alors ´ecrit :

n= apap-1...a1a0en baseb

Exemple1.La division euclidienne permet de d´emontrer que les sous-groupes deZsont de la formemZavecm?N

D´efinition 1 :La relation "divise"

Soit (a, b)?Z×Z?.

Lorsque?k?Ztel quea=b.k, on dira que :bdivisea(not´eb / aoub|a).

Remarque2.

1. Dire queb|alorsqueb >0 revient `a dire que le reste de la division euclidienne deaparbest nul.

2. On notebZl"ensemble des nombres divisibles parb. Ces nombres sont appel´es lesmultiplesdeb.

bdivisea??amultiple deb

3. La relation "divise" d´efinit une relation d"ordre partielle surN?.

M´ethode pour montrer quebdivisea:

On pourra :

1. Rechercher une relation de la formea=bc.

2. Effectuer la Division Euclidienne deaparbet prouver que le reste est nul.

3. Effectuer un calcul avec les congruences (voir ci-dessous).

4. Appliquer le th´eor`eme de Gauss (voir plus loin).

Proposition 2 :Propri´et´es de la divisibilit´e

Soienta,b,c,d,λetμdansZ.

1. Si ?a/bc/dalorsac/bd 2. Si ?a/bb/aalorsa=±b(antisym´etrie)3.

Si?a/ba/calorsa/(λb+μc)

4. Si ?a/bb/calorsa/c(transitivit´e)

Preuve 2 :Aucune difficult´e!

Remarque3.

1. La proposition 2. (antisym´etrie) est parfois utilis´ee pour d´emontrer des ´egalit´es.

2. La proposition 3. est souvent utilis´ee dans la recherche de diviseurs.

Remarque4.Comme le montre les exemples suivants, les relations de divisibilit´e permettent en particulier de r´esoudre

des ´equations d"entiers. Exemple2.(?) R´esoudre dansZles ´equations suivantes : 2 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

1.x-1|x+ 32.xy= 2x+ 3y

2 Les congruences

D´efinition 2 :La notation "congruence"

Soient trois entiersa,betn.

Lorsqu"il existek?Ztels quea=b+kn, on ´ecrit :

a≡b[n] ou parfois plus simplement :a=b[n]

On dit que "aest congru `abmodulon"

Remarque5.Ainsi, sirest le reste de la division euclidienne deaparb, on a :a≡r[b]

Proposition 3 :Op´erations sur les congruences

Les nombres intervenant dans les propri´et´es suivantes sont tous des entiers.

Les diff´erentes propri´et´es suivantes, permettent d"effectuer des "calculs de congruence" :

P 1

Si?a1≡b1[n]

a

2≡b2[n]alors :a1a2≡b1b2[n] etλa1+μa2≡λb1+μb2[n]?λ, μ?N.

P 2 Sia≡b[n] alors :•pour toutp?Non a :ap≡bp[n]

•pour toutk?Z, on a :?k.a≡k.b[n]

k.a≡k.b[kn]etk+a≡k+b[n]

•b≡a[n] (sym´etrie)

•a-b≡0 [n]

P 3

Si?a≡b[n]

b≡c[n]alors :a≡c[n] (transitivit´e)

Preuve 3 :Pas de difficult´e ...

Remarque6.La relation??≡??est une relation d"´equivalence (r´eflexive, sym´etrique et transitive)

M´ethodes

1. Pour montrer quebdiviseaon pourra donc calculeramodulobet montrer que :a≡0[b].

2. Pour d´eterminer le reste de la division euclidienne deaparb, on pourra calculeramodulobjusqu"`a

obtenir un entier compris entre 0 etb-1

Exemple3.(?) Soitn?N.

1. Montrer que : 3

2n-2nest un multiple de 7.

2. Montrer que : 11|2123+ 3121.

3. Montrer que : 6|5n3+n

4. D´eterminer le reste de la division euclidienne de 2

npar 3.

Exercice : 1

(?) Soitn?Z. Montrer que?n1≡0 [4] oun2≡4 [8] sinest pair n

2≡1 [8] sinest impair

3 PGCD et PPCM

D´efinition 3 :PGCD et PPCM

Soientaetbdeux entiers naturels dont l"un au moins est non nuls.

1. L"ensemble des entiers deN?diviseurs communs `aaetbadmet un plus grand ´el´ementδnot´eδ=a?b.

C"est leplus grand commun diviseurdes entiersaetb.

2. L"ensemble des entiers deN?multiples communs deaetbadmet un plus petit ´el´ementμnot´eμ=a?b.

C"est leplus petit commun multipledes entiersaetb. 3 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

Remarque7.

1. Le PPCM de deux entiers permet en particulier :

(a) de limiter les calculs lors de l"addition de deux fractions rationnelles. (b) de d´eterminer la plus petite p´eriode d"une fonction p´eriodique

2. Le PGCD de deux entiers permet de transformer une fraction rationnelle en une fraction irr´eductible.

Remarque8.On d´efinit de mˆeme :

1. le PGCD d"un nombre fini d"entiers naturels comme le plus grand diviseur commun `a tous les entiers.

2. le PPCM d"un nombre fini d"entiers naturels comme le plus petit multiplecommun `a tous les entiers.

Remarque9.On peut ´etendre les notions de PGCD et de PPCM `a deux entiers relatifs dont l"un au moins est non nul.

On d´efinit alors :

a?b=|a| ? |b|eta?b=|a| ? |b| Lemme 4 :Ensemble des multiples communs `a deux entiers Les multiples communs `a deux entiersaetbsont les multiples de leur PPCM.

Preuve 4 :Soitmun multiple commun `aaetb.

On effectue la division euclidienne demparμle PPCM et on d´emontre que le reste est nul. Proposition 5 :Les op´erateurs "PGCD" et "PPCM" sont commutatifs et associatifs

Pour tout entiers relatifsa,betcnon nuls, on a :

1.a?b=b?aeta?b=b?a

2. (a?b)?c=a?(b?c) (=a?b?c) et (a?b)?c=a?(b?c) (=a?b?c)

Preuve 5 :La d´emonstration de l"associativit´e est admise pour l"instant...

Remarque10.On peut ainsi d´efinir le PGCD et le PPCM denentiers :?pgcd(x1,..., xn) =x1? ··· ?xn

ppcm(x1,..., xn) =x1? ··· ?xn Exemple4.(?) D´eterminer le PGCD des 4 nombres suivants : 34, 56, 45, 124.

Proposition 6 :Relation entre PGCD et PPCM

Soientaetbdeux entiers naturels dont l"un au moins est non nul.

Alors :

(a?b)(a?b) =ab

Preuve 6 :

1. On pose?δ=a?b

μ=a?beta?,b?tels que?a=δ.a?

b=δ.b?aveca??b?= 1.

2. Remarquons queδ.a?.b?est un multiple commun `aaetbet donc `aμ, donc :?k?Ntel queδ.a?.b?=k.μ

3. Commeμest un multiple commun `aaetb, on a d"autre part :?μ=α.a

μ=β.b. Ainsi :?b?=kα

a ?=kβ.

4. Or, commea??b?= 1 alorsk= 1. Et donc :δ.a?.b?=μ.

5. On conclut en multipliant parδ.

Remarque11.Ainsi, poura, b?N:

1. sia?b= 1 alorsa?b=ab

2. si?a=a?δ

b=b?δaveca??b?= 1 alorsa?b=δa?b?

Exemple5.

Exercice : 2

(?) R´esoudre dansN2le syst`eme?x?y= 5 x?y= 60. 4 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

3.1 L"algorithme d"Euclide et ses cons´equences

Th´eor`eme Fondamental 7 :Th´eor`eme d"Euclide

Pour tout entiers relatifsaetbnon nuls.

Sia=bq+rest la division euclidienne deaparb, alors :PGCD(a, b) =PGCD(b, r). Preuve 7 :On montre sans difficult´e que{a, b}et{b, r}ont mˆeme ensemble de diviseurs communs. Pour prouver l"´egalit´e de deux PGCD ( cada?b=e?f) On pourra prouver que les deux couples (a, b) et (e, f) ont mˆeme ensemble de diviseurs commun. Cela revient `a raisonner de la fa¸con suivante :

1. Soitdun diviseur commun `aaetb, montrons que?d|e

d|f...

2. Soitdun diviseur commun `aeetf, montrons que?d|a

d|b...

Exercice : 3

(?) D´emontrer l"associativit´e de l"op´erateur?.

Algorithme d"Euclide

Le th´eor`eme pr´ec´edent permet de construire un algorithme permettant de d´eterminer le PGCD de deux entiers

non nulsaetb.

1. On poser0=aetr1=b

2. On construit alors une suite (rk) strictement d´ecroissante derestesen effectuant, tant querk?= 0, la

division euclidienne derk-1parrket en appelantrk+1le nouveau reste obtenu. r k-1=rk.qk+rk+1

3. D"apr`es le th´eor`eme d"Euclide, on ark-1?rk=rk?rk+1.

Comme (rk) est une suite d"entiers strictement d´ecroissante, il existe un rangntel quern?= 0 etrn+1= 0.

4. On a alors?a?b=rn?rn-1

r n/rn-1et ainsi : rn=a?b Exemple6.(?) Utiliser l"algorithme d"Euclide pour d´eterminer le PGCD dea= 2004 etb= 835.

En d´eduire la valeur du PPCM.

Dessin

Algorithme d"Euclide

Exercice : 4

(?) Construire en langage Python une proc´edure mettant en oeuvre l"algorithme d"Euclide. Corollaire 8 :Caract´erisation des diviseurs et multiples communs `aaetb Soient deux entiersaetb.1.dest un diviseur commun deaetbssiddivisea?b

2.mest un multiple commun deaetbssimest un multiple dea?b

5 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

Preuve 8 :

1.?C"est une cons´equence de l"algorithme pr´ec´edent.

?Evident!

2. D´ej`a d´emontr´e!

Remarque12.En d"autres termes :

1.a?best le plus grand des diviseurs communs `aaetb´egalement pour la relation d"ordre partielle "divise".

2. Siaetbdivise un entiercalorsa?bdivise aussic.

Corollaire 9 :Caract´erisation du PGCD

Siaetbsont 2 entiers relatifs non nuls, v´erifiant?a=a?δ b=b?δalors :

δ=a?b??a??b?= 1 .

Preuve 9 :Par double contrapos´ee.

M´ethodes pour d´eterminer un PGCD

1. On pourra utiliser l"algorithme d"Euclide (lorsque les entiersaetbsont connus)

2. On pourra utiliser la caract´erisation pr´ec´edente, c"est `a dire, montrer que :

il existe deux entiersa?etb?et un entierδtels quea??b?= 1 et?a=δa? b=δb?

3. On pourra enfin effectuer un raisonnement direct de type Analyse/Synth`ese :

"soitdun diviseur commun `aaetbalors..." on utilisera en particulier le fait queddivise toute combinaison lin´eaire enti`ere deaetb

Proposition 10 :2 formules de calcul

Sia,betcsont 3 entiers naturels non nuls alors :

F 1 :?(ca)?(cb) =c(a?b) (ca)?(cb) =c(a?b)F

2:ak?bk= (a?b)kpour toutk?N?

Preuve 10 :

1. Distributivit´e

(a) Pour la premi`ere :

On ´ecrit que?a=δa?

b=δb?aveca??b?= 1. On a alors?ac=cδa? bc=cδb?aveca??b?= 1. On a donccδ= (ac)?(bc) d"apr`es la caract´erisation du PGCD. (b) On d´eduit la deuxi`eme de la premi`ere `a l"aide de la relationab= (a?b)(a?b).

2. Puissance

On noteδ=a?betd=ak?bket on montre qued=δk.

Pour cela, on calculed=ak?bk=...en exprimant?a=a?.δ b=b?.δaveca??b?= 1.

On d´emontrera plus loin quea?k?b?k= 1.

Exemple7.(?) Prouver que six?y?z= 1 alorsx2?y2?z2= 1

Exercice : 5

(?) Soitaetbdeux entiers relatifs tels quea2/b2. Montrer quea/b. On pourra penser dans les raisonnements `a utiliser l"´equivalence :b|a??b=a?b. 6 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

3.2 Le th´eor`eme de Bezout

Th´eor`eme Fondamental 11 :Th´eor`eme de Bezout

Soientaetbdeux entiers relatifs non nuls.

On a :

a?b=δ? ?(u, v)?Z2tels queau+bv=δ

Exemple8.M´ethode simple pour trouveruetv:

Lorsqueaetbsont simples, en comparant les multiples on peut trouver rapidementun couple de bezout.

Faites-le pour (a, b)? {(5,3),(11,13),(4,9)}.

Preuve 11 :La d´emonstration est donn´ee par l"algorithme suivant.

Remarque13.

1. On dira que (u, v) tel queau+bv=δest uncouple de Bezoutassoci´e `aaetb.

2. On retrouve ainsi le fait qu"un diviseur commun `aaetbdivise aussia?b.

3. Comme on le verra plus tard, il existe une infinit´e de couples de Bezout.

4. : la r´eciproque de ce th´eor`eme n"est vraie que siδest un diviseur commun `aaetb.

5. Le th´eor`eme de Bezout est tr`es souvent utilis´e dans les exercices ou les d´emonstrations.

Algorithme pour trouver un couple de Bezout

Soientaetbdeux entiers relatifs non nuls tels quea?b=δ. On pourra trouver un couple de Bezout associ´e `aaetben proc´edant de la fa¸con suivante :

1. On applique l"algorithme d"Euclide `aaetb.

On construit les suites?(rn)

(qn)telles que?r0=a r

1=bet :

rn=qn+1.rn+1+rn+2avec 0< rn+1< rn. Notonsrn0=δle dernier terme non nul de la suite (rn).

2. On recherche des suites (un) et (vn) telles quern=una+vnbpour toutn?[[1,n0]].

On constate que?(un)

(vn)d´efinies par?(u0, v0) = (1,0) (u1, v1) = (0,1)et?un+2=un-qn+1un+1 v n+2=vn-qn+1vn+1conviennent.

3. Comme d"autre partδ=un0a+vn0b, alors les coefficients de Bezout sontun0etvn0.

4. Lors de l"application manuelle de cet algorithme, on pourra pr´esenter les calculs interm´ediaires dans un

tableau de la forme : r0=ar1=br2...rn...δ qkq1q2...qn... uk10u2...un...un0=u vk01v2...vn...vn0=v Exemple9.(?) Appliquer l"algorithme pr´ec´edent pour d´eterminer :

1. un couple de Bezout poura= 22 etb= 17.

2. un couple de bezout poura= 127 etb= 35.

Exemple10.(??) Sauriez-vous construire un programme d´eterminant un couple de Bezout pour un couple (a, b) donn´e?

Proposition 12 :G´en´eralisation de Bezout

Soienta1, ..., anetn?N?entiers naturels non nuls.

On a :

a

1? ··· ?an=δ? ?(u1, ..., un)?Zntels quea1u1+···+anun=δ

Preuve 12 :Par r´ecurrence surn.

4 Les nombres premiers entre eux

D´efinition 4 :Nombres premiers entre eux

Soientaetbdeux entiers relatifs non nuls.

On dit queaetbsontpremiers entre euxssia?b= 1

7 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/ Exemple11.(?) D´emontrer que deux entiers naturels cons´ecutifs sont premiers entre eux. Remarque14.On dira qu"une fractiona/bestirr´eductiblelorsquea?b= 1.

Exercice : 6

(?) Prouver que la fraction21n+414n+3est irr´eductible pour toutn?N. Th´eor`eme Fondamental 13 :Th´eor`eme de Bezout (bis)

Soientaetbdeux entiers relatifs non nuls.

On a :

a?b= 1?? ?(u, v)?Z2tels queau+bv= 1

Preuve 13 :

?Cons´equence imm´ediate du th´eor`eme de Bezout. ?Commea?bdiviseaetb, alors il diviseau+bv, c"est `a dire 1. Pour prouver que deux entiers sont premiers entre eux

On peut :

1. Soit montrer que leur PGCD est ´egal `a 1 avec l"algorithme d"Euclide

2. Soit montrer qu"un diviseur commun divise n´ecessairement 1

3. Soit utiliser le th´eor`eme de Bezout(bis)

Exemple12.(?) Soitn?N?avecn≥2. D´eterminer les ´el´ements inversibles de (Z/nZ,×). Dans quel cas tous les ´el´ements non nuls deZ/nZsont-ils inversibles?

Corollaire 14 :

Sia,betcsont 3 entiers relatifs non nuls alors :?cdivisea a?b= 1?c?b= 1. En d"autres termes : "Sia?b= 1 alors les diviseurs deasont ´egalement premiers avecb."

Preuve 14 :

M1 : On utilise l"´egalit´e de Bezout pour traduirea?b= 1. M2 : On peut aussi effectuer une d´emonstration directe.

Corollaire 15 :

- Sia,b1etb2sont 3 entiers relatifs non nuls, alors :?a?b1= 1 a?b2= 1?a?b1b2= 1. - De fa¸con plus g´en´erale :

1. siaest premier avecb1, ...etbkalorsa?b1...bk= 1.

2.a?b= 1??ap?bq= 1 pour tout (p, q)?N?2

Preuve 15 :Imm´ediat avec le th´eor`eme de Bezout, puis on g´en´eralise par r´ecurrence.

Exemple13.(?) Siaetbsont premiers entre eux, montrer queab?(a+b) = 1. Th´eor`eme Fondamental 16 :Th´eor`eme de Gauss

Soienta,betctrois entiers naturels non nuls.

On a :

Si?adivisebc

a?b= 1alorsadivisec Preuve 16 :Cons´equence imm´ediate du th´eor`eme de Bezout.

Exercice : 7

(??) L"arm´ee de Sun Zi. Pour compter l"effectif de son arm´ee, Sun zi proc`ede ainsi : 8 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

1. En regroupant les soldats par 3, il en reste 2

2. En les regroupant par 5 il en reste 3

3. En les regroupant par 7 il en reste 2

Quel est l"effectif minimum de l"arm´ee de Sun Zi?

Il existe une m´ethode plus g´en´erale (vue en TD) de r´esolution de ce type de probl`eme dit "probl`eme des restes chinois".

Formes `a reconnaˆıtre en arithm´etique :

1.ab=cpermet d"affirmer queaet(ou)bdivisec

2.ab=cdpermet ´eventuellement d"appliquer le th´eor`eme de Gauss pour montrer queadivisec

3.ab+cd= 1 permet d"en d´eduire quea?c= 1

Exemple14.Prouver d"une fraction irr´eductible a un nombre de d´ecimales fini si et seulement si son d´enominateur est

de la forme 2 i.5javec (i, j)?N2.

Equations diophantiennes

SoientA,BetCtrois entiers relatifs non nuls et on consid`ere l"´equation : (E) :Ax+By=Cavec (x, y)?Z2 Voici une m´ethode permettant de r´esoudre cette ´equation.

1. Soitδ=A?B.

(a) Siδne divise pasCalors on montre facilement queS=∅. (b) Sinon, en divisant parδ, l"´equation (E) on se ram`ene `a (E?) :A?x+B?y=C?avecA??B?= 1.

2. On d´etermine une solution particuli`ere de (E?) en recherchant un couple de Bezout associ´e `aA?etB?.

3. On en d´eduit alors l"ensembleSde toutes les solutions par une Analyse/Synth`ese `a l"aide du th´eor`eme

de Gauss. Exemple15.(?) R´esoudre dansZles ´equations : 13x+ 5y= 4 et 24x+ 20y= 36 Corollaire 17 :Soienta,betctrois entiers relatifs non nuls.???adivisec bdivisec a?b= 1?abdivisec Preuve 17 :Imm´ediat avec le th´eor`eme de Gauss. Exemple16.(?) Soitp >3 un nombre premier. Montrer que 24|p2-1.

D´efinition 5 :N nombres premiers entre eux

Soienta1, ..., an,n?N?entiers naturels non nuls.

1. On dit quea1, ..., ansontpremiers entre eux dans leur ensemblessia1? ··· ?an= 1

2. On dit quea1, ..., ansontpremiers entre eux 2 `a 2ssi?i, j?[[1,n]] tels quei?=j,ai?aj= 1

Remarque15.

1.nentiers peuvent ˆetre premiers entre eux dans leur ensemble sansˆetre premiers entre eux deux `a deux.

Montrer que les entiers 10, 6 et 15 sont premiers entre eux. Le sont-ils deux `a deux?

2. Prouver que si parminentiers, deux sont premiers entre eux, alors ils sont premiers entre eux dans leur ensemble.

En deduire une implication entre les deux notions.

Proposition 18 :Le th´eor`eme pr´ec´edent se g´en´eralise au casaest divisible parb1, ...,bkavec lesbipremiers

entre eux deux `a deux. 9 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/

5 Les nombres premiers

D´efinition 6 :Nombre premier

DansN?, on dira qu"un nombre est premier ssi :?il est diff´erent de 1il n"admet pas d"autre diviseur que 1 et lui-mˆeme.

On pourra noterPl"ensemble des nombres premiers.

Remarque16.Les nombres premiers sont lesatomesde l"arithm´etique. Comme les atomes permettent en chimie de

construire toutes les mol´ecules, nous verrons en effet que les nombres premiers engendrent l"ensemble des nombres entiers.

Exercice : 8

(?) Soitp, q?N?tels quepq>1. D´eterminer les valeursn?N?telles quenpqest premier. Remarque17.Le crible d"´erathost`ene permet de d´eterminer les premiers nombres premiers. Proposer une programmation de cet algorithme en Python.

Exercice : 9

(??) Soitaetpdeux entiers sup´erieurs `a 2.

1. Montrer que siap-1 est premier alorsa= 2 etpest premier.

2. Etudier la r´eciproque de la proposition pr´ec´edente.

Lorsque2p-1est premier alors ce nombre est appel´e un "nombre premier deMersenne". Pour prouver qu"un nombre n"est pas premier, on pourra montrer : qu"il s"´ecrit sous la formen=abaveca, b?Zet?a≥2 b≥2

Un tel nombre est ditcompos´e.

Remarque18.Un nombren?Nest compos´e s"il s"´ecrit sous la formen=abaveca, b?[[2,n-1]]

Exemple17.(??) Montrer que?n?N?, 4n3+ 6n2+ 4n+ 1 est un nombre compos´e. (Utilisez votre calculatrice...)

5.1 Propri´et´es des nombres premiers

Proposition 19 :Propri´et´es des nombres premiers

1. Soitp?Nun nombre premier etn?Z. Alors, soitpdivisen, soitp?n= 1.

En particulier, un nombre premierpest premier avec tous les ´el´ements de [[1,p-1]].

2. Deux nombres premiers distincts sont premiers entre eux.

3. Si un nombre premier divise un produit d"entiers, alors il divise l"un d"entre eux.

Preuve 19 :

1. Pas de difficult´e.

2. Pas de difficult´e.

3. On applique le th´eor`eme de Gauss et la propri´et´e 1.

Remarque19.Ainsi, si un nombre premierpdivisemkalorspdivisem.

Exemple18.(??)

1. Soitpun nombre premier. Prouver que⎷

pest un irrationnel.

2. D´emontrer par l"absurde que pour toutn?N, etppremier avecp≥3,pn+ 1 est un nombre pair.

10 Cours MPSI-2017/2018 Arithm´etique http://pascal.delahaye1.free.fr/ Th´eor`eme 20 :Le petit th´eor`eme de Fermat

Soitpun nombre premier etn?Z.

On a :

•np≡n[p].

•np-1-1≡0[p] sipne divise parn.

Preuve 20 :On montre que?k?[[1,p-1]], on a?p

k?≡0 [p].

Puis on en d´eduit que :

1.?(a, b)?Z2, on a (a+b)p≡ap+bp[p].

2.?n?Zon anp≡n[p].r´ecurrence pourn?N- cas particulierp= 2pourn?Z\N

3. sipne divise parnalorsnp-1-1≡0[p].Gauss

Remarque20.

quotesdbs_dbs22.pdfusesText_28

[PDF] arithmétique 3eme 2016

[PDF] exercices arithmétique 3ème

[PDF] cours arithmétique terminale s spécialité

[PDF] arithmétique des nombres entiers capes

[PDF] ensemble des nombres entiers naturels n et notions en arithmétique exercices

[PDF] l'arithmétique dans n tronc commun exercices

[PDF] exercices corrigés maths tronc commun maroc

[PDF] l ensemble n et les notions d arithmétique

[PDF] exercices de maths tronc commun science en francais

[PDF] les ensembles n z q r tronc commun exercices

[PDF] l arithmétique dans n tronc commun exercices corrigés

[PDF] ensemble des nombres entiers naturels n et notions d arithmétique

[PDF] l'arithmétique dans n exercices corrigés

[PDF] arithmétique dans z exercices corrigés

[PDF] arithmétique dans z exo7