[PDF] Cours : Arithmétique Les calculs de cryptage se





Previous PDF Next PDF



Petit théorème de Fermat

Démonstration par récurrence du petit théorème de Fermat. Soit p un nombre premier et P a la propriété : ap=a p . Initialisation. 0p 



LE PETIT THÉORÈME DE FERMAT En octobre 1640 dans une de

Ainsi Leibniz rédige une démonstration vers 1683 mais ne la publie pas. En 1741 1750 et 1761



Arithmétique : le petit théorème de Fermat

Démonstration par Euler et Leibniz (raisonnement par récurrence) : est un entier positif et nombre premier et la proposition ? [ ].



Démonstrations utiles pour comprendre le RSA Petit théorème de

Démonstrations utiles pour comprendre le RSA. Petit théorème de Fermat demonstration : Montrons par recurrence sur a que ap ? a(mod p).



PGCD ET NOMBRES PREMIERS

Le plus grand diviseur commun à 60 et 100 est 20. Unicité : On effectue une démonstration par récurrence ... 3) Petit théorème de Fermat.



La récurrence au fil des siècles

pour premier (petit théorème de Fermat) lui aussi entre dans des détails qui montrent bien que ce mode de raisonnement reste inhabituel. Récurrence et 



Concepts de base en arithmétique

3.4 Petit théorème de Fermat . Dans ce document nous utiliserons fréquemment le principe de récurrence ... La démonstration de ce théorème est trop.



Sur différents types de démonstrations rencontrées spécifiquement

[MRG] : Raisonnement par récurrence généralisé. Un choix de textes autour de la démonstration du petit théorème de Fermat. III.1. Un texte de Legendre.



Cours : Arithmétique

Les calculs de cryptage se feront modulo n. • Le décodage fonctionne grâce à une variante du petit théorème de Fermat. 1. Division euclidienne et pgcd.



Préparation à lagrégation interne de mathématiques - Année 2013

2 oct. 2013 (Trois démonstrations du petit théorème de Fermat.) Le «petit théorème» de Fermat ... (c) Démontrer par récurrence que pour tout entier a :.



[PDF] Petit théorème de Fermat

Démonstration par récurrence du petit théorème de Fermat Soit p un nombre premier et P a la propriété : ap=a p Initialisation 0p 



[PDF] Arithmétique : le petit théorème de Fermat

Démonstration par Euler et Leibniz (raisonnement par récurrence) : est un entier positif et nombre premier et la proposition ? [ ]



[PDF] Le petit théorème de Fermat - Mathemathieu

Ainsi Leibniz rédige une démonstration vers 1683 mais ne la publie pas En 1741 1750 et 1761 Euler en publie deux qui procèdent par récurrence et utilisent le 



[PDF] Le Petit Fermat - Licence de mathématiques Lyon 1

