« Approfondissements de lycée/Arithmétique modulaire » : différence entre les versions

Contenu supprimé Contenu ajouté
Aucun résumé des modifications
Aucun résumé des modifications
Ligne 547 :
Que remarquez-vous ?
 
===Théorème des restes chinois===
===Chinese remainder theorem===
TheLe Chinesethéorème remainderdes theoremrestes ischinois knownest inconnu Chinaen asChine sous le nom ''Han Xing Dian Bing'', whichqui indans itssa mosttraduction naivela translationplus meansnaïve veut dire ''Han Xing countscompte hisses soldierssoldats''. TheLe problème original problemest goesle likesuivant this:
:ThereIl existsexiste aun numbernombre ''x'', whenlorsque divideddivisé bypar 3 leavesdonne remainderle reste 2, whenlorsque divideddivisé bypar 5 leavesdonne remainderle reste 3 andet whenlorsque divideddivisé bypar 7 leavesdonne remaiderle reste 2. FindTrouver le theplus smallestpetit ''x''.
WeNous tranlatetraduisons thela question intoen symbolicforme symbolique form:
:<math>
\begin{matrix}
Ligne 559 :
</math>
 
Comment allons-nous rechercher un tel ''x'' ? Nous utiliserons une méthode familière et cela sera illustré de meilleure manière par un exemple :
How do we go about finding such a ''x''? We shall use a familar method and it is best illustrated by example:
 
Looking atRegardons x = 2 (mod 3), wenous makefaisons thele ''jumpsaut'' intoen ordinarymathématique mathematicsordinaires
:<math>
\begin{matrix}
Ligne 569 :
</math>
 
NowMaintenant, weregardons look at the equationl'équation modulo 5
:<math>
\begin{matrix}
Ligne 579 :
</math>
 
SubstituteSubstituons intodans (1) topour getobtenir (2)
:<math>
x = 2 + 3(2 + 5b) \qquad (2)
Ligne 589 :
b \equiv 1 \pmod{7}
</math>
WeNous choosechoisissons b = 1 topour minimiseminimiser x, thereforepar conséquent x = 23. AndEt aune simplevérification checksimple (toà beexécuter performedpar byle the readerlecteur) shouldconfirmerait confirm thatque x = 23 isest aune solution. AUne goodbonne question toà askposer isest what"quel isest thele nextprochain smallestplus petit ''x'' thatqui satisfait satisfiesaux thetrois threecongruences congruencies? TheLa answerréponse isest x = 128, andet thele nextprochain ''x'' isest 233 andet thele nextprochain ''x'' isest 338, andet theyils differdiffèrent byde 105, thele productproduit ofde 3, 5 andet 7.
 
Nous illustrerons la méthode de résolution d'un système de congruences supplémentaire par les exemples suivants :
We will illustrate the method of solving a system of congruencies further by the following examples:
 
'''ExampleExemple 1'''
FindTrouver thele smallestplus petit ''x'' thatqui satifait satifies:
:<math> x \equiv 1 \pmod{3} </math>
:<math> x \equiv 2 \pmod{5} </math>
Ligne 612 :
\end{matrix}
</math>
ThereforePar conséquent 52 isest le theplus smallestpetit ''x'' thatqui satifiessatisfait theles congruenciescongruences.
 
'''ExampleExemple 2'''
FindTrouver thele smallestplus petit ''x'' thatqui satifait satifies:
:<math> x \equiv 5 \pmod{11} </math>
:<math> x \equiv 3 \pmod{7} </math>
Ligne 635 :
\end{matrix}
</math>
ThereforePar conséquent 269 isest le theplus smallestpetit ''x'' thatqui satifiessatifait theles congruenciescongruences.
 
==== ExcercisesExercices ====
1.
SolveRésoudre forpour ''x''
:<math>
\begin{matrix}
Ligne 649 :
 
2.
SolveRésoudre forpour ''x''
:<math>
\begin{matrix}
Ligne 658 :
</math>
 
==== Existence of ad'une solution ====
TheLes exercisesexercices aboveprécédents allont havetous aune solution. SoDonc, doesexiste-t'il thereun existsystème ade systemcongruences oftel congruenciesqu'aucune suchsolution thatne nopuisse solutionêtre couldtrouvée be found? ItC'est certainly iscertainement possible, considerconsidérons :
:x &equiv; 5 (mod 15)
:x &equiv; 10 (mod 21)
Ligne 665 :
:x &equiv; 1 (mod 2)
:x &equiv; 0 (mod 2)
mais nous ne considérons pas des exemples absurdes comme cela.
but we won't consider silly examples like that.
 
