SP20:Lecture 18 Modular division and exponentiation

From CS2800 wiki

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 [math]x [/math] is a number (e.g. a modular number), then we say [math]y [/math] is a multiplicative inverse of [math]x [/math] if [math]xy = 1 [/math] (or [math]xy = \href{/cs2800/wiki/index.php/Modular_number}{⟦1⟧} [/math] in the case of modular numbers).
Definition: Unit
If [math]x [/math] is a number that has a multiplicative inverse, then [math]x [/math] 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 [math]\href{/cs2800/wiki/index.php/%E2%84%A4_m}{ℤ_m} [/math]. 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^*
[math]ℤ_m^* [/math] is the set of all units of [math]\href{/cs2800/wiki/index.php/%E2%84%A4_m}{ℤ_m} [/math]


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


Definition: φ
[math]\href{/cs2800/wiki/index.php/%CE%A6}{φ}(m) [/math] is the number of units of [math]\href{/cs2800/wiki/index.php/%E2%84%A4_m}{ℤ_m} [/math].

Units and gcd

If [math]\href{/cs2800/wiki/index.php/Modular_number}{⟦a⟧} \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4_m}{ℤ_m} [/math], then [math]\href{/cs2800/wiki/index.php/Modular_number}{⟦a⟧} [/math] is a unit if and only if [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,m) = 1 [/math].
Proof:
This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 33.

φ(p) for prime p

If [math]p [/math] is prime, then [math]\href{/cs2800/wiki/index.php/%CE%A6}{φ}(p) = p - 1 [/math]
Proof:
This content has not been migrated to the wiki yet. See Redirect:SP17 Lecture 33.