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

Contenu supprimé Contenu ajouté
Aucun résumé des modifications
Ligne 7 :
:<math>
\begin{matrix}
3 + 2 \equiv= 5 \mod{7}\\
\\
5 + 6 \equiv= 11 \equiv= 4 \mod{7}\\
\\
5 - 6 \equiv= - 1 \equiv= 6 \mod{7}\\
\end{matrix}
</math>
Ligne 18 :
:<math>
\begin{matrix}
3 \times 5 \equiv= 15 \equiv= 1 \mod{7}\\
\\
5 \times - 6 \equiv= - 30 \equiv= 5 \mod{7}\\
\end{matrix}
</math>
Ligne 281 :
====Info -- Algorithme====
<blockquote style="padding: 1em; border: 2px dotted purple;">
Un algorithme est une description pas à pas d'une série d'actions qui faites correctement peuvent accomplir une tâche. Il existe des algorithmes pour trouver des nombres premiers, décider si 2 nombres sont premiers entre eux, trouver des inverses et beaucoup d'autres usages.<br/> Vous apprendrez comment implémenter certains de ces algorithmes que nous avons vus en utilisant un ordinateur deans le chapitre [[AL Programmation mathématique|Programmation mathématique]].
An algorithm is a step-by-step description of a series of actions when performed correctly can accomplish a task. There are algorithms for finding primes, deciding whether 2 numbers are coprimes, finding inverses and many other purposes.<br/> You'll learn how to implement some of the algorithms we have seen using a computer in the chapter [[HSE Mathematical programming|Mathematical Programming]].
</blockquote>
 
===DiophantineEquations equationdiophantiennes===
Jetons de nouveau un coup d'oeil à l'idée d'inverse, mais à partir d'un angle différent. Considérons :<br/>
Let's look at the idea of inverse again, but from a different angle. Let's consider:<br/>
:5''x''<math>5x = 1 (mod 7)\,</math><br/>
WeNous knowsavons que ''x'' is theest l'inverse ofde 5 andet wenous canpouvons worktrouver outque itc'sest 3 pretty quicklyrapidement. ButMais x = 10 isest alsoaussi aune solution, so isdonc x = 17, 24, 31, ... 7n + 3. SoAinsi, thereil areexiste infinitelyune manyinfinité de solutions; thereforepar weconséquent, saynous disons que 3 isest equivalentéquivalent toà 10, 17, 24, 31 andet soainsi onde suite. ThisC'est is a crucialune observation cruciale.
 
