1) Gauss’s Modular Arithmetic
Given a positive integer \(m \), we say that two integers \( a\) and \(b \) are congruent modulo \(m\) if they give the same remainder when divided by \(m \). We use the following notation introduced by the German mathematician Gauss:
\[ a \equiv b \pmod{m} \]For example \( 21 \equiv 3 \pmod {9}, \quad 100 \equiv 1 \pmod {33} \) .
Theorem 1.1
Let \(m\) be a non-negative integer \(m \in \mathbb{Z} \). Then for every \(a \in \mathbb{Z}\), there is a single non-negative integer \(r\) such that
This theorem is a consequence of the Division Algorithm for integers, which states that given any two integers \(a \) and \(b\), with \(b>0 \) we can find integers \(q\) and \(r\) such that \(0 \le r <b\) and \( a=bq+r \).
It can easily be shown that the congruence relation is an equivalence relation (symmetric, reflexive and transitive) and therefore induces a partition of the set of integers \(\mathbb{Z}\) into \(m\) distinct equivalence classes. A complete system of residues \( \pmod {m} \) is a set of \(m \) distinct numbers, each taken from one of the \(m\) equivalence classes. The standard representation for the congruence classes modulo \(m\) is formed by taking the elements of the set \(\{0,1,2, . . . , m-1\}\).
For example if \(m=3 \) we have \(3 \) equivalence classes, indicated with square brackets:
[0] which contains the integers {-6,-3,0,3,6,9,…}
[1] which contains the integers {-8,-5,-2,1,4,7,10,…}
[2] which contains the integers {-7,-4,-1,2,5,8,11,…}
The sum and product operations between two classes are defined in a natural way. The set of integers modulo \(m \) with the sum and product operations is indicated with the symbol \( \mathbb{Z}/(m) \).
Theorem 1.2
If \( a \equiv b \pmod{m} \) and \( c \equiv d \pmod {m} \), then:
Theorem 1.3
If \( (k,m)=1 \), then
An important area of number theory is the study of congruence equations, i.e. equations of the type \( f(x) \equiv b \pmod{m} \). Solutions are considered distinct only if they belong to different equivalence classes. The simplest case is constituted by the linear equations, i.e. equations of the type: \( ax \equiv b \pmod{m} \). This congruence equation is equivalent to the arithmetic equation \( ax-my=b \), which is solvable in integers if and only if \( d=(a,m)|b \). This property is expressed in the following theorem.
Theorem 1.4
If \( (a,m)=d \), then the equation
admits solutions if and only if \( d|b \) .
As for the number of solutions, we have the following theorem:
Theorem 1.5
The linear equation \( ax \equiv b \pmod {m} \), with \(d=(a,m)|b \), has exactly \(d \) distinct solutions \( \pmod {m} \). In fact if \(x_{0}\) is a solution, so are the following
In particular, the solution is unique if \( d=(a, m)=1\). The inverse of an integer \(a\) \( \pmod {m} \) is defined as an integer \( b \) such that \(a · b \equiv 1 \pmod {m} \). We use the notation \(a^{-1}\) or \([a]^{-1}\) to indicate the inverse of \(a \pmod {m}\). From the theorem, it follows that an inverse of \( a \pmod {m} \) exists if and only if \((a,m)=1\).
Example 1.1
Consider the equation \( 3x \equiv 18 \pmod {21} \). We have \( d=(3,21)=3\) and \( 3|18\). So there are \(3\) distinct solutions. A solution that we can easily find is \(x_{0}=6\): the other two are \(x_{1}= 6 + \frac{21}{3}=13\) and \(x_{2}= 6 + \frac {2 \cdot 21}{3}=20\).
1.1) Simple applications
1.1.1) Caesar cipher
Caesar cipher is a simple cryptography scheme, used by Julius Caesar to communicate with his generals. The scheme consists in shifting each letter of the plaintext message \( n \) positions to the right. For example if \(n=4\) we have the following scheme, assuming to use the English alphabet of \(26\) letters:
\[ A \rightarrow E; B \rightarrow F; \cdots Z \rightarrow D \]For example the word ROMA is encoded with the VSQE string. If we associate each letter of the alphabet with a number from 0 to 25, Caesar cipher is equivalent to adding \( \pmod{26} \) the number associated with each letter and the secret key \(n \). For the decryption operation it is sufficient to perform the subtraction \( \pmod {26} \).
Of course it is an inefficient cipher. The Vigenere method is a more complex variant of the Caesar cipher; instead of always moving the letter to be encrypted with the same number of places, we move by a variable number of places, determined on the basis of a keyword, making it more difficult to decipher the code.
1.1.2) Divisibility criteria
Another application of modular arithmetic is the proof of the criteria of divisibility by an integer.
Example (criterion of divisibility by \(3\))
As it is known, the criterion says that an integer is divisible by three if and only if the sum of the digits is a number divisible by \(3\). Now, because \(10 \equiv 1 \pmod {3}\), multiplying both members we have:
Given the decimal expansion of \( n \):
\[ n=c_{k}\cdot 10^{k} + c_{k-1} \cdot 10^{k-1} \cdots +c_{1} \cdot 10 + c_{0}; \quad 0 \le c_{i} \le 9 \]we can replace all powers \( 10^k \) with \(1\) getting:
\[ n \equiv (c_{k} + c_{k-1} \cdots +c_{1} + c_{0}) \pmod {3} \]In the same way we can obtain the divisibility criteria by \( 7, 9, 11 \).
2) Fermat’s Little Theorem
Fermat’s theorem states that if \(p\) is a prime number and \(a\) is an integer, then:
\[ a^{p} \equiv a \pmod{p} \]It’s a special case of Euler’s theorem, which we will study in one of next articles. It has important applications in various areas of number theory, in particular to check if an integer is prime, and also in public-key cryptography. An equivalent formulation is the following: if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then:
\[ a^{p-1} \equiv 1 \pmod{p} \]In reality Fermat didn’t give a proof. The theorem was already known also by Gottfried Wilhelm Leibniz (1646-1716). The first proof of the theorem was published by Euler in 1736. Several proofs of Fermat’s theorem can be given.
2.1) Proof with Newton’s binomial formula
Let’s recall some definitions. The binomial coefficient \(\binom{n}{k}\), where \(n,k\) are positive integers, represents the number of simple combinations of \(n\) items taken \(k\) at a time; or equivalently, it’s the number of subsets of order \(k\) that can be built with the \(n\) objects. We also define \(\binom{n}{0} = 1\). The following formulas can be easily proved:
\[ \begin{array}{l} \displaystyle \binom{n+1}{k+1} =\binom{n}{k} +\binom{n}{k+1} \\ \displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!} \\ \end{array} \]If \(p\) is a prime number, from the previous formula derives that
\[ p | \binom{p}{k} \quad 0 \lt k \lt p; \]The following Newton’s binomial formula generalizes the binomial and trinomials special products that are taught in elementary schools:
\[ (x+y)^n = \sum_{k=0}^n {n \choose k} x^{n – k} y^k \]From Newton’s binomial theorem we derive the following formula, useful for proving Fermat’s theorem:
\[ (x+y)^p \equiv x^p +y^p \pmod{p} \]At this point we have all the tools to prove Fermat’s theorem.
We must prove that \(a^{p} \equiv a \pmod{p} \), with \( p\) prime number. We proceed by induction on the number \(a\). If \(a=1\) the statement is true. Suppose now that it is true for a generic positive integer \(a \ge 1\) and we show that it is also true for \(a+1\). We apply the binomial theorem:
Since \(p\) divides all the terms of the second member, excluding the first and the last, we can write the following congruence: \((a+1)^p \equiv a^p + 1 \pmod{p}\). By the inductive hypothesis we have \( (a+1)^p \equiv a+1 \pmod{p} \), as we wanted to prove.
2.2) Second proof
A permutation on a set of \( n \) elements, which we can indicate with \(\{1, 2, . . . , n\} \) or with letters \(\{a,b,c,…\} \), is a one-to-one correspondence with itself. Precisely it is a function that associates another element to each element of the set (possibly the element itself) so that two different elements are never associated with the same element. Permutations can be represented explicitly using a two-line matrix; for example a permutation on the set \( \{1,2,3,4,5,6\}\) it’s the following:
\[ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 5 & 6 & 1 & 4 \\ \end{pmatrix} \]An important type of permutation is the cycle, which moves some elements cyclically and keeps the others fixed. For example:
\[ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 5 & 1 \\ \end{pmatrix} \]A cycle can also be represented with a single line, in which each index is associated with the next one and the last is associated with the first: for example \( \{1,2,4,5\}\).
It can be shown that any permutation can be uniquely represented as a composition of disjoint cycles.
For example, the above permutation is equivalent to the composition of the following cycles: \( \{1,2,3,5\}\{4,6\} \). A permutation is called cyclic if it can be represented with a single cycle.
The following theorem is useful for the proof of Fermat’s little theorem.
Theorem 2.1
Let \(s\) be an arbitrary string of length \( p\) symbols, not necessarily all distinct, where \( p\) is a prime number. If the string \(s\) contains at least two different symbols, then the cyclic permutations of \( s\) are all distinct.
For example, given the string of numbers \( 23411\quad(p=5)\), its cyclical permutations are \(\{34112, 41123, 11234, 12341\}\). Instead, in the case of the string \(2323 \quad(p=4)\), we have \(\{3232, 2323, 3232\}\) which are not distinct, as they contain equal concatenated substrings. Clearly this is not possible if the length is a prime number.
We say two strings are equivalent if each can be obtained from the other through a cyclic permutation.
At this point we can prove Fermat’s theorem. Let’s take a set of \(n\) symbols and we form all possible strings of length \(p\), with repetitions. The total number of strings is equal to \(n^p\). Removing the strings with the same symbol, there remain \(n^p – n\) strings. Each of these strings has length \(p\) and therefore has \(p\) distinct cyclic permutations. The set of \(n^p – n\) strings can then be divided into a finite number of string classes; each class contains a group of \(p\) equivalent permutations. This implies that
where \(k\) is the number of classes, therefore the theorem is proved.
2.3) Proof with Burnside’s theorem
To introduce Burnside’s theorem it is useful to remember the definition of an algebraic group. A group consists of a set G on which a binary operation \(\bullet : G \times G \rightarrow G\) is defined, such that the following properties are satisfied:
1) \( a,b \in G \implies a\bullet b \in G \)
2) \(a,b,c \in G \implies a\bullet (b \bullet c) = (a \bullet b) \bullet c \)
3) \(\exists e \in G\) such that \(a \bullet e = e \bullet a = a \quad \forall a \in G \)
4) \(\forall a \in G \quad \exists b \in G\) such that \( a\bullet b = b \bullet a = e\)
A subset \(H\) of \(G\) is called a subgroup if it satisfies all the above properties with the same binary operation. An example of a group is the set of integers \(\mathbb{Z}\) with the sum operation. The neutral element is represented by the number \(0\) .
The symmetric group: we indicate with \(S_{n}\) the group of all permutations on the set \(X =\{1,2,…,n\}\) . The group binary operation consists of the composition of two permutations. \(S_{n}\) is called the symmetric group of the \(n\) elements, and the cardinality of the group is \(|S_{n}| = n! \) . For example
Given a permutation \( \sigma \in S_{n}, i \in \mathbb{N}\), we define the permutation \( \sigma ^i \ge 0 \), obtained by composing the \(\sigma\) with itself \(i\) times; then the set \( \{\sigma ^i| i\ge 0\}\) is the subgroup generated by the permutation \(\sigma\) and is indicated with \(<\sigma>\).
Let us remember the concept of symmetry. A symmetry on an object is an operation that transforms an object leaving its appearance unaltered.
As it can be seen from the previous diagram, the square has \(8\) symmetries, \(4\) rotations and \(4\) reflections. In general a regular polygon of \(n\) sides has \(2n\) symmetries.
Let now \( C\) be a set of colors. We define a coloring as a function \( f\colon X \to C \) which assigns to each element of the set \( X=\{1,2,…n\} \) a color. Two colorings \(C_{1}\) and \(C_{2}\) are called equivalent if there exists a symmetry \(\pi\) defined on the permutation group such that \( \pi (C_{1}) = C_{2} \). This relation is an equivalence relation and therefore the set of colorings is subdivided into a finite number of classes. The problem is how to determine the different colorings. For each permutation \(\pi\) we indicate with \(\Psi (\pi) \) the number of colorings that remain unchanged with \(\pi\).
Theorem 2.2 – Burnside’s theorem
Let G be a finite group of permutations of the finite set \(X\). Let \(Y\) be a closed set of colorings with respect to \(G\). Then the number of equivalence classes is:
where \( \Psi (\pi) = \{ y \in Y \; | \; \pi(y)=y \} \).
For a proof see for example [1].
To prove Fermat’s theorem we suppose that \( G\) is the cyclic group generated by the permutation \( (1,2,..p)\). The permutations in a cyclic group can also be interpreted as rotations of the vertices of a regular polygon of \(p\) sides. Suppose we have n colors, and \(|G|=p\), where \(p\) is a prime number. For each permutation \(\pi\) we have to compute \(\Psi(\pi)\). For the permutation identity, which leaves the elements unchanged, we have that the number of unchanged colorings is \(n^{p}\). For each of the other \(p-1\) permutations only the colorings with a single color remain unchanged, since \(p\) is a prime number, therefore \((p-1) \cdot n\).
Ultimately, for Burnside’s theorem, we have:
\[ \frac{1}{|G|} \sum_{\pi \in G} | \Psi(\pi)| = \frac{1}{p}(n^p + \underbrace{n+n + … + n}_{p-1 \;\text{times}}) \]The final expression represents the number of distinct colorings and must be a positive integer. Then \( n^p + (p-1)n \) must be divisible by \(p\). Simplifying we have:
\[ n^p+(p-1)n \equiv 0 \pmod{p} \Rightarrow n^p-n\equiv 0 \pmod{p} \]and Fermat’s theorem is proved.
3) Pseudoprimes
A composite integer \(n \ge 2\) is called pseudoprime with respect to the base \(b\) if
\[ b^{n-1} \equiv 1 \pmod{n} \]The smallest pseudoprime \(n\) with base \( 2\) is \(341=11 \cdot 31\). In fact it turns out that \(2^{340} \equiv 1 \pmod {341}\).
It can be shown that for every base \(b\) there are infinite pseudoprimes with respect to the base itself. The composite positive integers \(m\) that are pseudoprimes with respect to each base relatively prime with \(m\) are called Carmichael numbers. Carmichael’s smallest number is
For a more in-depth study of the topics of this article you can read the following texts: [2], [3], [4].
4) Some exercises to solve
1) Prove that \( 2^{35} + 1\) is divisible by \(11\).
We observe first that:
\[ 2^{7} \equiv 7 \pmod{11} \implies 2^{35} \equiv 7^{2}\cdot 7^{2}\cdot 7 \pmod{11} \]Then
\[ 2^{35} \equiv 5 \cdot 5 \cdot 7 \pmod{11} \]and therefore
\[ 2^{35} \equiv 3 \cdot 7 \pmod{11} \implies 2^{35} \equiv 10 \pmod {11} \]Adding \(+1\) we finally get: \(2^{35}+1 \equiv 0 \pmod{11}\).
2) Prove the following formula:
\[ x^{p-1} – 1 \equiv (x-1)(x-2) \cdots (x-(p-1)) \pmod{p} \]Apply Fermat’s theorem for all the values of a complete residue system, for example \(\{0,1, \cdots p-1 \}\).
3) Prove that \(341 | 20^{15}-1\).
Prove that each of the prime factors of \(341\) divides the number to the right.
4) Find the remainder of \(605^{13} \div 7 \).
We observe that \( 605 \equiv 3 \pmod{7} \). Then \(605^{13} \equiv 3^{13} \pmod{7}\). So we have:
\[ 3^{13} = 3^{4} \cdot 3^{4} \cdot 3^{4} \cdot 3 \equiv 4 \cdot 4 \cdot 4 \cdot 3 \pmod{7} \implies 3^{13} \equiv 2 \cdot 5 \equiv 3 \pmod {7} \\ \]5) Compute \( 2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60} + 7^{70} \pmod{7} \).
We observe that \(2^6 \equiv 1 \pmod{7} \) and therefore \(2^{20} = 2^{6} \cdot 2^{6} \cdot 2^{6} \cdot 2^{2} \equiv 4 \pmod{7} \). Proceed in the same way with the other powers. Finally we have:
\[2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60} + 7^{70} \equiv 4 + 1+4+4+1+0 = 14 \equiv 0 \pmod{7} \\ \]6) Show that if p it’s a prime number, then
\[ 1^{n-1} + 2^{p-1} +…. +(p-1)^{p-1} + 1 \equiv 0 \pmod{p} \]Apply Fermat’s Theorem to each element.
7) Show that for every positive integer \(n\) the number
\[ 3(1^{5}+2^{5}+ \cdots + n^{5}) \]is divisible by the number
\[ 1^{3}+2^{3}+ \cdots +n^{3} \]First prove by mathematical induction the formulas for the sums of the third powers and of the fifth powers.
8) Prove that \(2^{70}+3^{70} \equiv 0 \pmod{13}\)
Begin with \(2^{12} \equiv 1 \pmod{13}\) and \(3^{3} \equiv 1 \pmod {13}\).
Bibliography
[1]Tucker – Applied Combinatorics (Wiley)
[2]Niven, Zuckerman, Montgomery – An introduction to the Theory of Numbers, V edition (Wiley, 1991).
[3]Erdos, Suranyi – Topics in the Theory of Numbers (Springer)
[4]Hardy, Wright – An Introduction to the Theory of Numbers (Oxford University Press)
0 Comments