Démonstration : On a que ( Théorème (Petit Théorème de Fermat) Soit p premier et n ? N Alors np ? n mod p Démonstration : Par récurrence sur n



Petit théorème de Fermat : Cours Démonstration et exercices corrigés

8 jan 2022 · Voici un cours avec des exercices corrigés sur le petit théorème de Fermat On fait aussi la démonstration de ce théorème



Petit théorème de Fermat - Wikipédia

La démonstration d'Euler et de Leibniz du second énoncé utilise la formule du binôme de Newton et un raisonnement par récurrence sur l'entier a supposé positif 



Petit théorème de Fermat et démonstration – Démos Maths MPSI

4 jui 2020 · Pour démontrer le petit théorème de Fermat nous allons procéder par récurrence sur a L'hypothèse de récurrence H 



[PDF] Petit théorème de Fermat : une démonstration

Cette démonstration comporte plusieurs phases ? p divise-t-il les p 1 ? premiers multiples de a que sont ( )



[PDF] Nombres premiers Théorème de Fermat Théorème dEuler

En déduire une preuve par récurrence du petit théorème de Fermat ? Le petit théorème de Fermat donne une condition nécessaire pour qu'un nombre soit premier



[PDF] Le théorème de Fermat - Meilleur En Maths

Le théorème de Fermat 1 Remarques et rappels Si p est un nombre premier et si k ?? et 1?k?p?1 alors Démonstration: Soit d un diviseur commun de p 

:
Cours : Arithmétique

Arithmétique

Vidéo"partie 1. Division euclidienne et pgcd

Vidéo"partie 2. Théorème de Bézout

Vidéo"partie 3. Nombres premiers

Vidéo"partie 4. Congruences

Fiche d"exercices‡Arithmétique dansZ

PréambuleUne motivation : l"arithmétique est au coeur du cryptage des communications. Pour crypter un message on commence

par le transformer en un -ou plusieurs- nombres. Le processus de codage et décodage fait appel à plusieurs notions

de ce chapitre :

On choisit deuxnombres premierspetqque l"on garde secrets et on posen=pq. Le principe étant que même

connaissantnil est très difficile de retrouverpetq(qui sont des nombres ayant des centaines de chiffres).

La clé secrète et la clé publique se calculent à l"aide de l"algorithme d"Euclideet descoefficients de Bézout.

Les calculs de cryptage se ferontmodulon.

Le décodage fonctionne grâce à une variante dupetit théorème de Fermat.

1. Division euclidienne et pgcd

1.1. Divisibilité et division euclidienneDéfinition 1.

Soienta,b2Z. On dit quebdiviseaet on notebjas"il existeq2Ztel quea=bq.Exemple 1.

7j21; 6j48;aest pair si et seulement si 2ja.

Pour touta2Zon aaj0 et aussi 1ja.

Siaj1 alorsa= +1 oua=1.

(ajbetbja) =)b=a (ajbetbjc) =)ajc (ajbetajc) =)ajb+cThéorème 1(Division euclidienne). Soit a2Zet b2Nnf0g. Ilexistedes entiers q,r2Ztels quea=bq+r et06rARITHMÉTIQUE1. DIVISION EUCLIDIENNE ET PGCD2

Terminologie :qest lequotientetrest lereste.

Nous avons donc l"équivalence :r=0 si et seulement sibdivisea.

Exemple 2.

Pour calculerqetron pose la division " classique ». Sia=6789 etb=34 alors

6789=34199+23

