Pages

modulo - Part 4


One of the all-time famous mathematicians is Pierre de Fermat. He is a French mathematician and lived in the 17th century.

To mention Fermat, we must mention "his problem" - the Fermat's last problem. The problem that had challenged generations of mathematicians. Probably the reason that his problem is so well-known and attracted so much effort from top mathematicians as well as young school students is that it is stated so simple and that a secondary school student can understand it.

The Fermat's last problem is stated as follows. Prove that for any $n \geq 3$ the following equation does not have non-trivial solutions  
$$ x^n+y^n=z^n $$

Non-trivial solutions here mean non-zero solutions. This is because if  $x$, $y$ or $z$ is equal to 0 then the equation becomes trivial.



Fermat was actually not a professional mathematician. He was a lawyer and he was doing math just for fun. He didn't try to publish his research. All his inventions that have become known today were from his correspondence with his friends and his occasional notes on books that he read. After he passed away, his son collected his letters and notes and published his research.


The above problem was written on the margin of a book. He wrote that he had found a beautiful proof but couldn't write it down because there wasn't enough space on the margin! Whether Fermat had a correct proof or not, no one can be sure, however, one can be sure that the problem had frustrated generations of mathematicians. It took more than 350 years for mathematicians to work out a correct proof. And that was Andrew Wiles - an English mathematician who finally solved it. In 1993, Wiles announced the proof but soon an error in his proof was discovered, and it took another year, in 1994, Wiles and his former student Richard Taylor fixed the error and thus solved the problem completely. The proof is a few hundred page long and employs some of the most powerful tools of modern mathematics. If it is to be translated to the elementary math language of Fermat's time, the proof must be a few thousand page long. So "not enough space on the margin" was indeed a valid reason! 
the margin doesn't have enough space!


You probably wonder that while Fermat's problem asserts that the equation $x^n + y^n = z^n$ does not have solutions when $n \geq 3$, so what happens in the case for $n=2$? Does the equation $x^2 + y^2 = z^2$ have a solution? The answer is, not only it has a solution but it has an infinite number of solutions as illustrated by the following equality
$$
(a^2-b^2)^2 + (2ab)^2 = (a^2+b^2)^2
$$

Fermat proved many beautiful results about prime numbers. The Fermat's "little" Theorem is one of them. It states that for any prime number $p$, and for any number $a$ not divisible by $p$, we have $a^{p-1} = 1 \pmod{p}$. We will prove this beautiful theorem in the next post. 

We know that an arbitrary number is either equal to 0, 1, 2, or 3 modulo 4. If $x = 0 \pmod{4}$ then $x$ is divisible by 4. If $x = 2 \pmod{4}$ then $x$ is an even number. So an odd prime number is either equal to 1 or 3 modulo 4. In other words, an arbitrary odd prime number is either of the form $4k+1$ or $4k+3$. Fermat proved that if a prime number of the form $p=4k+1$ then $p$ can be written as sum of two squares  $p=a^2 + b^2$. And if a prime number of the form $p=4k+3$ then we cannot find such $a,b$ so that $p=a^2 + b^2$.

Example:
  • $p = 5 = 1 \pmod{4}$   then $p = 5 = 1 + 4 = 1^2 + 2^2$
  • $p = 7 = 3 \pmod{4}$ then $p = 7 \neq a^2 + b^2$.
  • $p = 11 = 3 \pmod{4}$ then $p = 11 \neq a^2 + b^2$.
  • $p = 13 = 1 \pmod{4}$ then $p = 13 = 4 + 9 = 2^2 + 3^2$.
  • $p = 17 = 1 \pmod{4}$ then $p = 17 = 1 + 16 = 1^2 + 4^2$.
  • $p = 19 = 3 \pmod{4}$ then $p = 19 \neq a^2 + b^2$.
  • $p = 23 = 3 \pmod{4}$ then $p = 23 \neq a^2 + b^2$.
  • $p = 29 = 1 \pmod{4}$ then $p = 29 = 4 + 25 = 2^2 + 5^2$.


We will save the case $p=4k+1$ for later. Now we consider the case $p = 4k+3$. We will find out why is that when $p = 3 \pmod{4}$ then $p \neq a^2 + b^2$.

We consider $n^2 \pmod{4}$. We know that for an arbitrary number $n$, 
$$n = 0, 1, 2, 3 \pmod{4}$$
so
$$n^2 = 0^2, 1^2, 2^2, 3^2 = 0, 1, 4, 9 = 0, 1 \pmod{4}$$
Therefore, $n^2 = 0$ or $1 \pmod{4}$.

So $a^2 = 0, 1 \pmod{4}$. And also $b^2 = 0, 1 \pmod{4}$. It follows that $a^2 + b^2=0, 1, 2 \pmod{4}$. But we have $p = 3 \pmod{4}$, so $p$ cannot be the same number as $a^2 + b^2$.

We have just proved a very beautiful result that says if $p = 4k+3$ then $p \neq a^2 + b^2$. This proof only employs a simple modulo fact that, for any $n$, $n^2 = 0$ or $1 \pmod{4}$.


Remark: As mentioned in previous posts, in modulo calculation, sometimes negative numbers are quite useful. In the above example, because modulo 4 is quite small so we didn't use them. However, if we want to find out $n^2 = ? \pmod{11}$, then instead of using
$$ n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \pmod{11} $$
$$ n^2 = 0^2, 1^2, 2^2, 3^2, 4^2, 5^2, 6^2, 7^2, 8^2, 9^2, 10^2 \pmod{11} $$
if we use negative numbers as follows then we can save half of the calculations
$$ n = 0, \pm 1, \pm 2, \pm 3, \pm 4, \pm 5 \pmod{11} $$
so
$$n^2 = 0, 1, 4, 9, 16, 25 = 0, 1, 4, 9, 5, 3 \pmod{11}$$
This is because $6 = -5 \pmod{11}$, $7 = -4 \pmod{11}$, $8 = -3 \pmod{11}$, etc...


Homework: Using modulo 8 and work out when a prime number $p$ can be written as $p = a ^ 2 + 2 b ^ 2$

  • $3 = 1 + 2 = 1^2 + 2 \times 1^2$
  • $5 \neq a^2 + 2 b^2$
  • $7 \neq a^2 + 2 b^2$
  • $11 = 9 + 2 = 3^2 + 2 \times 1^2$
  • $13 \neq a^2 + 2 b^2$
  • $17 = 9 + 8 = 3^2 + 2 \times 2^2$
  • $19 = 1 + 18 = 1^2 + 2 \times 3^2$
  • $23 \neq a^2 + 2 b^2$
  • $29 \neq a^2 + 2 b^2$


See you again at "modulo - Part 5"