|
D'abord, supposons la proposition suivante :
Let us first assume that
:''thereil areexiste aun finitenombre numberfini ofde primesnombre premiers''
par conséquent
therefore
:''il doit exister un nombre premier qui est plus grand que tous les autres,''
:''there must be one prime that is greater than all others,''
appelons ce nombre premier ''n''. Nous allons maintenant montrer que les deux propositions sont contradictoires, et ainsi montrer qu'il existe une infinité de nombres premiers.
let this prime be referred to as ''n''. We now proceed to show the two assumptions made above will lead to non-sense, and so there are infinitely many primes.
TakePrenons thele productproduit ofde alltous primeles numbersnombres topremiers yieldpour aformer numberun nombre ''x''. ThusAinsi :<br/>
:<math>
x = 2 \times 3 \times 5 \times \ldots \times n
</math>
ThenAlors, letsoit ''y'' equalégal oneà moreun thanplus que ''x'' :<br/>
:<math>
y = x + 1
</math>
OneOn maypeut nowmaintenant concludeconclure thatque ''y'' isn'est notpas divisible by anypar ofaucun thedes primesnombres uppremiers toformant ''n'', sincepuisque ''y'' differsdiffère from ad'un multiple ofde eachchacun suchdes primenombres bypremiers exactlypar exactement 1. SincePuisque ''y'' isn'est notpas divisible bypar anyaucun primenombre numberpremier, ''y'' mustdoit eitherêtre besoit primeun nombre premier, orou itsses primefacteurs factorspremiers mustdoivent alltous beêtre greaterplus thangrands que ''n'', aune contradiction ofde thela originalproposition assumptionoriginale thatqui énonce que ''n'' isest thele largestplus grand nombre premier prime! ThereforePar conséquent, oneon mustpeut declaredéclarer theque originalla assumptionproposition incorrectoriginale est incorrecte, andet thatainsi, therequ'il existsexiste anune infiniteinfinité numberde ofnombres primespremiers.
====info -- PrimesNombres inpremiers arithmeticdans une progression arithmétique====
<blockquote style="padding: 1em; border: 2px dotted purple;">
ConsiderConsidérons the arithmeticla progression arithmétique
:''a'', ''a'' + ''b'', ''a'' + 2''b'', ''a'' + 3''b'' ....
ifsi ''a'' andet ''b'' sharepartagent aun facteur commoncommun factorplus greatergrand thanque 1, thenalors ''a'' + ''kb'' forpour anytout k isn'est notpas primeun nombre premier. ButMais ifsi ''a'' andet ''b'' aresont coprimespremiers entre eux, thenalors thereil areexiste infinitelyune manyinfinité de ''k'''s suchtels thatque ''a'' + ''kb'' isest premier prime!
ForPar exampleexemple, considerconsidérons a = 3, b = 4,
:3, 7, 11, 15, 19, 23, 27, 31...
indans thiscette ratherliste shortplutôt listcourte, 3, 7, 11, 19, 23 andet 31 aresont primepremiers andet theyils aresont alltous equalégaux toà 4''k'' + 3 forpour someun certain ''k''. AndEt thereil areexiste infinitelyune manyinfinité primesde innombres thispremiers dans cette progression (seevoir : proofExercices bysur contradictionla exercisedémonstration par l'absurde [[HSE_Mathematical_proofs|AL_Démonstrations Mathematicalmathématique| ProofsDémonstrations]]).
</blockquote>
==Modular Arithmetic==
===Introduction===
Modular arithmetic connects with primes in a cool sort of way. Let's start with modulo 7 arithmetic, it's just like ordinary arithmetic except the only numbers we can use are 0, 1, 2, 3, 4, 5 and 6. If we see a number outside of this range we add 7 to (or subtract 7 from) it, until it lies within that range.
'''Examples'''
:<math>
\begin{matrix}
3 + 2 = 5 \\
\\
5 + 6 = 11 = 4\\
\\
5 - 6 = -1 = 6\\
\end{matrix}
</math>
The same deal for multiplication
:<math>
\begin{matrix}
3 \times 5 = 15 = 1\\
5 \times -6 = -30 = 5\\
\end{matrix}
</math>
'''Note - Negatives''': The preferred representation of -3 is 4, as -3 + 7 = 4.
====Exercise====
Find in modulo 11
1.
:-1 × -5
2.
:3 × 7
3.
:2<sup>1</sup>
:2<sup>2</sup>
:2<sup>3</sup>
:2<sup>4</sup>
:2<sup>5</sup>
:2<sup>6</sup>
:2<sup>7</sup>
:2<sup>8</sup>
:2<sup>9</sup>
:2<sup>10</sup>
What do you notice? Using the powers of 2 find
:6<sup>1</sup>
:6<sup>2</sup>
:6<sup>3</sup>
:6<sup>4</sup>
:6<sup>5</sup>
:6<sup>6</sup>
:6<sup>7</sup>
:6<sup>8</sup>
:6<sup>9</sup>
:6<sup>10</sup>
What do you notice again?
4.
:<math>\sqrt{4} </math>
i.e. find all number x mod 11 such that x<sup>2</sup> = 4. There are two solutions, find both.
5.
:<math>\sqrt{-2} </math>
i.e. find all number x mod 11 such that x<sup>2</sup> = -2. There are two solutions, find both.
===Division and Inverses===
Staying in modulo 7, let's consider how division is done:
what is
:<math>\frac{1}{5}</math>?
Algebra is still very reliable in this slightly different setting:
:<math>
\begin{matrix}
x &=& \frac{1}{5}\\
5\times x &=& 1
\end{matrix}
</math>
we are looking for a number ''x'', such that ''x'' × 5 = 1 modulo 7. ''x'' = 3 is one solution.
'''Example'''
:<math>
\begin{matrix}
x &=& \frac{3}{5}\\
&=& 3\times \frac{1}{5}\\
&=& 3\times 3\\
&=& 2
\end{matrix}
</math>
It is interesting to note that when we do ''division'' we are really looking for a number that when multiplied by the denominator will give 1. Actually, the correct way to say what we are doing is finding ''multiplicative inverses''. But no harm will come to us if we just think of it as division. Consider the following example:
:<math>\frac{6}{2} \ \ \mbox{(mod 7)}</math>
If we treat it as ''division'', we get 3. Or we can do it the ''find inverse'' way.
:<math>\frac{6}{2} = 6 \cdot 4 = 24 = 3 \pmod{7}</math>
we still get the same answer. Interesting!
It is also interesting to note that division doesn't always work. Consider:
:<math>\frac{14}{7} \ \ \mbox{(mod 28)}</math>
By the division method, the answer is 2. But 7 doesn't have an inverse mod 28. So we can't say 14/7 = 2. This is a major problem with division in mod ''n'' arithmetic, it works when in some case but fails completely in others. It is safer to not refer to it as division. From now on, we will use ''x<sup>-1</sup>'' to denote the inverse of ''x'' if it exists. The above problem becomes:
:<math>14 \cdot 7^{-1} \ \ \mbox{(mod 28)}</math>
which is has no solution as 7<sup>-1</sup> does not exist.
Note 0 does not have an inverse (''Why do you think this must be?'') and it is only too clear that the inverse of 1 is 1, but does 1 have another inverse? You'll probably say 'no' after some thought. In fact, in any reasonable number system, a number can have one and only one multiplicative inverse. Here is the proof:
<blockquote style="padding: 1em; border: 2px dotted purple;">
Suppose ''a'' has inverses ''b'' and ''c''
:<math>
b = b \times 1 = b (ac) = (ba)c = 1 \times c = c
</math>
From the above argument, all inverses of ''a'' must be equal. As a result, if the number ''a'' has an inverse, it must have only one inverse.
</blockquote>
Another interesting property of any modulo ''n'' arithmetic is that the number ''n-1'' has itself as an inverse. That is, (n-1) × (n-1) = 1 (mod ''n''). The proof is left as an exercise at the end of the section.
====Existence of inverse====
It may have seem curious to you that we have only considered modular prime arithmetic so far; there is a reason for that. And we shall see that reason now.
Let's consider modulo 15 arithmetic and note that 15 is composite. We know that the inverse of 1 is 1 and of 14 is 14. But what about 3, 6, 9, 12, 5 and 10? None of them has an inverse! And note that each of them shares a common factor with 15!
Maybe you are still not convinced that it's true and it's good to be suspectful when learning mathematics. But cast away your doubt, as the proof is just ahead.
Let's consider 3. Suppose 3 has an inverse, which is denoted by x.
:<math>
3x = 1 \ \mbox{(mod 15)}
</math>
The tricky bit is to make the ''jump'' from modular arithemetic back into rational number arithmetic. If 3x = 1 in modulo 15 arithmetic, then
:<math>
3x = 15k + 1
</math>
for some ''k'' in rational number arithmetic.
:<math>
\begin{matrix}
3x &=& 15k + 1 \\
x &= & 5k + \frac{1}{3}\\
\end{matrix}
</math>
But this is wrong, because we know that ''x'' is an integer. Therefore 3 doesn't have an inverse in mod 15 arithmetic. To show that 10 doesn't have an inverse is harder and is left as an exercise.
We will state the theorem regarding the existence of inverses in modular arithmetic without its proof, as the proof is difficult.
'''Theorem'''
:If ''n'' is prime then every number (except 0) has an inverse in modulo ''n'' arithmetic.
Similarly
:If ''n'' is composite then every number that doesn't share a common factor with ''n'' has an inverse.
====Exercise====
1. Find x mod 7 if x exists:
:<math>x = 2^{-1}</math>
:<math>x = 3^{-1}</math>
:<math>x = 4^{-1}</math>
:<math>x = 5^{-1}</math>
:<math>x = 6^{-1}</math>
:<math>x = 7^{-1}</math>
2. Calculate x in two ways: "division" and "find inverse".
:<math>x = 28\cdot 7^{-1} \ \ \mbox{(mod 29)}</math>
3. Find x
:<math>x = 5^{99} \times (40 + 3^{-1}) \ \pmod{11}</math>
4.
Find all inverses mod n (n ≤ 19)<br/>
''This exercise may seem tedious, but it will increase your understand of the topic by tenfold''
===Coprime and greatest common divisor===
Two numbers are said to be coprimes if their greatest common divisor is 1. The greatest common divisor (gcd) is just what its name says it is. And there is a quick and elegant way to compute the gcd of two numbers, called Euclid's algorithm. Let's illustrate with a few examples:
'''Example 1:'''<br/>
:Find the gcd of 21 and 49.
We set up a 2-column table where the bigger of the two numbers is on the right hand side as follows
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th>
</tr>
<tr>
<td>21</td> <td>49</td>
</tr>
</table>
We now compute 49(mod 21) which is 7 and put it in the second row ''smaller'' column, and put 21 into the ''larger'' column.
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th>
</tr>
<tr>
<td>21</td> <td>49</td>
</tr>
<tr>
<td>7</td> <td>21</td>
</tr>
</table>
Perform the same action on the second row to produce the third row.
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th>
</tr>
<tr>
<td>21</td> <td>49</td>
</tr>
<tr>
<td>7</td> <td>21</td>
</tr>
<tr>
<td>0</td> <td>'''7'''</td>
</tr>
</table>
Whenever we see the number 0 appear on the ''smaller'' column, we know the corresponding ''larger'' number is the the gcd of the two numbers we started with, i.e. 7 is the gcd of 21 and 49. This ''algorithm'' is called Euclid's algorithm.
'''Example 2'''
:Find the gcd of 31 and 101
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th>
</tr>
<tr>
<td>31</td> <td>101</td>
</tr>
<tr>
<td>8</td> <td>31</td>
</tr>
<tr>
<td>7</td> <td>8</td>
</tr>
<tr>
<td>1</td> <td>7</td>
</tr>
<tr>
<td>0</td> <td>'''1'''</td>
</tr>
</table>
'''Example 3'''
:Find the gcd of 132 and 200
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th>
</tr>
<tr>
<td>132</td> <td>200</td>
</tr>
<tr>
<td>68</td> <td>132</td>
</tr>
<tr>
<td>64</td> <td>68</td>
</tr>
<tr>
<td>4</td> <td>64</td>
</tr>
<tr>
<td>0</td> <td>'''4'''</td>
</tr>
</table>
'''Remember'''
# The gcd need not be a prime number.
# The gcd of two primes is 1
You may not know why the algorithm works, but it seems to work. You may not be able to resist asking, "Why does it work?". To put it in the words of Arnold Ross, "It is for the questioner to discover, not for me to tell."
====personality -- Arnold Ross====
<blockquote style="padding: 1em; border: 2px dotted purple;">
Arnold Ross is a well respected educator and number theorist who is most famous for his mathematics summer school program for talented high school students in the USA and Australia.<br/>
* http://www.ams.org/notices/200107/fea-ross.pdf
</blockquote>
====Exercise====
1. Determine whether the following sets of numbers are coprimes
:# 5050 5051
:# 59 78
:# 111 369
:# 2021 4032
2. Find the gcd of the numbers 15, 510 and 375
====info -- Algorithm====
<blockquote style="padding: 1em; border: 2px dotted purple;">
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>
===Diophantine equation===
Let's look at the idea of inverse again, but from a different angle. Let's consider:<br/>
:5''x'' = 1 (mod 7)<br/>
We know ''x'' is the inverse of 5 and we can work out it's 3 pretty quickly. But x = 10 is also a solution, so is x = 17, 24, 31, ... 7n + 3. So there are infinitely many solutions; therefore we say 3 is equivalent to 10, 17, 24, 31 and so on. This is a crucial observation
Now let's consider<br/>
:<math>216x \equiv 1 \ \ \mbox{(mod 811)}</math>
A new notation is introduced here, it is the equal sign with three strokes instead of two. It is the "equivalent" sign; the above statement should read "216''x'' is EQUIVALENT to 1" instead of "216''x'' is EQUAL to 1". From now on, we will use the equivalent sign for modulo arithmetic and the equal sign for ordinary arithmetic.
Back to the example, we know that ''x'' exists, as gcd(811,216) = 1. The problem with the above question is that there is no quick way to decide the value of ''x''! The best way we know is to multiply 216 by 1, 2, 3, 4... until we get the answer, there are at most 816 calculations, way too tedious for humans. But there is a better way, and we have touched on it quite a few times!
We notice that we could make the ''jump'' just like before into rational mathematics:
:<math>
\begin{matrix}
216a & = & 1 + 811b\\
0 & \equiv & 1 + 163b &\pmod{216}\\
\end{matrix}
</math>
We jump into rational maths again
:<math>
\begin{matrix}
216c &=& 1 + 163b \\
53c &\equiv& 1 &\pmod{163}\\
\end{matrix}
</math>
We jump once more
:<math>
\begin{matrix}
53c &=& 1 + 163d \\
0 &\equiv& 1 + 4d&\pmod{53}\\
\end{matrix}
</math>
Now the pattern is clear, we shall start from the beginning so that the process is not broken:
:<math>
\begin{matrix}
216a & = & 1 + 811b\\
216c &=& 1 + 163b \\
53c &=& 1 + 163d \\
53e &=& 1 + 4d \\
e &=& 1 + 4f \\
\end{matrix}
</math>
Now all we have to do is choose a value for ''f'' and substitute it back to find ''a''! Remember ''a'' is the inverse of 216 mod 811. We choose f = 0, therefore e = 1, d = 13, c = 40, b = 53 and finally a = 199! If choose ''f'' to be 1 we will get a different value for ''a''.
The very perceptive reader should have noticed that this is just Euclid's gcd algorithm in reverse.
Here are a few more examples of this ingenious method in action:
'''Example 1'''
Find the smallest positive value of ''a'':
:<math>
\begin{matrix}
33a & \equiv & 1 \ \ \mbox{(mod 101)}\\
33a &=& 1 + 101b\\
33c &=& 1 + 2b\\
c &=& 1 + 2d\\
\end{matrix}
</math>
Choose d = 0, therefore a = 49.
'''Example 2'''
Find the smallest positive value of ''a'':
:<math>
\begin{matrix}
27a & \equiv & 1 \ \ \mbox{(mod 821)}\\
27a &=& 1 + 821b\\
27c &=& 1 + 11b\\
5c &=& 1 + 11d\\
5e &=& 1 + d\\
\end{matrix}
</math>
Choose e = 0, therefore a = -152 = 669
'''Example 3'''
Find the smallest positive value of ''a'':
:<math>
\begin{matrix}
34a & \equiv & 1 \ \ \mbox{(mod 55)}\\
34a &=& 1 + 55b\\
34c &=& 1+ 21b\\
13c& =& 1 + 21d\\
13e& =& 1 + 8d\\
5e &=& 1 + 8f\\
5g& = &1 + 3f\\
2g& =& 1 + 3h\\
2i& = &1 + h\\
\end{matrix}
</math>
Set i = 0, then a = -21 = 34. ''Why is this so slow for two numbers that are so small? What can you say about the coefficients?''
'''Example 4'''
Find the smallest positive value of ''a'':
:<math>
\begin{matrix}
21a & \equiv & 1 \ \ \mbox{(mod 102)}\\
21a &=& 1 + 102b\\
21c &=& 1 + 18b\\
3c &=& 1 + 18d\\
3d &=& 1\\
\end{matrix}
</math>
Now ''d'' is not an integerr, therefore 21 does not have an inverse mod 102.
What we have discussed so far is the method of finding integer solutions to equations of the form:
:ax + by = 1
where ''x'' and ''y'' are the unknowns and ''a'' and ''b'' are two given constants, these equations are called linear ''Diophantine equations''. It is interesting to note that sometimes there is no solution, but if a solution exists, it implies that infinitely many solutions exist.
====*Alternate explanation*====
The example was to find ''a'' given:
:216''a'' = 1 (mod 811)
Let's apply the Euclid's algorithm on the two numbers, but we should store more details; more specifically, we want to set up an additional column called PQ which stands for partial quotient. The partial quotient is just a technical term for "how many ''n'' goes into ''m''" e.g. The partial quotient of 3 and 19 is 6, the partial quotient of 4 and 21 is 5 and one last example the partial quotient of 7 and 49 is 7.
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th> <th>PQ</th>
</tr>
<tr>
<td>216</td> <td>811</td> <th>3</th>
</tr>
<tr>
<td>163</td> <td></td> <th></th>
</tr>
</table>
The tables says three 211s goes into 811 with remainder 163, or symbollically:
:811 = 3×216 + 163.
Let's continue:
<table border="1" cellpadding="2">
<tr>
<th>smaller</th> <th>larger</th> <th>PQ</th>
</tr>
<tr>
<td>216</td> <td>811</td> <th>3</th>
</tr>
<tr>
<td>163</td> <td>216</td> <th>1</th>
</tr>
<tr>
<td>53</td> <td>163</td> <th>3</th>
</tr>
<tr>
<td>4</td> <td>53</td> <th>13</th>
</tr>
<tr>
<td>1</td> <td>4</td> <th>4</th>
</tr>
<tr>
<td>0</td> <td>1</td> <th></th>
</tr>
</table>
Now we set up the so-called "magic table" which looks like this initially
<table border="1" cellpadding="2">
<tr>
<td></td> <td></td>
</tr>
<tr>
<td>0</th> <td>1</td>
</tr>
<tr>
<td>1</th> <td>0</td>
</tr>
</table>
Now we write the partial quotient on the first row:
<table border="1" cellpadding="2">
<tr>
<td></td> <td></td> <th>3</th> <th>1</th> <th>3</th> <th>13</th> <th>4</th>
</tr>
<tr>
<td>0</th> <td>1</td>
</tr>
<tr>
<td>1</th> <td>0</td>
</tr>
</table>
We produce the table according to the following rule:
:Multiply a partial quotient one space to the left of it in a different row, add the product to the number two space to the left on the same row and put the sum in the corresponding row.
It sounds more complicated then it should. Let's illustrate by producing a column:
<table border="1" cellpadding="2">
<tr>
<td></td> <td></td> <th>3</th> <th>1</th> <th>3</th> <th>13</th> <th>4</th>
</tr>
<tr>
<td>0</th> <td>1</td> <td>3</td>
</tr>
<tr>
<td>1</th> <td>0</td> <td>1</td>
</tr>
</table>
We put a 3 in the second row because 3 = 3×1 + 0. We put a 1 in the third row because 1 = 3×0 + 1.
We shall produce the whole table without disruption:
<table border="1" cellpadding="2">
<tr>
<td></td> <td></td> <th>3</th> <th>1</th> <th>3</th> <th>13</th> <th>4</th>
</tr>
<tr>
<td>0</th> <td>1</td> <td>3</td> <td>4</td> <td>15</td> <td>199</td> <td>811</td>
</tr>
<tr>
<td>1</th> <td>0</td> <td>1</td><td>1</td><td>4</td><td>53</td><td>216</td>
</tr>
</table>
I claim
:|199×216 - 811×53| = 1
In fact, if you have done the magic table properly and ''cross multiplied and subtracted'' the last two column correctly, then you will always get 1 or -1, provided the two numbers you started with are coprimes. The magic table is just a cleaner way of doing the mathematics. A ''messy'' way to do the same thing would be to do the following:
:811 = 3×216 + 163
:216 = 1×163 + 53
:163 = 3×53 + 4
:53 = 13×4 + 1
Now that we can work out the inverse of 216 by working the results backwards
:1 = 53 - 13×4
:1 = 53 - 13×(163 - 3×53)
:1 = 40×53 - 13×163
:1 = 40×(216 - 163) - 13×163
:1 = 40×216 - 53×163
:1 = 40×216 - 53×(811 - 3×216)
:1 = 199×216 - 53×811
Now look at the equation mod 811, we will see the inverse of 216 is 199.
====Exercise====
1.
Find the smallest positive ''x'':
:216x = 1 (mod 816)
2.
Find the smallest positive ''x'':
:42x = 7 (mod 217)
3.
'''(a)''' Produce the magic table for 33a = 1 (mod 101)<br/>
'''(b)''' Evaluate and express in the form p/q
:<math>
3 + {1 \over 16 + {1\over 2}}
</math>
What do yo notice?
4.
'''(a)''' Produce the magic table for 17a = 1 (mod 317)<br/>
'''(b)''' Evaluate and express in the form p/q
:<math>
18 + {1 \over 1 + {1\over {1 + {1\over 1 + {1\over 5}}}}}
</math>
What do yo notice?
===Chinese remainder theorem===
The Chinese remainder theorem is known in China as ''Han Xing Dian Bing'', which in its most naive translation means ''Han Xing counts his soldiers''. The original problem goes like this:
:There exists a number ''x'', when divided by 3 leaves remainder 2, when divided by 5 leaves remainder 3 and when divided by 7 leaves remaider 2. Find the smallest ''x''.
We tranlate the question into symbolic form:
:<math>
\begin{matrix}
x&\equiv &2 \pmod{3}\\
x&\equiv &3 \pmod{5}\\
x&\equiv &2 \pmod{7}\\
\end{matrix}
</math>
How do we go about finding such a ''x''? We shall use a familar method and it is best illustrated by example:
Looking at x = 2 (mod 3), we make the ''jump'' into ordinary mathematics
:<math>
\begin{matrix}
x&\equiv &2 \pmod{3}\\
x &=& 2 + 3a \qquad (1)
\end{matrix}
</math>
Now we look at the equation modulo 5
:<math>
\begin{matrix}
2 + 3a &\equiv& 3 \pmod{5}\\
3a &\equiv& 1 \pmod{5}\\
a &\equiv& 2 \pmod{5}\\
a &=& 2 + 5b
\end{matrix}
</math>
Substitute into (1) to get (2)
:<math>
x = 2 + 3(2 + 5b) \qquad (2)
</math>
:<math>
x = 8 + 15b \equiv 2 \pmod{7}
</math>
:<math>
b \equiv 1 \pmod{7}
</math>
We choose b = 1 to minimise x, therefore x = 23. And a simple check (to be performed by the reader) should confirm that x = 23 is a solution. A good question to ask is what is the next smallest ''x'' that satisfies the three congruencies? The answer is x = 128, and the next ''x'' is 233 and the next ''x'' is 338, and they differ by 105, the product of 3, 5 and 7.
We will illustrate the method of solving a system of congruencies further by the following examples:
'''Example 1'''
Find the smallest ''x'' that satifies:
:<math> x \equiv 1 \pmod{3} </math>
:<math> x \equiv 2 \pmod{5} </math>
:<math> x \equiv 3 \pmod{7} </math>
'''Solution'''
:<math>
\begin{matrix}
x &=& 1 + 3a &\equiv& 2 \pmod{5}\\
& & a &=& 2 + 5b\\
x &=& 1 + 3(2 + 5b) &\equiv& 3 \pmod{7}\\
&=& 7 + 15b &\equiv& 3 \pmod{7}\\
&& b &\equiv& 3 \pmod{7}\\
&& b &= &3 + 7c\\
x &=& 7 + 15(3 + 7c)\\
x &=& 52 + 15\times 7c
\end{matrix}
</math>
Therefore 52 is the smallest ''x'' that satifies the congruencies.
'''Example 2'''
Find the smallest ''x'' that satifies:
:<math> x \equiv 5 \pmod{11} </math>
:<math> x \equiv 3 \pmod{7} </math>
:<math> x \equiv 8 \pmod{9} </math>
''' Solution '''
:<math>
\begin{matrix}
x &=& 5 + 11a &\equiv& 3 \pmod{7}\\
& & a &\equiv& 3 \pmod{7} \\
& & a &=& 3 + 7b \\
x &=& 5 + 11(3 + 7b)\\
x &=& 38 + 11\times 7b &\equiv & 8\pmod{9}\\
& & 2 + 2\times 7b &\equiv &8 \pmod{9}\\
& & b &\equiv &3 \pmod{9}\\
& & b &= &3 + 9c\\
x &=& 38 + 11\times 7(3 + 9c)\\
&=& 269 + 11\times 7\times 9c
\end{matrix}
</math>
Therefore 269 is the smallest ''x'' that satifies the congruencies.
==== Excercises ====
1.
Solve for ''x''
:<math>
\begin{matrix}
3x &\equiv & 5 \pmod{14} \\
2x &\equiv & -3 \pmod{17} \\
x &\equiv &6 \pmod{15} \\
\end{matrix}
</math>
2.
Solve for ''x''
:<math>
\begin{matrix}
3x &\equiv & 5 \pmod{19} \\
7x &\equiv & -3 \pmod{17} \\
x &\equiv &6 \pmod{11} \\
\end{matrix}
</math>
==== Existence of a solution ====
The exercises above all have a solution. So does there exist a system of congruencies such that no solution could be found? It certainly is possible, consider:
:x ≡ 5 (mod 15)
:x ≡ 10 (mod 21)
a cheekier example is:
:x ≡ 1 (mod 2)
:x ≡ 0 (mod 2)
but we won't consider silly examples like that.
Back to the first example, we can try solve it by doing:
:<math>
\begin{matrix}
x & = & 5 + 15k & \equiv & 10 & \pmod{21} \\
& & 15k & \equiv & 5 & \\
& & 3k & \equiv & 1 & \\
\end{matrix}
</math>
the above equation has no solution because 3 does not have an inverse modulo 21!
You may be quick to conclude that if two modulo systems share a common factor then there is no solution. But this is not true! Consider:
:x ≡ 4 (mod 15)
:x ≡ 7 (mod 21)
:<math>
\begin{matrix}
x & = & 4 + 15k & \equiv & 7 & \pmod{21} \\
& & 15k & \equiv & 3 & \\
& & 17 \times 15k & \equiv & 17 \times 3 & \\
& & 3k & \equiv & 9 & \\
\end{matrix}
</math>
obviously, a solution exists, namely k = 3, and the two modulo systems are the same as the first example (i.e. 15 and 21).
So what determines whether a system of congruencies has a solution or not? Let's consider the general case:
:x ≡ a (mod m)
:x ≡ b (mod n)
we have
:x = a + km
:x = b + ln
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)
now suppose m and n have gcd(m,n) = d, and m = dm<sub>o</sub>, n = dn<sub>o</sub>. We have
:dln<sub>o</sub> - dkm<sub>o</sub> = (a - b)
:ln<sub>o</sub> - km<sub>o</sub> = (a - b)/d
now read the equation mod k<sub>o</sub>, we have:
:l<sub>o</sub>n ≡ (a - b)/d (mod k<sub>o</sub>)
note that the above only makes sense if (a - b)/d is integeral. Also if (a - b)/d is an integer, then there is a solution, as k<sub>o</sub> and l<sub>o</sub> are coprimes!
In summary: for a system of two congruent equations
:x ≡ a (mod m)
:x ≡ b (mod n)
there is a solution if and only if
:gcd(m,n) divides (a - b)
And the above generalises well into more than 2 congruencies. For a system of ''n'' congruencies:
:x ≡ a<sub>1</sub> (mod m<sub>1</sub>)
:x ≡ a<sub>2</sub> (mod m<sub>2</sub>)
:...
:x ≡ a<sub>n</sub> (mod m<sub>n</sub>)
, for a solution to exist, we require for any i and j with i ≠ j
:gcd(m<sub>i</sub>,m<sub>j</sub>) divides (a<sub>i</sub> - a<sub>j</sub>)
==== Exercises ====
Decide whether a solution exists for each of the congruencies. Explain why.
1.
:x ≡ 7 (mod 25)
:x ≡ 22 (mod 45)
2.
:x ≡ 7 (mod 23)
:x ≡ 3 (mod 11)
:x ≡ 3 (mod 13)
3.
:x ≡ 7 (mod 25)
:x ≡ 22 (mod 45)
:x ≡ 7 (mod 11)
4.
:x ≡ 4 (mod 28)
:x ≡ 28 (mod 52)
:x ≡ 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 ≤ a, b and c ≤ 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'' ≡ 1 (mod 4)
== Project -- The Square Root of -1 ==
1. Question 10 of the problem set showed that
:<math>\sqrt{-1} \equiv \sqrt{p-1} \pmod{p}</math>
exists for ''p'' ≡ 1 (mod 4) prime. Explain why no square root of -1 exist if ''p'' ≡ 3 (mod 4) prime.
2. Show that for ''p'' ≡ 1 (mod 4) prime, there are exactly 2 solutions to
:x = <math>\sqrt{-1} \pmod{p}</math>
3. Suppose ''m'' and ''n'' are integers with gcd(''n'',''m'') = 1. Show that for each of the numbers 0, 1, 2, 3, .... , ''nm'' - 1 there is a unique pair of numbers ''a'' and ''b'' such that the smallest number ''x'' that satisfies:
:''x'' ≡ a (mod m)
:''x'' ≡ b (mod n)
is that number.
E.g. Suppose m = 2, n = 3, then 4 is uniquely represented by
:''x'' ≡ 0 (mod 2)
:''x'' ≡ 1 (mod 3)
as the smallest ''x'' that satisfies the above two congruencies is ''4''. In this case the unique pair of numbers are 0 and 1.
4. If ''p'' ≡ 1 (mod 4) prime and ''q'' ≡ 3 (mod 4) prime. Does
:<math>\sqrt{-1} \pmod{pq}</math>
have a solution? Why?
5. If ''p'' ≡ 1 (mod 4) prime and ''q'' ≡ 1 (mod 4) prime and p ≠ q. Show that
:<math>x = \sqrt{-1} \pmod{pq}</math>
has more than 4 solutions.
6. Find the 4 solutions to
:<math>x = \sqrt{-1} \pmod{493} </math>
note that 493 = 17 × 29.
7. Take an integer ''n'' with more than 2 prime factors. Consider:
:<math>x = \sqrt{-1} \pmod{n}</math>
Under what condition is there a solution? Explain thoroughly.
==To go further==
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==
''Acknowledgement: This chapter of the textbook owes much of its inspiration to Terry Gagen, Associate Professor of Mathematics at the University of Sydney, and his lecture notes on "Number Theory and Algebra". Terry is a much loved figure among his students and is renowned for his entertaining style of teaching.''
| 