Congruences et théorème chinois des restes
Cherchons à résoudre le système de congruences suivant :.. x ? 1 (mod 3) x ? 2 (mod 5) x ? 3 (mod 7). On pose M = 3 × 5 × 7 = 105.
CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE
(1) Dans la congruence 36x ? 80 (mod 90) on a pgcd(36
M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2
Résoudre le système de congruences :.. x ? 1 mod 3 x ? 2 mod 11 x ? 51 mod 61. Solution. L'algorithme d'Euclide étendu :.
Congruence - Equations diophantiennes
Cette relation est appelée la relation de congruence modulo p. Exemples Soit à résoudre le système de congruence. { x ? 5 (mod 11) x ? 7 (mod 15).
Cours S4 : Mathématiques pour linformatique
A présent essayons de résoudre des systèmes particuliers de congruences. Lemme 1.35 (Lemme chinois). On cherche à résoudre le système.
Avant propos Références 1 Questions de coût (de la vie ?)
Théorème 3.4 (Système de congruence) Soit m et n deux entiers premiers entre eux. vous pouvez commencer à résoudre les systèmes avec a = 1.
Cours darithmétique
19 Résolution de systèmes de congruences linéaires. 90. 20 Le théorème des restes chinois. 94. 21 Le théorème d'Euler. 97. Mohamed ATOUANI.
Exercices à savoir faire
Déterminer un inverse de 75 modulo 13. Exercice 4. Résoudre dans Z les systèmes de congruence suivants. (1). {?.
Observation de la transition lycée-université grâce à lanalyse
Dans les deux sujets le but est de résoudre un système de deux congruences
Feuille 1 : Arithmétique élémentaire et congruences
Exercice 2 Résoudre les équations. 19x ? 2 (mod 140) Exercice 3 Résoudre 42x + 150y = 18. Exercice 4 ... Exercice 15 Résoudre le système de congruences.
[PDF] Congruences et théorème chinois des restes - Apprendre-en-lignenet
Résolution des équations sur les congruences Supposons que l'on cherche à résoudre : 3x ? 5 (mod 7) Cela est facile car le modulo est premier : On sait
[PDF] chapitre 3 : congruences et arithmétique modulaire
Congruences Définition 1 1 Soit m a b entiers On dit que a est congru à b modulo m si m divise a ? b (On dit aussi que “a et b sont congrus modulo m”
[PDF] Equations diophantiennes - Congruence - livres-mathematiquesfr
x ? b (mod n) sont données par x = x0 + kmn où x0 est une solution particulière Exemple Soit à résoudre le système de congruence { x ? 5 (mod 11) x ? 7
[PDF] UN PROBLEME DE RESTES ET SA RESOLUTION PAR QIN
Qin Jiushao au XIIIe siècle résolut (ou du moins trouva une solution à) un problème de répartition de grains basé sur un système de congruences On s'
[PDF] Corrigé Feuille 4 (Congruences ) Exer
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]
[PDF] M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2
Résoudre le système de congruences : Le système formé des deux premières équations équivaut donc à la congruence x ? a mod (3×11) avec a
[PDF] [PDF] Arithmétique - Exo7 - Cours de mathématiques
Nombres premiers · Vidéo ? partie 4 Congruences Résoudre les équations : 407x + 129y = 1 ; 720x + 54y = 6 ; 216x + 92y = 8 4 Trouver les couples (a
[PDF] Théor`eme des restes chinois - Epsilon 2000
le syst`eme de congruences défini par : ?k ? [1p]x ? ak (mod nk) admet une unique solution modulo Résoudre dans Z le syst`eme suivant :
Arithmétique dans Z: Comment résoudre un système de congruence
26 mai 2020 · Arithmétique dans Z: Comment résoudre un système de congruence - Exercice Beta Life Durée : 24:43Postée : 26 mai 2020
[PDF] Master-1 de mathématiques (MAlg 1) 2004/2005 - Institut Fourier
13 3 Résolution d'un système linéaire dans un anneau euclidien 327 Divisibilité des entiers pgcd ppcm congruences
Comment résoudre un système de congruence ?
Principe des congruences
Comment ? marche ? Pour déterminer des congruences modulo n , on élimine du nombre les multiples de n . Exemple 1 On sait que ; 15 est donc égal à un multiple de 7 plus 1 ; on a donc : On a donc un nombre limité de possibilités quand on travaille avec les congruences .Comment fonctionne le tableau de congruence ?
Le caractère utilisé pour exprimer la congruence de deux entiers est ?.
1a ? b (n) ;2a ? b [n] ;3a ? b (mod n) ;4a ? b mod n (notation de Gauss).Comment Ecrire congruence ?
Définition : On dit qu'un entier relatif admet un inverse modulo ( n ? N , n ? 2 ) lorsqu'il existe un entier relatif tel que a b ? 1 [ n ] . On dit aussi que est inversible modulo .
Congruences et théorème
chinois des restesMichel Van Caneghem Février 2003Turing : des codes secrets aux machines universelles #2c?2003 MVC Les congruencesDéveloppé au début du 19ème siècle par Carl Friedrich Gauss. On dit quea≡b(modn)sia-best divisible par n. Sirest le reste de la division deaparn,rs"appelle lerésidu deamodulon.5a≡b(modn)si et seulement si leurs résidus sont égaux.5La relationa≡b(modn)est une relation d"équivalence
surZ5On noteraale représentant dea. L"ensemble de ces classes d"équivalence est notéZ/nZ, ets"appelle l"ensemble des entiers modulon.Turing : des codes secrets aux machines universelles #2c?2003 MVC 1
Les opérations modulonOn définit l"addition et la multiplication modulonde la ma- nière suivante :a+b=a+ba×b=a×bmodulo 7modulo 6x0 1 2 3 4 5 600 0 0 0 0 0 01012 3 4 5 6
20 2 4 613 5
30 3 6 2 514
40 415 2 6 3
50 5 316 4 2
60 6 5 4 3 21x0 1 2 3 4 500 0 0 0 0 0
10 1 2 3 4 5
20 2 402 4
30 30303
40 4 204 2
50 5 4 3 2 1Turing : des codes secrets aux machines universelles #2c?2003 MVC 2
Les propriétés de ces opérationsL"addition modulonest (groupe abélien) :7commutative7associative7il y a un élément neutre7tout élément à un inverse
La multiplication modulon(anneau commutatif)8commutative8associative8il y a un élément neutre8La multiplication est distributive par rapport à l"addition
Sipest un nombre premier, alorsZ/pZest uncorps fini commutatif(Corps de Galois)Turing : des codes secrets aux machines universelles #2c?2003 MVC 3 Les diviseurs de zéroFPour quexpossède une classe inverse, il faut et il suffitquex?n= 1. Cet inverse est unique et on le notex-1.FSix?n?= 1alors il existeytel quex×y= 0. On dit quex
est un diviseur de zéro.FSinest premier alors tout élément sauf 0 possède un inverse.Ex :Z/15Z:q0,3,5,6,9,10,12 sont des diviseurs de zéroq1(1), 2(8), 4(4), 7(13), 8(2), 11(11), 13(7), 14(14) ont un in-
verseTuring : des codes secrets aux machines universelles #2c?2003 MVC 4 Les éléments inversiblesL"ensemble des éléments inversibles : Z forment un sous-groupe multiplicatif du groupe multiplicatif Z/pZ. En effet si :Mx?Z?palorsx?p= 1My?Z?palorsy?p= 1Mdoncxy?p= 1Met par conséquentxy?Z?p.l"élément neutre est bien sûr1.Turing : des codes secrets aux machines universelles #2c?2003 MVC 5
Résolution des équations sur les congruencesSupposons que l"on cherche à résoudre :3x≡5 (mod 7)
Cela est facile car lemodulo est premier: On sait que3-1≡5 (mod 7), on a doncx≡5×5≡4 (mod 7).
Quandle modulo n"est pas premiernous avons le théorèmesuivant : Sia,betmsont des entiers, et sia?m=dalors :3Sidne divise pasb, alorsax≡b(modm)n"a pas de
solution3Sinon l"équation précédente a exactementdsolutions.Turing : des codes secrets aux machines universelles #2c?2003 MVC 6
équations sur les congruences (2)Cherchons à résoudre par exemple :6x≡9 (mod 15) =?3(2x-3)≡0 (mod 15)
On sait que 3 est un diviseur de zéro, donc :
3×0≡0 (mod 15) 3×5≡0 (mod 15) 3×10≡0 (mod 15)
Donc les solutions sont :42x-3≡0 (mod 15)d"oux≡9 (mod 15),42x-3≡5 (mod 15)d"oux≡4 (mod 15),42x-3≡10 (mod 15)d"oux≡14 (mod 15).Turing : des codes secrets aux machines universelles #2c?2003 MVC 7
Recherche de l"inverseOn veut chercher l"inverse deamodulom:a-1≡? (modm). On sait que cet inverse existe si :a?m= 1. On sait alors qu"il existe deux nombresxetytels que : ax+my= 1 Ce qui entraine queax≡1 (modm)etxest l"inverse cher- ché. Si on cherche13-1(mod 15), on vérifie que13?15 = 1. Avec la méthode proposée dans le premier cours, on trouve que :13×7 + 15×(-6) = 1
donc13-1≡7 (mod 15).Turing : des codes secrets aux machines universelles #2c?2003 MVC 8 Résolution d"un systèmeDans le cas ou le modulo est premier, on a un corps et tout se passe comme dans les corps connus : ?3x+ 4y≡5 (mod 13)2x+ 5y≡7 (mod 13)
?3x+ 4y≡5 (mod 13)7y≡11 (mod 13)
et on trouve :7y≡7-1×11≡9 (mod 13)7x≡3-1×(5-36)≡3-1×8≡9×8≡7 (mod 13)Turing : des codes secrets aux machines universelles #2c?2003 MVC 9
Le petit théorème de FermatSipest un nombre premieret siaest un entier qui n"est pas divisible parpalors : a p-1≡1 (modp) Ce théorème est très important pour les codes secrets. La réciproque est fausse (nombres de Carmichael). [a560≡1 (mod 561)hors561 = 3×11×17]Théorème de Wilson :Sipest premier alors :
(p-1)!≡ -1 (modp) La réciproque est vraie, mais ce théorème ne sert à rien (pour l"instant!).Turing : des codes secrets aux machines universelles #2c?2003 MVC 10Le théorème d"EulerLe nombre d"éléments ayant un inverse modulonest notéΦ(n). Cette fonction s"appelle l"indicatrice d"Euler. C"est
aussi le nombre d"entierxtels quen?x= 1. Par exemple :Φ(15) = 8
Remarque : Sipest premier alorsΦ(p) =p-1.Théorème d"Euler :Siaest un entier premier avecnalors :
aΦ(n)≡1 (modn)
Remarque : le théorème de Fermat est une conséquence de ce théorème.Turing : des codes secrets aux machines universelles #2c?2003 MVC 11 Le théorème de LagrangePour tout groupe fini(G,×)et tout sous-groupe(H,×)tel queH?Galors|H|divise|G|. On appelle ordre d"un groupeGle nombre d"éléments de ce groupe :|G|
Pour touta?G, considérons le sous-groupe
H a={x?G|x=y×a y?H} H an"est pas vide car il contienta. C"est un sous-groupecar :Nx1?Haentrainex1 =y1×a y1?GNx2?Haentrainex2 =y2×a y2?GNet doncx1×x2 =y1×a×y2×a= (y1×a×y2)×aTuring : des codes secrets aux machines universelles #2c?2003 MVC 12
Le théorème de Lagrange (2)1.|H|=|Ha|car on peut construire une bijection entreHet H a,car les groupes sont finis.2.ou bienHa=Hb, ou bienHa∩Hb=∅. Si il y a un élémentccommun alorsc=x1×a=x2×b. Alorsx×a= (x×x1-1×x1)×a= (x×x1-1×x2)×bdonc :QLesHaforment une partition de G.QTous les ensembles ont la même tailleQdonc l"ordre deHdivise l"ordre deGTuring : des codes secrets aux machines universelles #2c?2003 MVC 13
Le théorème d"Euler (bis)On définit l"ordre d"un élémentx?Gpar : ord(x) =min{k >0|xk= 1} On en déduit immédiatement que :9pour toutx?Galorsord(x)divise|G|. Il suffit de consi- dérer les éléments :1,x1,x2,...,xk-1, ils forment un sous groupe deG;9pour toutx?Galorsx|G|= 1. En considérantZ?pqui contientΦ(p)éléments, on en déduitimmédiatement que pour toutx?Z?pon axΦ(p)= 1dansZ?p.Turing : des codes secrets aux machines universelles #2c?2003 MVC 14
L"indicatrice d"EulerSip?q= 1alors :
Φ(pq) = Φ(p)Φ(q)
On dit que la fonctionΦest une fonction multiplicative.Sipetqsont deux nombres premiers alors :
Φ(pq) = (p-1)(q-1)
Enfin sin=pα11pα22...pαnnalors
Φ(n) =n(1-1p1)(1-1p2)...(1-1pn)Turing : des codes secrets aux machines universelles #2c?2003 MVC 15
Calcul de la puissance modulaire (2)Il faut tout d"abord calculer les deux fonction suivantes :4modulo(a,b,d):a=b(modd). Si on remarque que :
b=qd+a, le modulo est le reste de la divison debpard.4multmod(a,b,c,d):a=b×c(modd). On calcule le pro-
duitb×cet on prend le résultat modulod.La fonctionpowermod(a,b,c,d):a=bc(modd)se calcule
alors au moyen de la procédure suivante : x n=?(x2)n/2sinest pair, x(x2)n/2sinest impair.Turing : des codes secrets aux machines universelles #2c?2003 MVC 17 Calcul de la puissance modulaire (3)Calculey=xn(modm)1ifnmod 2?= 0theny?xelsey?1fi2do3n? ?n/2?4ifn= 0thenexitfi5x?x×x(modm)
6ifnmod 2?= 0theny?y×x(modm)fi7od8yTuring : des codes secrets aux machines universelles #2c?2003 MVC 18
Le théorème chinois des restesSoitm1,m2,...,mrune suite d"entiers positifs premiers entre eux deux à deux. Alors le système de congruences :????? ???x≡a1(modm1) x≡a2(modm2) x≡ar(modmr) a une solution uniquexmoduloM=m1×m2× ··· ×mr: x=a1M1y1+a2M2y2+···+arMryr avec M i=M/miyiMi≡1 (modmi)Turing : des codes secrets aux machines universelles #2c?2003 MVC 19 Un exempleCherchons à résoudre le système de congruences suivant :??? ?x≡1 (mod 3) x≡2 (mod 5) x≡3 (mod 7)On poseM= 3×5×7 = 105
M1= 105/3 = 35y1×35≡1 (mod 3)y1= 2
M2= 105/5 = 21y2×21≡1 (mod 5)y2= 1
M3= 105/7 = 15y3×15≡1 (mod 7)y3= 1
x≡1×35×2 + 2×21×1 + 3×15×1≡157≡52 (mod 105)Turing : des codes secrets aux machines universelles #2c?2003 MVC 20
Un exemple (2)Quand les modulos ne sont pas premiers entre eux?x≡1 (mod 6) x≡4 (mod 15)??? ?x≡1 (mod 2) x≡1 (mod 3) x≡4 (mod 5) x≡1 (mod 6)???x≡1 (mod 2) x≡1 (mod 3) x≡4 (mod 15)???x≡1 (mod 3) x≡4 (mod 5)Turing : des codes secrets aux machines universelles #2c?2003 MVC 21Un exemple (3)?x≡1 (mod 9)
x≡4 (mod 15)??? ?x≡1 (mod 9) x≡1 (mod 3) x≡4 (mod 5) x≡1 (mod 9) =?x≡1 (mod 3) =??x≡1 (mod 9) x≡4 (mod 5)Turing : des codes secrets aux machines universelles #2c?2003 MVC 22 Le théorème chinois des restes (2)Soitm=m1×m2× ··· ×mralors l"application Z/mZ↔Z/m1Z×Z/m2Z× ··· ×Z/mrZ estbijective. Le théorème des restes chinois permet de construire l"application réciproque.Six= (x1,x2,...,xr)ety= (y1,y2,...,yr)alors :Fx+y= (x1+y1,x2+y2,...,xr+yr)Fx×y= (x1×y1,x2×y2,...,xr×yr)Turing : des codes secrets aux machines universelles #2c?2003 MVC 23
Le théorème chinois des restes (3)Un exemple avec3×5 = 15.0→(0,0) 8→(2,3)
1→(1,1) 9→(0,4)
2→(2,2) 10→(1,0)
3→(0,3) 11→(2,1)
4→(1,4) 12→(0,2)
5→(2,0) 13→(1,3)
6→(0,1) 14→(2,4)
7→(1,2)
Ex1 :3 + 8 = (0,3) + (2,3) = (2,6) = (2,1) = 11
Ex2 :2×6 = (2,2)×(0,1) = (0,2) = 12Turing : des codes secrets aux machines universelles #2c?2003 MVC 24
Application aux grands nombresComment additionner et multiplier :x= 3589ety= 11235 en ne faisant que des opérations sur des nombres de deux chiffres. On a : x≡25 (mod 99)y≡48 (mod 99) x≡61 (mod 98)y≡63 (mod 98) x≡0 (mod 97)y≡80 (mod 97) x≡74 (mod 95)y≡25 (mod 95) x+y≡73 (mod 99)x×y≡12 (mod 99) x+y≡26 (mod 98)x×y≡21 (mod 98) x+y≡80 (mod 97)x×y≡0 (mod 97)x+y≡4 (mod 95)x×y≡45 (mod 95)x+y=14824x×y=40322415Turing : des codes secrets aux machines universelles #2c?2003 MVC 25
Une petite propriétéSia=bq+ravecr < balors : 2 a-1 = 2bq+r-1 = 2bq2r+ 2r-2r-1 = 2r(2bq-1) + 2r-1 2 bq-1 = (2b)q-1q= (2b-1)Q? 2 a-1 = (2b-1)Q+ 2r-1 En appliquant l"algorithme d"Euclide aux exposants on en déduit que : (2 a-1)?(2b-1) = (2a?b-1) puis que siaetbsont premiers entre eux alors : (2 a-1)?(2b-1) = 1Turing : des codes secrets aux machines universelles #2c?2003 MVC 26 Des tests de divisibilitéTest 1 :Un nombre est divisible par2ksi seskderniers chiffres sont divisibles par2k.10≡0 (mod 2) 10j≡0 (mod 2j)Test 2 :Un nombre est divisible par5ksi seskderniers
chiffres sont divisibles par5k.Test 3 :Un nombre est divisible par 3 ou 9 si la somme de ses chiffres est divisible par 3 ou par 9.10≡1 (mod 3) 10≡1 (mod 9)
c"est lapreuve par 9.Turing : des codes secrets aux machines universelles #2c?2003 MVC 27 Des tests de divisibilité (2)Test 4 :Un nombre est divisible par 11 si la somme alternée de ses chiffres est divisible par 11.10≡ -1 (mod 11)
Ex : 723160823 est divisible par 11 car :
7-2+3-1+6-0+8-2+3 = 22Test 5 :Un nombre est divisible par 7, 11 ou 13 si la somme
alternée des blocs de 3 chiffres est divisible par 7, 11 ou 13.7×11×13 = 1001 1000≡ -1 (mod 1001)
Ex 59358208 est divisible par 7 et 13 mais pas par 11 car :59 - 358 + 208 = -91 = 910 = 13*7*10.Turing : des codes secrets aux machines universelles #2c?2003 MVC 28
Calcul du jour de la semaineOn veut savoir à quel jour de la semaine correspond une date donnée. On va représenter les jours avec les entiers suivants :Dimanche = 0 Jeudi = 4Lundi = 1 Vendredi = 5
Mardi = 2 Samedi = 6
Mercredi = 3
Pour Jules César l"année avait365,25 joursce qui ne cor- respond pas à la valeur exacte qui est de365,2422 jours. Ily a donc une erreur d"environ 8 jours au bout de 1000 ans.En 1582, il y avait 10 jours de retardTuring : des codes secrets aux machines universelles #2c?2003 MVC 29
Calcul du jour de la semaine (2)Le pape Grégoire décida donc de passer du 5 Octobre 1582 au 15 Octobre 1582, et il donna la règle ducalendrier grégo-rienqui est encore utilisé aujourd"hui.>Les années bissextiles sont les années divisibles par 4
sauf les siècles>Les siècles divisibles par 400 sont cependant bissextiles (Ex : 2000) Cela donne une durée d"année de365,2425 joursce qui donne encore une erreur de 1 jour pour 3000 ans. Remarque : ce changement de calendrier a été effectué auJapon en 1873 et en Grèce en 1923.Turing : des codes secrets aux machines universelles #2c?2003 MVC 30
Excel de Microsoft27 février 1900 27 février 200028 février 1900 28 février 200029 février 190029 février 2000
1 mars 1900 1 mars 2000
2 mars 1900 2 mars 2000Turing : des codes secrets aux machines universelles #2c?2003 MVC 31
Calcul du jour de la semaine (3)Pour simplifier les calculs on va supposer que l"année com- mence le 1er Mars. C"est à dire que Février est le 12èmemois de l"année. On écrira l"année sous la formeS×100+A.Première étape :On va calculer le jour de la semaine du 1er
Mars d"une année :
D≡3-2×S+A+?S/4?+?A/4?(mod 7)
Ex : 1er Mars 2002 :
D≡3-40 + 2 + 5 + 0 =-30 = 5 (mod 7)
C"est donc un Vendredi (prochain cours!!!!).Turing : des codes secrets aux machines universelles #2c?2003 MVC 32
Calcul du jour de la semaine (4)Deuxième étape :Il ne reste plus qu"a s"occuper du jour dans l"année. On remarque que31≡3 (mod 7) 30≡2 (mod 7)
Il suffit alors de construire la table correspondante : (3,2,3,2,3,3,2,3,2,3,3). Mais on peut exprimer cette table avec la formule :?2,6×M-0.2? -2d"ou la formule finale : j≡J+?2.6×M-0.2? -2×S+A+?S/4?+?A/4?(mod 7)Ex : 22 Février 2002 (22/12/2001)
j≡22 + 31-40 + 1 + 5 + 0 = 19 = 5 (mod 7)C"est donc un VendrediTuring : des codes secrets aux machines universelles #2c?2003 MVC 33
quotesdbs_dbs22.pdfusesText_28[PDF] consommation ampoule 60w
[PDF] combien coute une ampoule allumée
[PDF] calcul consommation ampoule led
[PDF] lumiere allumée toute la nuit consommation
[PDF] calcul de consommation électrique d'un appareil
[PDF] consommation ventilateur 40w
[PDF] consommation congelateur ancien
[PDF] consommation four electrique kwh
[PDF] tableau de consommation des appareils électroménagers pdf
[PDF] consommation frigo américain
[PDF] consommation frigo kwh
[PDF] cout electricite congelateur
[PDF] consommation vieux frigo
[PDF] consommation congelateur 30 ans