On a bien 0623<34 (sinon c"est que l"on n"a pas été assez loin dans les calculs).678934 19934

338306

329
306

23dividendediviseur

quotient reste

Démonstration.

Existence.On peut supposera>0pour simplifier. SoitN=n2Njbn6a. C"est un ensemble non vide car n=02 N. De plus pourn2 N, on an6a. Il y a donc un nombre fini d"éléments dansN, notonsq=maxNle plus grand élément.

Alorsqb6acarq2 N, et(q+1)b>acarq+1=2 N, donc

qb6a<(q+1)b=qb+b. On définit alorsr=aqb,rvérifie alors 06r=aqbUnicité.

Supposons queq0,r0soient deux entiers qui vérifient les conditions du théorème. Tout d"aborda=bq+r=

bq0+r0et doncb(qq0) =r0r. D"autre part06r00 pour avoir1Définition 2.

Soienta,b2Zdeux entiers, non tous les deux nuls. Le plus grand entier qui divise à la foisaetbs"appelle leplus

grand diviseur commundea,bet se note pgcd(a,b).Exemple 3. pgcd(21,14) =7, pgcd(12,32) =4, pgcd(21,26) =1. pgcd(a,ka) =a, pour toutk2Zeta>0. Cas particuliers. Pour touta>0 : pgcd(a,0) =aet pgcd(a,1) =1.

1.3. Algorithme d"EuclideLemme 1.

Soient a,b2N. Écrivons la division euclidienne a=bq+r. Alorspgcd(a,b) =pgcd(b,r)

En fait on a mêmepgcd(a,b) =pgcd(b,aqb)pour toutq2Z. Mais pour optimiser l"algorithme d"Euclide on

applique le lemme avecqle quotient.

Démonstration.

Nous allons montrer que les diviseurs deaet debsont exactement les mêmes que les diviseurs deb etr. Cela impliquera le résultat car les plus grands diviseurs seront bien sûr les mêmes. Soitdun diviseur deaet deb. Alorsddivisebdonc aussibq, en plusddiviseadoncddiviseabq=r.

ARITHMÉTIQUE1. DIVISION EUCLIDIENNE ET PGCD3

Soitdun diviseur debet der. Alorsddivise aussibq+r=a.Algorithme d"Euclide.On souhaite calculer le pgcd dea,b2N. On peut supposera>b. On calcule des divisions euclidiennes successives.

Le pgcd sera le dernier reste non nul.

division deaparb,a=bq1+r1. Par le lemme1 ,pgcd(a,b) =pgcd(b,r1)et sir1=0alorspgcd(a,b) =bsinon on continue : b=r1q2+r2, pgcd(a,b) =pgcd(b,r1) =pgcd(r1,r2), r1=r2q3+r3, pgcd(a,b) =pgcd(r2,r3), rk2=rk1qk+rk, pgcd(a,b) =pgcd(rk1,rk), rk1=rkqk+0. pgcd(a,b) =pgcd(rk,0) =rk.

Comme à chaque étape le reste est plus petit que le quotient on sait que06ri+1

car nous sommes sûrs d"obtenir un reste nul, les restes formant une suite décroissante d"entiers positifs ou nuls :

b>r1>r2>>0.

Exemple 4.

Calculons le pgcd dea=600 etb=124.600=1244+104

124=1041+20

104=205+4

20=45+0

Ainsi pgcd(600,124) =4.

Voici un exemple plus compliqué :

Exemple 5.

Calculons pgcd(9945,3003).

9945=30033+936

3003=9363+195

936=1954+156

195=1561+39

156=394+0

Ainsi pgcd(9945,3003) =39.

1.4. Nombres premiers entre euxDéfinition 3.

Deux entiersa,bsontpremiers entre euxsi pgcd(a,b) =1.Exemple 6.

Pour touta2Z,aeta+1sont premiers entre eux. En effet soitdun diviseur commun àaet àa+1. Alorsddivise

aussia+1a. Doncddivise1mais alorsd=1oud= +1. Le plus grand diviseur deaeta+1est donc1. Et donc pgcd(a,a+1) =1. Si deux entiers ne sont pas premiers entre eux, on peut s"y ramener en divisant par leur pgcd :

Exemple 7.

Pour deux entiers quelconquesa,b2Z, notonsd=pgcd(a,b). La décomposition suivante est souvent utile :

a=a0d b=b0daveca0,b02Zet pgcd(a0,b0) =1Mini-exercices. 1. Écrire la division euclidienne de 111 111par 20 xx, où 20xxest l"année en cours. 2. Montrer qu"un diviseur positif de 10 008et de 10 014appartient nécessairement à f1,2,3,6g.

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT43.Calculer pgcd (560,133), pgcd(12121,789), pgcd(99999,1110).

4.

T rouvertous les entiers 1 6a650 tels queaet 50 soient premiers entre eux. Même question avec 52.2. Théorème de Bézout

2.1. Théorème de BézoutThéorème 2(Théorème de Bézout).

Soient a,b des entiers. Il existe des entiers u,v2Ztels queau+bv=pgcd(a,b)La preuve découle de l"algorithme d"Euclide. Les entiersu,vne sont pas uniques. Les entiersu,vsont descoefficients

de Bézout. Ils s"obtiennent en " remontant » l"algorithme d"Euclide.

Exemple 8.

Calculons les coefficients de Bézout poura=600etb=124. Nous reprenons les calculs effectués pour trouver

pgcd(600,124) =4. La partie gauche est l"algorithme d"Euclide. La partie droite s"obtient debas en haut. On exprime

lepgcdà l"aide de la dernière ligne où le reste est non nul. Puis on remplace le reste de la ligne précédente, et ainsi

de suite jusqu"à arriver à la première ligne.600=1244+1044=

6006+124(29)

124(5)+(6001244)6124=1041+204=

124(5)+1046

104(1241041)5104=205+44=

10420520=45+0

Ainsi pouru=6 etv=29 alors 6006+124(29) =4.

Remarque.

Soignez vos calculs et leur présentation. C"est un algorithme : vous devez aboutir au bon résultat! Dans la partie

droite,ilfautà chaque ligne bien la reformater. Parexemple104(1241041)5se réécriten124(5)+1046

afin de pouvoir remplacer ensuite 104.

N"oubliez pas de vérifier vos calculs! C"est rapide et vous serez certains que vos calculs sont exacts. Ici on vérifie à

la fin que 6006+124(29) =4.

Exemple 9.

Calculons les coefficients de Bézout correspondant à pgcd(9945,3003) =39.9945=30033+93639=9945(16)+3003533003=9363+19539=

936=1954+15639=

195=1561+3939=1951561156=394+0

À vous de finir les calculs. On obtient 9945(16)+300353=39.

2.2. Corollaires du théorème de BézoutCorollaire 1.

Si dja et djb alors djpgcd(a,b).Exemple : 4j16 et 4j24 donc 4 doit diviser pgcd(16,24)qui effectivement vaut 8.

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT5

Démonstration.Commedjauetdjbvdoncdjau+bv. Par le théorème de Bézoutdjpgcd(a,b).Corollaire 2.

Soient a,b deux entiers. a et b sont premiers entre euxsi et seulement siil existe u,v2Ztels queau+bv=1Démonstration.Le sens)est une conséquence du théorème de Bézout.Pour le sens(on suppose qu"il existeu,vtels queau+bv=1. Commepgcd(a,b)jaalorspgcd(a,b)jau. De même

pgcd(a,b)jbv. Donc pgcd(a,b)jau+bv=1. Donc pgcd(a,b) =1.Remarque.

Si on trouve deux entiersu0,v0tels queau0+bv0=d, cela n"impliquepasqued=pgcd(a,b). On sait seulement alors

que pgcd(a,b)jd. Par exemplea=12,b=8; 121+83=36 et pgcd(a,b) =4.Corollaire 3(Lemme de Gauss).

Soient a,b,c2Z.Si ajbc etpgcd(a,b) =1alors ajcExemple : si 4j7c, et comme 4 et 7 sont premiers entre eux, alors 4jc.

Démonstration.

Commepgcd(a,b) =1alors il existeu,v2Ztels queau+bv=1. On multiplie cette égalité parc

pour obteniracu+bcv=c. Maisajacuet par hypothèseajbcvdoncadiviseacu+bcv=c.2.3. Équationsax+by=cProposition 1.

Considérons l"équation

ax+by=c(E) où a,b,c2Z. 1.

L "équation(

E ) possède des solutions(x,y)2Z2si et seulement sipgcd(a,b)jc. 2.