Maintenant, considérons<br/>
Now let's consider<br/>
:<math>216x \equiv 1 \ \ \mbox{(mod {811)}</math>
AUne newnouvelle notation isest introducedintroduite hereici, itc'est isle thesigne equalégal signavec withtrois threetraits strokesau insteadlieu ofde twodeux. ItC'est isle thesigne "equivalentéquivalent" sign; thele aboverésultat statementci-dessus shoulddevrait readêtre lu "216''x'' isest EQUIVALENT toà 1" insteadà ofla place de "216''x'' isest EQUALEGAL toà 1". FromA partir nowde onmaintenant, wenous willutiliserons usele thesigne equivalentéquivalent signpour forl'arithmétique modulomodulaire arithmeticet andle thesigne equalégal signour for ordinaryl'arithmétique arithmeticordinaire.
 
BackPour torevenir theà examplel'exemple, wenous knowsavons thatque ''x'' existsexiste, ascomme gcdPGDC(811,216) = 1. TheLe problemproblème withavec the abovela question isci-dessus thatest therequ'il isn'existe nopas quickde waymanière torapide decidede thedécider valuela ofvaleur de ''x'' ! TheLa bestmeilleure wayméthode weque knownous isconnaissons toest multiplyde multiplier 216 bypar 1, 2, 3, 4... untiljusqu'à ce que wenous getobtenions thela answerréponse, thereil areexiste atau mostplus 816 calculationscalculs, waymanière tootrop tediousfastidieuse forpour humansles humains. ButMais thereil isexiste aune bettermeilleure waymanière, andet wenous have touched on itl'avons quiteapprochée aquelques fewfois times!
 
Nous notons que nous pouvions faire le ''saut'' juste avant vers les mathématiques rationnelles :
We notice that we could make the ''jump'' just like before into rational mathematics:
:<math>
\begin{matrix}
Ligne 302 :
\end{matrix}
</math>
Nous sautons vers les mathématiques rationnelles de nouveau
We jump into rational maths again
 
:<math>
Ligne 310 :
\end{matrix}
</math>
Nous sautons une fois encore
We jump once more
:<math>
\begin{matrix}
Ligne 318 :
</math>
 
Maintenant, le motif est clair, nous démarrerons à partir du début ainsi le processus ne sera pas interrompu :
Now the pattern is clear, we shall start from the beginning so that the process is not broken:
:<math>
\begin{matrix}
Ligne 329 :
</math>
 
NowMaintenant, alltout wece haveque tonous doavons isà choosefaire aest de choisir une valuevaleur forpour ''f'' andet substitutela itsubstituer backen toretour findpour trouver ''a'' ! RememberSouvenez-vous que ''a'' is theest l'inverse ofde 216 mod 811. WeNous choosechoisissons f = 0, thereforepar conséquent e = 1, d = 13, c = 40, b = 53 andet finallyfinalement a = 199 ! IfSi choosenous choisissons 1 pour ''f'', tonous beobtiendrons 1 we will get aune differentvaleur valuedifférente forpour ''a''.
 
Un lecteur très perspicace aura noté que ceci est l'algorithme d'Euclide à l'envers.
The very perceptive reader should have noticed that this is just Euclid's gcd algorithm in reverse.
 
Voici quelques exemples de plus de cette méthode ingénieuse en action :
Here are a few more examples of this ingenious method in action:
 
'''ExampleExemple 1'''
 
FindTrouver thela smallestplus positivepetite valuevaleur ofpositive de ''a'' :
:<math>
\begin{matrix}
Ligne 346 :
\end{matrix}
</math>
ChooseChoisissons d = 0, thereforepar conséquent a = 49.
 
'''ExampleExemple 2'''
FindTrouver thela smallestplus positivepetite valuevaleur ofpositive de ''a'' :
:<math>
\begin{matrix}
Ligne 359 :
\end{matrix}
</math>
ChooseChoisissons e = 0, thereforepar conséquent a = -152 = 669
 
'''ExampleExemple 3'''
FindTrouver thela smallestplus positivepetite valuevaleur ofpositive de ''a'' :
:<math>
\begin{matrix}
Ligne 376 :
\end{matrix}
</math>
SetFixons i = 0, thenalors a = -21 = 34. ''WhyPourquoi isest-ce thisqi solent slowpour fordeux twonombres numbersd'être thatsi arepetit so small? WhatQue canpouvez-vous youdire saysur about theles coefficients ?''
 
'''ExampleExemple 4'''
FindTrouver thela smallestplus positivepetite valuevaleur ofpositive de ''a'' :
:<math>
\begin{matrix}
Ligne 389 :
\end{matrix}
</math>
NowMaintenant ''d'' isn'est notpas anun integerrnombre entier, thereforepar conséquent 21 doesn'a not have anpas d'inverse mod 102.
 
Ce que nous avons exposé si longuement est la méthode pour trouver des solutions entières aux équations de la forme :
What we have discussed so far is the method of finding integer solutions to equations of the form:
:ax + by = 1
where ''x'' andet ''y'' aresont theinconnus unknowns andet ''a'' andet ''b'' aresont twodeux givenconstantes constantsdonnées, theseces equationséquations aresont called linearappelées ''Diophantineéquations equationsdiophantiennes'' linéaires. ItIl isest interestingintéressant tode notenoter thatque sometimesquelquefois thereil isn'existe nopas de solution, butmais ifsi aune solution existsexiste, itcela impliesimplique thatqu'il infinitelyen manyexiste solutionsune existinfinité.
 
====*AlternateExplication explanationalternative*====
TheL'exemple exampleétait wasde to findtrouver ''a'' givendonné :
:216''a'' = 1 (mod 811)