# SP20:Lecture 18 Modular division and exponentiation

We started by trying to define modular exponentiation the same way that we defined modular addition and modular multiplication. However, we found that the obvious definition was not well-defined.

In order to fix it, we took a detour through modular division.

# Naive definition of modular exponentiation is not well-defined

This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 33.

# Units and inverses

This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 32 Operations on modular numbers.

If is a number (e.g. a modular number), then we say is a multiplicative inverse of if (or in the case of modular numbers).
Definition: Unit
If is a number that has a multiplicative inverse, then is called a unit.

# Units of ℤm

If we want to solve equations involving multiplication of modular numbers, we'll need to be able to find multiplicative inverses in . It will also turn out that the set of all units will be important as well, so we introduce some notation in this lecture for talking about it.

## Definitions/notation

This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 32 Operations on modular numbers.

Definition: ℤ m^*
is the set of all units of

This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 32 Operations on modular numbers.

Definition: φ
is the number of units of .

## Units and gcd

If , then is a unit if and only if .
Proof:
This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 33.

## φ(p) for prime p

If is prime, then
Proof:
This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 33.