\chapter{Modular arithmetic} \section{Introduction to modular arithmetic} Numbers with the same remainder when divided by $n$ form an equivalence class; Modular arithmetic is basically a convenient notation for arithmetic on these $n$ equivalence classes. \begin{definition}[Congruence] \[ a \equiv b \mod n \iff n | a-b \] The number $n$ is called the \emph{modulus}; multiples of $n$ are congruent to 0. \end{definition} \subsection{Basic laws} Equivalence relation \[ a \equiv a \mod m \] \[ a \equiv b \mod m \implies b \equiv a \mod m\] \[ a \equiv b \mod m \land b \equiv c \mod m \implies a \equiv c \mod m\] Since congruences form equivalence relations, one can write residues by means of the set containing all numbers with the same residue $\mod n$. This is a neat notational shortcut. \[ [a]_n = \{ a+kn : k \in \mathbb{Z} \} \] \[ a \equiv b \mod n \iff [a]_n = [b]_n \] \[ \mathbb{Z} = \cup^{n}_{i=0} [i]_n\] \[j \notin [i]_n \iff [i]_n \cap [j]_n = \emptyset\] Essentially, these equivalence classes partition $\mathbb{Z}$ (equivalence classes don't overlap, and every integer must belong to some equivalence class). We'll describe the set of all these equivalence classes by writing $\mathbb{Z} / n\mathbb{Z}$. This will represent all the elements in our new 'modular algebrae'; addition and multiplication of mod $n$ equivalence classes. \[ \mathbb{Z} / n \mathbb{Z} = \{ [a]_n : a \in \mathbb{Z} \}\] We now check that addition and multiplication are well defined on this equivalence relation (consider equivalence classes $[a]_n,[b]_n$, there exists a $[c]_n$ such that any $x \in [a]_n,y \in [b]_n$ obeys $x+y \in [c]_n$). \[ a \equiv b \mod n \land x \equiv y \mod n \implies a+x \equiv b+y \mod n \] \[ a \equiv b \mod n \land x \equiv y \mod n \implies ax \equiv by \mod n \] Here are some obvious corollaries that follow, however they are included to accustomize the reader's intuition to the behaviour of modular arithmetic. \[\forall k \in \mathbb{Z} [ a \equiv b \mod n \implies a+k \equiv b+k \mod n ] \] \[\forall k \in \mathbb{Z} [ a \equiv b \mod n \implies ak \equiv bk \mod n ] \] \[\forall k \in \mathbb{N} \setminus \{0\} [ a \equiv b \mod n \implies a^k \equiv b^k \mod n ] \] Cancellation laws \[\forall n \in \mathbb{N}\setminus\{0\} [ an \equiv bn \mod nm \implies a \equiv b \mod m ] \] \[\forall n \in \mathbb{N} [ \mathrm{gcd}(n,m)=1 \land an \equiv bn \mod m \implies a \equiv b \mod m ] \] \[\gcd(a,n)=1 \land ax \equiv ay \mod n \implies x \equiv y \mod n\] \[ p \text{is prime} \implies ax \equiv l\] \section{Divisibility tests} A nice use for conguence is an efficient notation for understanding and proving divisibility tests. -digital sum -digital root \begin{definition} \[ n = \sum^{k}_{i=0} 10^i d_i\] \[ \mathrm{ds}(n) = \sum_{i=0}^{k} d_i\] \end{definition} \[ 2|n \iff 2|(n \mod 10) \] \[ 5|n \iff 5|(n \mod 10) \] \[ 10|n \iff n \equiv 0 \mod 10) \] \[ 4|n \iff 4|(n \mod 100) \] \[ 2^k|n \iff 2^k|(n \mod 10^k) \] \[ 5^k|n \iff 5^k|(n \mod 10^k) \] \[ 3|n \iff 3|\mathrm{dr}(n) \] \[ 9|n \iff 9|\mathrm{dr}(n) \] \[ 7|(10n+r) \iff 7|(n-2r) \] 11 13 -binary squaring \subsection{Modular multiplicative inverse} \begin{definition} Let $a,n \in \mathbb{Z}$, the \emph{$n$-modular multiplicative inverse of $a$ ($n$-MMI of $a$)} is some element $x$ satisfying the following. \[ax \equiv 1 \mod n\] \end{definition} \begin{proposition} Let $a$ have an $n$-MMI $x$, then all its other $n$-MMIs are congruent to $x$ mod $n$. \end{proposition} This essentially says that $n$-MMI are unique when disregarding its congruent copies. Another basis thing to note is that being an $n$-MMI is a reciprocal relationship; if $x$is the $n$-MMI of $a$, then $a$ is the $n$-MMI of $x$. This immediately implies that within $[0,n) \cap \mathbb{N}$ no numbers share the same $n$-MMI. Numbers can have themselves as their own $n$-MMI, in fact there are some general cases where this is known to occur \begin{proposition} 1 is its own $n$-MMI. $n-1$ is its own $n$-MMI. \end{proposition} The proof? $1^2 \equiv 1 \mod n$ The proof? $(n-1)^2=n(n-2)+1 \equiv 1 \mod n$ Perhaps the most important observation is the following; after playing around a bit, it becomes clear that not every element has a ($3x \equiv 1 \mod 6$ has no integer solutions). Let's work backwards from an $n$-MMI to see what conditions are needed to ensure its existence. \[ax \equiv 1 \mod n\] \[\iff ax + 1 = ny\] \[ax -ny = -1\] \[-ax +ny = 1\] Since $x$ is an integer, it may be transformed as $x \mapsto -x$ without changing the existence of solutions (merely changing its sign). \[ax +ny = 1\] Our previous theory on Bézout's lemma comes in clutch here, if $\mathrm{gcd}(a,n)=1$ then Bézout's lemma asserts that the equation $ax+ny=1$ has integer solutions and hence an $n$-MMI for $a$. What's more however is thatonly when $\mathrm{gcd}(a,n)=1$ is satisfied does $a$ have an $n$-MMI \begin{proposition} \[ \exists x,y \in \mathbb{Z} [ ax+by = d ] \iff \exists n \in \mathbb{Z} [ d=n\mathrm{gcd}(a,b) ] \] \end{proposition} \section{Euler's theorem} One may recall that our definitions for our 'modular algebrae' allows for addition and multiplication of equivalence classes to be well defined, but exponentiation definitely isn't; we can't reduce exponents to theie equivalence class in these algebrae. That said, exponentiation inerpreted as repeated multiplication rather than its own operator allows us to talk about it in a limited setting (we've already proved one proposition relating to 'exponentiation'). There's also some group theory that can be used to give a deeper understanding of what is occuring, but we'll take an apporach that is accessible to those uninitiated in the wizardry of group theory. Perhaps the most interesting phenomenon of repeated multiplication om modular algebrae are Fermat's little theorem and its generalization Euler's theorem. \subsection{Fermat's little theorem} \begin{theorem}[Fermat's little theorem] \[p \text{ is prime} \implies a^{p-1} \equiv 1 \mod p \] \end{theorem} However there is a stronger version of the theorem. It requires the understanding of a \emph{totient function}. \subsection{Euler's totient function} \begin{definition} \emph{Euler's totient function} $\varphi : \mathbb{N}\setminus \{0\} \to \mathbb{N}\setminus \{0\}$ \[ \varphi (n) = |\{ m \in \mathbb{Z}\cap[1,n) [ \gcd(n,m)=1 ] \}| \] \end{definition} Much can be said about Euler's totient function; the bulk of these results will be left for a chapter on \emph{arithmetic functions}. We will however note one proposition that will be required to compare Fermat's version to Euler's. \begin{proposition} \[ \varphi (p) = p-1 \] \end{proposition} \subsection{Euler's theorem} \begin{theorem}[Euler's theorem] \[ \gcd(a,n)=1 \implies a^{\varphi (n)} \equiv 1 \mod n \] \end{theorem} Notice that Euler's theorem reduces to Fermat's little theorem when $n$ is prime. The underlying 'reason' for why Euler's theorem holds is not necessarily a numeric reason, but rather an algebraic one; studying group theory provides the tools to make this theorem almost trivial! \subsection{Primitive roots} Exponentiating an integer $a$ coprime to the modulus by $\varphi(n)$ is a sure way to obtain an integer congruent to $1$, however is t \begin{definition} A \emph{primitive root modulo $n$} is an integer $a$ with $\mathrm{gcd}(a,n)=1$ such that $\varphi(n)$ is the smallest exponent such that $a^{\varphi(n) \equiv 1 \mod n}$ holds. \end{definition} \begin{proposition} $a$ with $\mathrm{gcd}(a,n)=1$ is a primitive root modulo $n$ iff for any prime $p$ dividing $\varphi(n)$, $a^{\frac{\varphi(n)}{p}} \not\equiv 1 \mod n$. \end{proposition} Honestly, a group theoretic approach is ideal for this study, however we can easily emulate the same ideas in an elementary setting. We have an observation which allows us to enumerate the amount of primitive roots without even knowing them \begin{proposition} If there exists a primitive root modulo $m$, there are $\varphi(\varphi(n))$ of them. \end{proposition} The idea is that if $r$ is a primitive root, then any $r^{k}$ where $k$ doesn't divide $\varphi(n)$ is a primitive root; this gives us a way of constructing $\varphi ( \varphi (n))$ primitive roots. (From the group theoretic point of view, this is really asking for the amount of generators of $(\mathbb{Z} /n\mathbb{Z})^{*}$). \begin{proposition} There exists a primitive root modulo $n$ iff $n$ is 1,2,4 or a prime power $p^k$. \end{proposition} (Again with group theory, this is really asking when $(\mathbb{Z} /n\mathbb{Z})^{*}$ is a cyclic group). \subsection{Discrete logarithms} The theory of primitive roots, Fermat's little theorem and Euler's theorem proves powerful in studying discrete logarithms. \begin{definition} The \emph{discrete logarithm $\log_b (a)$ modulo $m$} is any integer $k$ solving the following. \[ a^k \equiv b \mod n \] \end{definition} If a modulus admits a primitive root and we can find this primitive root, discrete logarithms become linear congruences! Let $r$ be a primitive root, then we have $r^i \in [b]_n , r^{j} \in [a]_n$ our problem is as follows. \[ r^{jk} \equiv r^{i} \mod n \] Since, we want to find the $k$ satifying the following. \[ jk \equiv i \mod \varphi(n) \] \section{Chinese remainder theorem} \begin{theorem}[Chinese remainder theorem] Consider the following set of $k$ simultaneous equations where the $n_i$ are pairwise coprime with eachother. \[ \begin{cases} a_1 x \equiv r_1 \mod n_1 \\ \vdots \\ a_k x \equiv r_k \mod n_k \end{cases} \] There exists a unique solution for $x$ in $\mathbb{Z} / N\mathbb{Z}$, where $N=\prod^{k}_{i=1}n_i$. \end{theorem} By FTA, one can therefore break any modulo $n$ problem into a sequence of modulo $p_{i}^{k_{i}}$ problems The true power of the CRT is realizing that the problem of $k$ congruences of coprime moduli is equivalent to some problem modulo $\prod^{k}_{i=1}n_i$. CRT asserts the uniqueness and existence of such a solution, however we can indeed form a constructive method to swap between the two. Let $N=\prod^{k}_{i=1}n_i$, then if for $k$ congruences $f(x) \equiv s_i \mod n_i$ (where the $n_i$ are pairwise coprime) \[f(x) \equiv \sum^{k}_{i=1} \frac{N}{n_i}r_i \mod N\] \begin{theorem} Consider the following set of $k$ simultaneous equations where the $n_i$ are pairwise coprime with eachother. \[ \begin{cases} f(x) \equiv 0 \mod n_1 \\ \vdots \\ f(x) \equiv 0 \mod n_k \end{cases} \] If equation $i$ has $S_i$ solutions, then $f(x) \equiv 0 \mod N$ has $\prod^{k}_{i=1}S_i$ solutions for $x$ in $\mathbb{Z} / N\mathbb{Z}$, where $N=\prod^{k}_{i=1}n_i$. \end{theorem} \section{Quadratic residues} \subsection{Modular quadratics} - quadratic residue \begin{definition}[Quadratic residue] $q$ is called a \emph{quadratic residue modulo $n$} iff it is congruent to a square number mod $n$. \[ q \text{ is a quadratic residue modulo } n \iff \exists x \in \mathbb{Z} /n\mathbb{Z} [ x^2 \equiv q \mod n ] \] \end{definition} It is useful to play around with quadratics mod $n$ and wee what basic properties hold. \[ x^2 \equiv (n-x)^2 \mod n \] The study of quadratic residues is simplified greatly when we considering the case where we have a prime modulus. When considering prime moduli, we use the Legendre symbol. \begin{definition}[Legendre symbol] Let $p$ be an odd prime, then the \emph{legendre symbol} $\left( \frac{a}{p} \right)$ is defined as such. \[ \left( \frac{a}{p} \right) = \begin{cases} 1 & a \text{ is a quadratic residue modulo }$p$ \\ -1 & a \text{ is a quadratic nonresidue modulo }$p$ \\ 0 & a \equiv 0 \mod p \end{cases} \] \end{definition} We note some properties. \[ \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p}\right) \] \[ \left( \frac{a}{p} \right) = \left( \frac{a+kp}{p} \right) \] \[ \left( \frac{a}{p} \right) = \left( \frac{a^{-1}}{p} \right) \] A crucial property of quadratic residues is the following. \begin{theorem} Let $p$ be prime, then there are exactly $\frac{p-1}{2}$ unique quadratic residues in $\mathbb{Z} / p\mathbb{Z}$. \end{theorem} Here's fancy way to say the same thing with our new notation. \begin{corollary} \[ \sum^{p-1}_{i=1}\left( \frac{i}{p} \right) = 0\] \end{corollary} To prove this we require Lagrange's theorem. \subsection{Lagrange's theorem} There is a theorem due to Lagrange which proves extremely useful whenever we consider polynomials modulo some prime. Recall the idea that when $p$ is prime $ax \equiv b \mod p$ has a unique solution in $\mathbb{Z} / p\mathbb{Z}$; Lagrange's theorem generalizes this proposition from linear functions topolynomials of any degree on $\mathbb{Z} /p\mathbb{Z}$. \begin{theorem}[Lagrange's theorem] Let $p$ be prime and $f \in \mathbb{Z}[x]$ be a polynomial with integer coefficients. Either every coefficient is divisible by $p$, or the following conguence has $\mathrm{deg}(f)$ solutions in $\mathbb{Z}/p\mathbb{Z}$. \[f(x) \equiv 0 \mod p\] \end{theorem} Imagine now that we have $\mathbb{Z} / m \mathbb{Z}$, where $m$ is a product of distinct primes. We can make use of the Chinese remainder theorem to break the problem into multiple prime congruences and then apply Lagrange's theorem. \begin{corollary} Let $n=\prod^{k}_{i=1} p_i$ be a product of distinct prime and $f \in \mathbb{Z}[x]$ be a polynomial with integer coefficients. Either every coefficient is divisible by $p$, or the following conguence has $k\mathrm{deg}(f)$ solutions in $\mathbb{Z}/n\mathbb{Z}$. \[f(x) \equiv 0 \mod p\] \end{corollary} Lagrange's theorem also demonstrates great power in simplifying proofs; One remarkable theorem that can be proven by Lagrange's theorem is Wilson's theorem. \begin{theorem}[Wilson's theorem] \[ p \text{ is prime } \iff (p-1)! \equiv -1 \mod p \] \end{theorem} With a prime modulus, every integer $n$ has a unique inverse such that $n^{-1} n \equiv 1$. So when considering $(p-1)!=1\cdot 2 \cdot \hdots \cdot (p-1)$, when an integer isn't its own inverse we can use commutativity to match each $n$ in the product with its respective $n^{-1}$ to get $1$. We need to find which integers are their own inverse since they cannot match with anything in the product. This means we are to solve $x^2 \equiv 1 mod p$ which occurs only when $x$ is $1$ or $-1$ according to Lagrange's theorem. Therefore every other number is 'pairable' with its inverse to make $1$, so we have the following. \[(p-1)! \equiv \prod^{p-1}_{k=1} k \equiv \prod^{p-3}_{k=1} 1 \cdot 1 \cdot -1 \equiv -1 \mod p\] \begin{corollary} \[ p\text{ is prime } \implies [(\frac{p-1}{2})!]^2(-1)^{\frac{p-1}{2}}\equiv -1 \mod p\] \end{corollary} Furthermore, this corollary or Euler's criterion (to be covered) can be used to prove the following \begin{proposition} \[ \left( \frac{p-1}{p}\right) =1 \iff p \equiv 1 \mod 4 \] \end{proposition} Euler's criterion gives the Legendre symbol a more tangible form to work with. It can be proven using Fermat's little theorem and Lagrange's theorem (yet to be introduced) together, however there exists an even more elementary approach. \begin{theorem}[Euler's criterion] \[ \left( \frac{a}{p} \right) = a^{\frac{p-1}{2}} \mod p \] \end{theorem} For the case where $a$ is a quadratic residue, $a \equiv x^2 \mod p \implies a^{\frac{p-1}{2}}x^{p-1} \equiv 1 \mod p$ When $a$ is a quadratic nonresidue, $x^2 \equiv 1 \mod p \implies x \equiv \pm 1 \mod p$, so therefore it must equal $-1$ \subsection{Law of quadratic reciprocity} \begin{lemma}[Gauss' lemma] \[ a \mathbb{Z} / (\frac{p-1}{2})\mathbb{Z} = \{ a, 2a, 3a, \hdots , (\frac{p-1}{2})a \} \] \[ n = |\{ k \in a \mathbb{Z} / (\frac{p-1}{2}\mathbb{Z} : k > \frac{p-1}{2} \}| \] \[ \left( \frac{a}{p} \right) = (-1)^{n} \] \end{lemma} The proof works based on our favourite little fact that for prime moduli, for a fixed $a$, each $ax$ is distinct for incongruent $x$. \[ (\frac{p-1}{2})! \equiv a^{\frac{p-1}{2}}(\frac{p-1}{2})!(-1)^{n} \] \[ 1 \equiv a^{\frac{p-1}{2}}(-1)^{n} \] \[ a^{\frac{p-1}{2}} \equiv a^{p-1}(-1)^{n} \] \[ a^{\frac{p-1}{2}} \equiv (-1)^{n} \] \[ \left( \frac{a}{p} \right) \equiv (-1)^{n} \] \begin{theorem}[Law of quadratic reciprocity] \[ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{(p-1)(q-1)}{4}} \] \end{theorem} \section{Ring theoretic formulation} After having learned the rudiments of modular arithmetic, we can analyze our work through the perspective of the algebraist. \subsection{Additive group of integers modulo $n$} \subsection{Multiplicative group of integers modulo $n$} Since we know modular multiplicative inverses exist for numbers coprime to the modulus, we make $(\mathbb{Z} / n \mathbb{Z})^{*})$ only contain integers of $\mathbb{Z} / n\mathbb{Z}$ coprime to $n$ since groups must have all elements invertible. The fact that any $ax$ has a unique solution mod $p$ is actually analogous to the fact that $f(h)=gh$ is a bijection for any group. To compromise between group theory and number theory, we could say that $\mathbb{Z} / p\mathbb{Z}$ $f(n)=an$ is bijective. When the modulus is prime, many desirable properties can be shown since evey element of the additive group (save $0$) is still in the multiplicative group! This means that every element (except $0$) is inveritible for multiplicative groups of prime moduli; this is why we can prove Fermat's little theorem, Lagrange's theorem, Wilson's theorem, and many more results. When our modulus isn't prime, we can establish the same results, however they'll only hold for the integers coprime to the modulus. Even Euler's theorem that $a^{\varphi (n)}\equiv 1 \mod n$ is a trivial consequence of the group theoretic result that$g^{|G|}=1_{G}$ A group of order $n$ has $\varphi(n)$ generators, $(\mathbb{Z} / n\mathbb{Z})^{*}$ has order $\varphi(n)$, and hence has $\varphi(\varphi(n))$ generators (i.e primitive roots). \subsection{Commutative ring of integers modulo $n$} Say we want to combine $(\mathbb{Z} / n\mathbb{Z})^{+}$ and $(\mathbb{Z} / n\mathbb{Z})^{*}$ into one algebraic structure. If we have $(\mathbb{Z} / n\mathbb{Z})^{+}$ as the base set, all the elements will be in our algebraic structure, but it is possible that for multiplication there will be elements without inverses (meaning that this structure will connect a group and a 'monoid'). On the other hand, if we have $(\mathbb{Z} / n\mathbb{Z})^{*}$ as the base set, we're missing the identity element for addition ($0$), and the set would never be closed under addition (my counter example is $(n-1)+1=0 \notin (\mathbb{Z} / n\mathbb{Z})^{*}$). Though it sucks to lose invertibility, the former is definitely the better of the 2 cases, since having an ill-defined operation is just unacceptable. This additive group and multiplicative monoid combination is called a \emph{ring}, and we also define the distributive law of multiplication with respect to addition. \begin{proposition} $ \mathbb{Z} / n\mathbb{Z} $ is a commutative ring of two abelian groups. \end{proposition} When the modulus is prime, many desirable properties can be shown; When studying quadratic residues, we often confined ourselves to prime moduli. The reason for this is because prime modular rings are fields; rings that can claim their invertibility back! \begin{proposition} Let $p$ be prime, then $ \mathbb{Z} / p\mathbb{Z} $ is a field. \end{proposition} This is the necessary condition for Lagrange's theorem to hold; so the field properties have been implicitly working their magic whenever we employed Lagrange's theorem. This is the primary reason why the theorem is powerful to begin with! Aurifeuillan factorization