Sipgcd(a,b)jcalors il existe même une infinité de solutions entières et elles sont exactement les(x,y) = (x0+

k,y0+k)avec x0,y0,,2Zfixés et k parcourantZ.

Le premier point est une conséquence du théorème de Bézout. Nous allons voir sur un exemple comment prouver

le second point et calculer explicitement les solutions. Il est bon de refaire toutes les étapes de la démonstration à

chaque fois.

Exemple 10.

Trouver les solutions entières de

161x+368y=115 (E)

Première étape. Y a-t-il des solutions? L"algorithme d"Euclide.

On effectue l"algorithme d"Euclide pour calculer

le pgcd dea=161 etb=368.

368=1612+46

161=463+23

46=232+0

Doncpgcd(368,161) =23. Comme115=523alorspgcd(368,161)j115. Par le théorème de Bézout, l"équation

E ) admet des solutions entières.

Deuxième étape. Trouver une solution particulière : la remontée de l"algorithme d"Euclide.

On effectue la

remontée de l"algorithme d"Euclide pour calculer les coefficients de Bézout.

368=1612+46

161=463+23

46=232+023=1617+368(3)

161+(3682161)(3)

23=161346

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT6

On trouve donc 1617+368(3) =23. Comme 115=523 en multipliant par 5 on obtient :

