\part{Modular arithmetic}
\chapter{Modular arithmetic}
Modular arithmetic is basically a convenient notation for equivalence classes of numbers that have the same remainder when divided by $n$.

Congruence
\[ a \equiv b \mod n  \iff n | a-b \]

modulus; the number that tells when to wrap around

\section{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 m$. This is a neat notational shortcut.
\[ [a]_m = \{ km+a : k \in \mathbb{Z} \} \]
\[ a \equiv b \mod m \iff [a]_m = [b]_m \]


\[ \mathbb{Z} = \cup^{m}_{i=0} [i]_m\]
\[ \mathbb{Z} / m \mathbb{Z} = \{ [a]_m  : a \in \mathbb{Z} \}\]

This notation may seem a little overly complicated; the reason we write this set like this is because this notation comes from group theory, meaning quotient group; though quotient groups are extremely powerful in this setting, we will remain with our elementary methods of analysis. Feel free to check out Group Theory if you are interested.


\[\forall  n \in \mathbb{Q} [  a \equiv b \mod m \implies an \equiv bn \mod m  ] \]
\[\forall  n \in \mathbb{N} \setminus \{0\} [  a \equiv b \mod m \implies a^n \equiv b^n \mod m  ] \]

\[ 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 \]
\[\gcd(a,n)=1 \land ax \equiv ay \mod n \implies x \equiv y \mod n\]


\chapter{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) \]

11
7
13

-binary squaring




\section{Modular multiplicaive inverse}



\chapter{Euler's theorem}
\section{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}.

\section{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 ist one proposition that will be required to compare Fermat's version to Euler's.

\begin{proposition}
\[ \varphi (p) = p-1 \]
\end{proposition}

\section{Euler's theorem}

\begin{theorem}[Euler's theorem]
	\[ \gcd(a,n)=1 \implies a^{\varphi (n)} \equiv 1 \mod n \]
\end{theorem}


\section{Discrete logarithms}
Euler's theorem is particularly useful for discussing the

The \emph{discrete logarithm $\log_b (a)$ modulo $m$} is any integer $k$ solving the following.
\[ b^k \equiv a \mod m \]




\chapter{Chinese remainder theorem}

\begin{theorem}[Chinese remainder theorem]
\end{theorem}






\chapter{Quadratic residues}

\section{Modular quadratics}
- quadratic residue
<p>\(q \text{ is a quadratic residue modulo } n \iff \exists x\in \mathbb{Z}_{n} : x^2 \equiv q \mod n\)</p>
- Legendre symbol
<h3 class=dred>Legendre symbol</h3>
<p>If \(p\) is an odd prime</p>
<p>\( \left( \frac{a}{p} \right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue} \\ -1 & \text{if } a \text{ is a quadratic nonresidue}\\ 0 & \text{if } a \equiv 0 \mod p \end{cases}\)</p>
<h4 class=dred>Theorems</h4>
<p>\( \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p}\right) \)</p>
<p>\( \left( \frac{a}{p} \right) = \left( \frac{a+kp}{p} \right) \)</p>

- Euler's criterion
<h3 class=dred>Euler's criterion</h3>
<p>\( \left( \frac{a}{p} \right) = a^{\frac{p-1}{2}} \mod p  \)</p>
<h3 class=dred>Proof</h3>
<p>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\)</p>
<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\)</p>

- uniqueness mod (p-1)/2 of quadratic residues
\section{Lagrange's theorem}

\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}


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}



\section{Law of quadratic reciprocity}


<h3 class=dred>Gauss' lemma</h3>
<p>\( u = |\{ s \in \{  a \mod p , 2a \mod p , 3a \mod p  ... , (\frac{p-1}{2})a \mod p\} : s \gt \frac{p-1}{2}   \}| \)</p>

<p>\( \left( \frac{a}{p}  \right) = (-1)^{u} \)</p>
<h4 class=dred>Proof</h4>
<p>Imagine some reduced product \( a^{\frac{p-1}{2}} ( 1 \cdot 2 \cdot 3 \cdot ... \cdot \frac{p-1}{2} ) \mod p\).</p>
<p>Since \(p\) is prime and all numbers  up to \(\frac{p-1}{2}\) are coprime, these are still unique elements in \( [0,p]\). However under this operation, some numbers in this product may fall in \( [\frac{p-1}{2},p] \), or in other words, <b>modularly negative</b>.</p>
<p>Therefore we can simplify as  \((-1)^{u}(\frac{p-1}{2})! \mod p\), where \(u\) is the amount of elements that are on the other side of \(p\) (modularly negative). Since the definition of \(u\) is the cardinality of all these "modularly negative" results, we get \( a^{\frac{p-1}{2}}(\frac{p-1}{2})!  \equiv (-1)^{u}(\frac{p-1}{2})! \mod p \), or, \( a^{\frac{p-1}{2}} \equiv (-1)^u \mod p\) </p>


<h3 class=dred>Law of quadratic reciprocity</h3>
<p>\( \left( \frac{p}{q}  \right) \left( \frac{q}{p}  \right) = (-1)^{\frac{(p-1)(q-1)}{4}}\)</p>


<h3 class=dred>Quadratic residue lemmas</h3>
<p>\(x^2 \equiv -1 \mod p \iff p \equiv 1 \mod 4\)</p>
<h4 class=dred>Proof</h4>
<p>By Wilson's theorem, \(-1 \equiv (p-1)! \equiv ((\frac{p-1}{2})!)^2 (-1)^{\frac{p-1}{2}} \mod p\)</p>
<p>If \(p \equiv 1 \mod 4\), then \(\frac{p-1}{2} = \frac{(4k+1)-1}{2}\) is always even, hence the \(-1\) is always made positive and the lemma is proved </p>
<p>By alternate methods, by Euler's criterion, \( \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}\). This means for \(-1\) to be a residue, \(\frac{p-1}{2}\) must be even, and for this to be even, \(p \equiv 1 \mod 4\)</p>

- Gauss' lemma
- law of quadratic reciprocity



<h3 class=dred>Carmichael's totient function</h3>
<p>Function \(\lambda (n)\) denoting the smallest \(m :  \gcd (a,n) \implies a^m \equiv 1 \mod n\)</p>
<p>\(\lambda (p) = \varphi (p)\)</p>


<h3 class=dred>Carmichael number</h3>
<p>Pseudoprime that passes the Fermat primality test for all coprime \(a\)</p>
<p>\(n \text{ is a Carmichael number } \iff n \text{ is composite } \land \forall a \in \mathbb{N} : \gcd(a,n) = 1, a^{n-1} \equiv 1 \mod n\)</p>


<h3 class=dred>Korselt's theorem</h3>
<p>\(n \text{ is a Carmichael number } \iff n=\prod_{i=1} p_i : \text{each prime is distinct } \land p_i | n-1 \)</p>
<h4 class=dred>Proof</h4>
<p>let \gcd(a,n)=1, then \(\forall p_i, a^{p_i -1} \equiv 1 \mod p_i \) and since \(p_i -1 | n-1\) (by the assumption), then \forall p_i, a^{n-1} \equiv 1 \mod p_i\) and therefore since \(a^{n-1}-1\) divides all the prime factors, \( a^{n-1} \equiv 1 \mod n\)</p>





