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

Fin de la traduction de l'article anglais
Aucun résumé des modifications
(Fin de la traduction de l'article anglais)
:x ≡ 5 (mod 15)
:x ≡ 10 (mod 21)
Un exemple plus gros est :
a cheekier example is:
:x ≡ 1 (mod 2)
:x ≡ 0 (mod 2)
\end{matrix}
</math>
évidemment, une solution existe, explicitement k = 3, et les deux systèmes modulo sont le même comme pour le premier exemple (i.e. 15 andet 21).
 
Donc, qu'est-ce qui détermine si un système de congruences possède une solution ou pas ? Considérons le cas général :
So what determines whether a system of congruencies has a solution or not? Let's consider the general case:
:x &equiv; a (mod m)
:x &equiv; b (mod n)
Nous avons
we have
:x = a + km
:x = b + ln
essentiellement, le problème nous demande de trouver k et l tels que les deux équations précédentes soient satisfaites. Nous effectuons :
essentially, the problem asks us to find k and l such that the above equations are satisfied. We proceed:
:0 = (a - b) + (km - ln)
:(ln - km) = (a - b)
nowMaintenant supposesupposons que m andet n haveont gcdpgdc(m,n) = d, andet m = dm<sub>o</sub>, n = dn<sub>o</sub>. WeNous haveavons
:dln<sub>o</sub> - dkm<sub>o</sub> = (a - b)
:ln<sub>o</sub> - km<sub>o</sub> = (a - b)/d
nowmaintenant readlire the equationl'équation mod k<sub>o</sub>, wenous avons have:
:l<sub>o</sub>n &equiv; (a - b)/d (mod k<sub>o</sub>)
notenoter thatque thece abovequ'il onlyy makesa ci-dessus n'a de sens senseseulement ifsi (a - b)/d isest integeralentier. AlsoAussi ifsi (a - b)/d isest anun integerentier, thenalors thereil isexiste aune solution, ascomme k<sub>o</sub> andet l<sub>o</sub> aresont premiers entre eux coprimes!
 
En résumé : pour un systeme de deux équations congruentes
In summary: for a system of two congruent equations
:x &equiv; a (mod m)
:x &equiv; b (mod n)
thereil isexiste aune solution ifsi andet onlyseulement ifsi
:gcdpgdc(m,n) dividesdivise (a - b)
 
Et ce qui suit généralise le cas à plus de deux congruences. Pour un système de ''n'' congruences :
And the above generalises well into more than 2 congruencies. For a system of ''n'' congruencies:
:x &equiv; a<sub>1</sub> (mod m<sub>1</sub>)
:x &equiv; a<sub>2</sub> (mod m<sub>2</sub>)
:...
:x &equiv; a<sub>n</sub> (mod m<sub>n</sub>)
, forpour aqu'une solution to existexiste, weil requirefaut forpour anytout i andet j withavec i &ne; j
:gcdpgdc(m<sub>i</sub>,m<sub>j</sub>) dividesdivise (a<sub>i</sub> - a<sub>j</sub>)
 
==== ExercisesExercices ====
DecideDécider whethersi aune solution existsexiste forpour eachchacune ofdes the congruenciescongruences. ExplainExpliquer whypourquoi.
 
1.
:x &equiv; 28 (mod 52)
:x &equiv; 24 (mod 32)
 
== Problem Set ==
1. Show that the divisible-by-3 theorem works for any 3 digits numbers (Hint: Express a 3 digit number as 100a + 10b + c, where 0 &le; a, b and c &le; 9)
 
2. "A number is divisible by 9 if and only if the sum of its digits is divisible by 9." True or false? Determine whether 89, 558, 51858, and 41857 are divisible by 9. Check your answers.
 
3. Is there a rule to determine whether a 3-digit number is divisible by 11? If yes, derive that rule.
 
4.
:<math>
\begin{matrix}
X & 2 & 3 & X & 5 &X &7& X& X& X \\
11 & X & 13 & X& X& X&17 &X& 19& X\\
X& X& 23 & X& X &X&X&X&29& X\\
31 &X& X& X& X &X&37& X& X& X\\
41 & X& 43 & X& X&X&47& X& 49& X\\
\end{matrix}
</math>
The prime sieve has been applied to the table above. Notice that every number situated directly below 2 and 5 are crossed out. Construct a rectangular grid of numbers running from 1 to 60 so that after the prime sieve has been performed on it, all numbers situated directly below 3 and 5 are crossed out. What is the width of the grid?
 
5. Show that ''p'', ''p + 2'' and ''p + 4'' cannot all be primes. (''p'' a positive integer)
 
6. Show that n - 1 has itself as an inverse modulo ''n''.
 
7. Show that 10 does not have an inverse modulo 15.
 
8. Find x
:<math>
\begin{matrix}
x \equiv 3^7 + 1^7 + 2^7 + + 4^7 + 5^7 + 6^7 + 7^7 \ \pmod{7}\\
\end{matrix}
</math>
 
9. Show that there are no integers x and y such that
:<math>
x^2 - 5y^2 = 3
</math>
 
10.
Let ''p'' be a prime number. Show that
 
'''(a)'''
:<math>
(p-1)! \equiv -1\ \mbox{(mod p)}
</math>
where
:<math>
n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n
</math>
E.g. 3! = 1*2*3 = 6
 
'''(b)'''
 
Hence, show that
:<math>\sqrt{-1} \equiv \frac{p - 1}{2}! \pmod{p}</math>
for ''p'' &equiv; 1 (mod 4)
 
== Projet -- La racine carrée de -1 ==
1. La question 10 de l'ensemble des problèmes a montré que
:<math>\sqrt{-1} \equiv \sqrt{p-1} \pmod{p}</math>
existe pour ''p'' &equiv; 1 (mod 4) premier. Expliquer pourquoi aucune racine carrée de -1 n'existe si ''p'' &equiv; 3 (mod 4) est premier.
 
2. Montrer que pour ''p'' &equiv; 1 (mod 4) premier, il existe exactement 2 solutions à
:x = <math>\sqrt{-1} \pmod{p}</math>
 
3. Supposons ''m'' et ''n'', des nombres entiers avec pgdc(''n'',''m'') = 1. Montrer que pour chacun des nombres 0, 1, 2, 3, .... , ''nm'' - 1, il existe une paire unique de nombre ''a'' et ''b'' tel que le plus petit nombre ''x'' qui satisfait :
:''x'' &equiv; a (mod m)
:''x'' &equiv; b (mod n)
is that number.
E.g. Supposons m = 2, n = 3, alors 4 est uniquement représenté par
:''x'' &equiv; 0 (mod 2)
:''x'' &equiv; 1 (mod 3)
comme le plus petit ''x'' qui satisfait les deux congruences précédentes est ''4''. Dans ce cas, l'unique paire de nombres est 0 et 1.
 
4. Si ''p'' &equiv; 1 (mod 4) premier et ''q'' &equiv; 3 (mod 4) premier. Est-ce que
:<math>\sqrt{-1} \pmod{pq}</math>
a une solution ? Pourquoi ?
 
5. Si ''p'' &equiv; 1 (mod 4) premier et ''q'' &equiv; 1 (mod 4) premier et p &ne; q. Montrer que
:<math>x = \sqrt{-1} \pmod{pq}</math>
a plus que 4 solutions.
 
6. Trouver les 4 solutions pour
:<math>x = \sqrt{-1} \pmod{493} </math>
noter que 493 = 17 x 29.
 
7. Prendre un entier ''n'' avec plus de 2 facteurs premiers. Considérons :
:<math>x = \sqrt{-1} \pmod{n}</math>
Sous quelle conditions existe-t'il une solution ? L'expliquer.
 
==Pour aller plus 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..
 
==AcknowledgementReconnaissance==
''AcknowledgementReconnaissance : ThisCe chapterchapitre ofdoit thebeaucoup textbookde owes much of itsson inspiration toà Terry Gagen, AssociateProfesseur Professorassocié ofde MathematicsMathématiques atà thel'Université University ofde Sydney, andet hisà lectureses notes onde lecture de "Number Theory and Algebra". Terry isest aun muchpersonnage lovedtrès figureapprécié amongparmi hisses students andétudiants iset renownedest forrenommé hispour entertainingson style ofd'apprentissage teachingentrainant.''
358

modifications