16135+368(15) =115

Ainsi(x0,y0) = (35,15)est unesolution particulièrede (E).

Troisième étape. Recherche de toutes les solutions.Soit(x,y)2Z2une solution de (E). Nous savons que

(x0,y0)est aussi solution. Ainsi :

161x+368y=115 et 161x0+368y0=115

(on n"a aucun intérêt à remplacerx0ety0par leurs valeurs). La différence de ces deux égalités conduit à

161(xx0)+368(yy0) =0

=)237(xx0)+2316(yy0) =0 =)7(xx0) =16(yy0) ()

Nous avons simplifié par23qui est le pgcd de161et368. (Attention, n"oubliez surtout pas cette simplification,

sinon la suite du raisonnement serait fausse.) Ainsi7j16(yy0),orpgcd(7,16) =1donc parle lemme de Gauss7jyy0. Ilexiste donck2Ztelqueyy0=7k. Repartant de l"équation():7(xx0) =16(yy0). On obtient maintenant7(xx0) =167k. D"où xx0=16k. (C"est le mêmekpourxet poury.) Nous avons donc(x,y) = (x016k,y0+7k). Il n"est pas dur de voir que tout couple de cette forme est solution de l"équation ( E ). Il reste donc juste à substituer(x0,y0)par sa

valeur et nous obtenons :Les solutions entières de 161x+368y=115 sont les(x,y) = (3516k,15+7k),kparcourantZ.Pour se rassurer, prenez une valeur dekau hasard et vérifiez que vous obtenez bien une solution de l"équation.

2.4. ppcmDéfinition 4.

Le ppcm(a,b)(plus petit multiple commun) est le plus petit entier>0 divisible paraet parb.Par exemple ppcm(12,9) =36.

Le pgcd et le ppcm sont liés par la formule suivante :Proposition 2. Si a,b sont des entiers (non tous les deux nuls) alorspgcd(a,b)ppcm(a,b) =jabjDémonstration. Posonsd=pgcd(a,b)etm=jabjpgcd(a,b). Pour simplifier on supposea>0etb>0. On écrita=da0et b=db0. Alorsab=d2a0b0et doncm=da0b0. Ainsim=ab0=a0best un multiple deaet deb.

Il reste à montrer que c"est le plus petit multiple. Sinest un autre multiple deaet debalorsn=ka=`bdonc

kda0=`db0etka0=`b0. Or pgcd(a0,b0) =1 eta0j`b0donca0j`. Donca0bj`bet ainsim=a0bj`b=n.Voici un autre résultat concernant le ppcm qui se démontre en utilisant la décomposition en facteurs premiers :

Proposition 3.

Si ajc et bjc alors ppcm(a,b)jc.

Il serait faux de penser queabjc. Par exemple6j36,9j36mais69ne divise pas36. Par contreppcm(6,9) =18 divise bien 36.Mini-exercices. 1.quotesdbs_dbs33.pdfusesText_39
[PDF] equivalent temps plein mode de calcul

[PDF] assistant mise en scène cinéma

[PDF] théorème de bezout

[PDF] calcul etp excel

[PDF] théorème de wilson exercice corrigé

[PDF] mise en scène arts plastiques

[PDF] définition éducation thérapeutique

[PDF] équivalent temps plein pluriel

[PDF] equivalent temps plein fonction publique

[PDF] lille 1

[PDF] la fermentation alcoolique pdf

[PDF] utilisation des microorganismes dans l'industrie alimentaire pdf

[PDF] role des micro organisme dans la fabrication des aliments

[PDF] fermentation conservation aliments

[PDF] fermentation propionique réaction