Theorem. (Fermat's Little Theorem) For \(p\) prime and \(a\) not divisible by \(p\), \(a^{p-1}\equiv 1\mod p\).
We looked at powers of \(a\) modulo \(p\). For example, when \(a=2\) and \(p=5\), we saw that
We only needed to check powers of \(a=2\) up to \(p-1=4\), after this, any patterns that we saw repeated.
By taking \(2\) to different powers, we could obtain all possible residues modulo \(5\).
The second observation isn’t true for every choice of \(a\) and \(p\):
We say that \(a\) is a primitive root modulo \(n\) if for every \(b\in\mathbb{Z}\) with \((a,b)=1\), there exists some \(k\in\mathbb{N}\) so that \(a^k \equiv b \mod n\).
There’s not a straightforward algorithm to produce primitive roots modulo \(n\) in general, which brought us to the Diffie-Hellman key exchange.
A nice cartoon that helped us understand the process of the Diffie-Hellman key exchange, which was shamelessly borrowed from Wikipedia.
If you've seen this material before or want something to think about, here are some problems for you! Unless otherwise stated, all variables are assumed to be integers.
Let \(a,n\in\mathbb{N}\) with \( (a,n)=1\). The smallest \(k\) such that \(a^k \equiv 1 \mod n\) is called the order of \(a\) modulo \(n\). We write this as \( ord_n(a)\). How large can \(ord_n(a)\) be, depending on \(n\)?
In our discussion today, we'll talk about Fermat's little theorem, which states that \(a^{p-1}\equiv 1 \mod p\) for \(p\) prime and assuming \(p\) does not divide \(a\). Use this to do the following computations without a calculator:
