Wilson's Theorem

A positive integer $n > 1$is a prime if and only if:

Euler's Theorem

Let $n \in \mathbb{Z}^{+}$ and $a \in \mathbb{Z}$ s.t. $gcd(a, n) = 1$, then:

Fermat's Little Theorem

Let $p$be a prime and $a \in \mathbb{Z}$, then:

or equivalently:

Reference

1. Wilson's Theorem - Brilliant

2. Euler's Theorem - Brilliant

3. Fermat's Little Theorem - Brilliant

Introduction

Since we can add, subtract, multiply, divide even... what would be missing? Powering! I'm not talking about some power fantasy here, but rather introduce some really really important theorems. Fermat little's theorem proves useful in a great deal of situation, and is along with Euler's theorem a piece of arithmetic you need to know. Arguably the most canonical example of using these is the RSA cryptosystem, whose decryption step is built around Euler's theorem.

Fermat's Little Theorem

Since we want to talk about powers, let's look at powers. And because I like 7, I made a table of all the powers of all the integers modulo 7.

On the last row, there is a clear pattern emerging, what's going on??? Hm, let's try again modulo 5 this time.

Huh, again?! Clearly, there is something going on... Sage confirms this!

p, itworks = 1, True
for _ in range(100):
    p = next_prime(p)
    Fp = GF(p) # Finite Field of size p
    itworks &= all(Fp(x)^(p-1) == 1 for x in range(1,p))

print(itworks)
# True

Claim (Fermat's Little Theorem): Let$p$a prime.$\forall a\in\mathbb Z, a^p\equiv a~[p]$

When$a\neq 0$, this is equivalent to what we observed:$a^{p-1}\equiv 1~[n]$. There are several proofs of Fermat's Little Theorem, but perhaps the fastest is to see it as a consequence of the Euler's Theorem which generalizes it. Still, let's look a bit at some applications of this before moving on.

A first funny thing is the following:$\forall a\in\mathbb Z, a\cdot a^{p-2}\equiv a^{p-1}\equiv 1~[p]$. When$p>2$, this means we have found a non-trivial integer that when multiplied to$a$yields 1. That is, we have found the inverse of$a$, wow. Since the inverse is unique modulo$p$, we can always invert non-zero integers by doing this. From a human point of view, this is really easier than using the extended euclidean algorithm.

Introduction

Thinking not over the integers as a whole but modulo some integerinstead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.

Congruences

For the following chapter, we will assumeis a natural integer, andandare two integers. We say thatandare congruent modulowhen, or equivalently when there is an integersuch that. We denote this byor . I will use the first notation throughout this chapter.

Remark: When, we have, whereis the remainder in the euclidean division ofby

This relation has a number of useful properties:

• The proofs are left as an exercise to the reader :p (Hint: go back to the definition)

Seeing as addition and multiplication are well defined, the integers moduloform a ring, which we note. In sage, you can construct such ring with either of the following

Modular Inverse