2.6. Fields

Informally, a field is an algebraic structure in which all non-zero elements are invertible. That is, a structure where multiplication has division. Examples of fields include the rationals, the reals and the complex numbers. Interestingly, it also includes ${\mathbb{Z}}_p$ precisely when $p$ is a prime number.

Reflect.

Look back at your notes. You should be able to prove that any non-zero element of ${\mathbb{Z}}_p$ is invertible just by citing the right things.

Note:

Most of this section is discussed informally and actively (i.e. with a lot of me pointing at things) during the lecture. As such, these notes do not cover said discussion.

Fermat’s little theorem

Let $p$ be a prime number.

Fermat's little theorem.

If $p\nmid a$, then $a^{p-1}{\equiv }_{p}1$.

I prove this by first considering a lemma.

Lemma.

Let $0<a<p$ and $0<i\le j<p$. If $ia{\equiv }_{p}ja$, then $i=j$.

Proofs are informally seen in lectures.

Example.

Say you want to figure out what the number $50^{247}$ is mod $83$. First, divide $247=82\cdot 3+1$ and substitute. Then, Fermat’s little theorem solves the problem.

$$50^{247}=50^{82\cdot 3+1}={\left(50^{82}\right)}^3\cdot 50\equiv 1^3\cdot 50=50(\mathrm{mod}83).$$

A tiny glimpse into more advanced number theory

Prove these as exercises. You need nothing more than what I covered so far.

Modular logarithms.

If $k\equiv \ell (\mathrm{mod}p-1)$, then $a^k{\equiv }_p{a}^{\ell }$. That is, you can reduce the exponent mod $p-1$ to simplify computations.

Modular inverses.

If $p$ is not $2$, then the inverse of $a/{\equiv }_{p}0$ is $a^{p-2}$.

Modular unit square roots.

If $p$ is not $2$, then ${\left(a^{\frac{p-1}{2}}\right)}^2=a^{p-1}{\equiv }_{p}1$. That is, $a^{\frac{p-1}{2}}$ is like the “square root” of $1$ mod $p$.