Revenons au premier exemple, nous pouvons essayer de résoudre en faisant :
Back to the first example, we can try solve it by doing:
:<math>
\begin{matrix}
Ligne 675 :
\end{matrix}
</math>
thel'équation aboveprécédente equationn'a haspas node solution becauseparceque 3 doesn'a not have anpas d'inverse modulo 21 !
 
YouVous maypouvez beconclure quickrapidement toque concludesi thatdeux if twosystèmes modulo systemspartagent shareun afacteur commoncommun factoralors thenil theren'existe ispas node solution. ButMais thisceci isn'est notpas vrai true! ConsiderConsidérons :
:x &equiv; 4 (mod 15)
:x &equiv; 7 (mod 21)
Ligne 688 :
\end{matrix}
</math>
obviouslyévidemment, aune solution existsexiste, namelyexplicitement k = 3, andet theles twodeux systèmes modulo systemssont arele themême samecomme aspour thele firstpremier exampleexemple (i.e. 15 and 21).
 
So what determines whether a system of congruencies has a solution or not? Let's consider the general case:
Ligne 798 :
for ''p'' &equiv; 1 (mod 4)
 
== ProjectProjet -- TheLa Squareracine Rootcarrée ofde -1 ==
1. La question 10 de l'ensemble des problèmes a montré que
1. Question 10 of the problem set showed that
:<math>\sqrt{-1} \equiv \sqrt{p-1} \pmod{p}</math>
existsexiste forpour ''p'' &equiv; 1 (mod 4) primepremier. ExplainExpliquer whypourquoi noaucune squareracine rootcarrée ofde -1 existn'existe ifsi ''p'' &equiv; 3 (mod 4) primeest premier.
 
2. ShowMontrer thatque forpour ''p'' &equiv; 1 (mod 4) primepremier, thereil areexiste exactlyexactement 2 solutions toà
:x = <math>\sqrt{-1} \pmod{p}</math>
 
3. SupposeSupposons ''m'' andet ''n'', des arenombres integersentiers withavec gcdpgdc(''n'',''m'') = 1. ShowMontrer thatque forpour eachchacun ofdes the numbersnombres 0, 1, 2, 3, .... , ''nm'' - 1, thereil isexiste aune uniquepaire pairunique ofde numbersnombre ''a'' andet ''b'' suchtel thatque thele smallestplus numberpetit nombre ''x'' thatqui satisfait satisfies:
:''x'' &equiv; a (mod m)
:''x'' &equiv; b (mod n)
is that number.
E.g. SupposeSupposons m = 2, n = 3, thenalors 4 isest uniquelyuniquement representedreprésenté bypar
:''x'' &equiv; 0 (mod 2)
:''x'' &equiv; 1 (mod 3)
ascomme thele smallestplus petit ''x'' thatqui satisfiessatisfait theles abovedeux twocongruences congruenciesprécédentes isest ''4''. InDans thisce case thecas, l'unique pairpaire ofde numbersnombres areest 0 andet 1.
 
4. IfSi ''p'' &equiv; 1 (mod 4) primepremier andet ''q'' &equiv; 3 (mod 4) primepremier. DoesEst-ce que
:<math>\sqrt{-1} \pmod{pq}</math>
have a une solution ? WhyPourquoi ?
 
5. IfSi ''p'' &equiv; 1 (mod 4) primepremier andet ''q'' &equiv; 1 (mod 4) primepremier andet p &ne; q. ShowMontrer thatque
:<math>x = \sqrt{-1} \pmod{pq}</math>
hasa moreplus thanque 4 solutions.
 
6. FindTrouver theles 4 solutions topour
:<math>x = \sqrt{-1} \pmod{493} </math>
notenoter thatque 493 = 17 &times;x 29.
 
7. TakePrendre anun integerentier ''n'' withavec moreplus thande 2 primefacteurs factorspremiers. ConsiderConsidérons :
:<math>x = \sqrt{-1} \pmod{n}</math>
Sous quelle conditions existe-t'il une solution ? L'expliquer.
Under what condition is there a solution? Explain thoroughly.
 
==ToPour goaller furtherplus loin==
Ce chapitre a été une introduction sympathique à la théorie des nombres, une branche des mathématiques profondément belle. Elle est sympathique dans le sens qu'elle est mathématiquement légère et somme toute un peu facile. Si vous avez apprécié la matière de ce chapitre, vous seriez aussi enchanté par le chapitre [[AL Arithmétique modulaire approfondie | Arithmétique modulaire approfondie]], qui est un traitement plus difficile et plus rigoureux du sujet..
This chapter has been a gentle introduction to number theory, a profoundly beautiful branch of mathematics. It is gentle in the sense that it is mathematically light and overall quite easy. If you enjoyed the material in this chapter, you would also enjoy [[HSE Further Modular Arithmetic | Further Modular Arithmetic]], which is a harder and more rigorous treatment of the subject..
 
==Acknowledgement==