Notes - Groups HT23, Modular arithmetic

Created: March 15, 2023

Flashcards

Why is $(\mathbb Z _ n, \times)$ not a group?

Because $0$ has no inverse.

What does it mean for $\bar a \in \mathbb Z _ n$ to be a multiplicative unit?::

\[\exists \bar b \in \mathbb Z \text{ s.t. } \bar a \bar b = \bar 1\]

i.e. has multiplicative inverse.

How is the set of multiplicative units (elements with a multiplicative inverse) in $\mathbb Z _ n$ denoted?
\[\mathbb Z_n^\ast\]

When will some $a \in \mathbb Z _ n^\ast$ be a multiplicative unit?
\[\text{hcf}(a, n) = 1\]

i.e. coprime

How is Euler’s totient function $\varphi(n)$ defined?

The number of positive integers less than $n$ coprime to $n$.

What set makes up the group $\mathbb Z _ n^\ast$?
\[\\{1 \le z \le n : x,n \text{ coprime}\\}\]

What well-known number-theoretic function is equal to the size of the group $\mathbb Z _ n^\ast$?
\[|\mathbb Z_n^\ast | = \varphi(n)\]

When $p$ is prime, what is $\varphi(p)$ where $\varphi$ is Euler’s totient function?
\[p-1\]

What property of Euler’s totient function $\varphi(n)$ lets you conclude that

\[\varphi(p_1^{x} \cdots p_n^y) = (p_1 - 1)p_1^{x-1} \cdots (p_2 - 1)p_2^{y-1}\]

where $p _ 1^{x} \cdots p _ n^y$ is $n$’s prime factorisation?

$\varphi$ is multiplicative, i.e.

\[\varphi(mn) = \varphi(m)\varphi(n)\]

Can you state Fermat’s little theorem?

Let $p$ be a prime and let $a \in \mathbb Z$ such that $p$ does not divide $a$. Then

\[a^{p-1} = 1 \pmod p\]

Can you state Euler’s theorem?

Let $n \ge 2$ and let $a \in \mathbb Z$ be coprime with $N$. Then

\[a^{\varphi(n)} = 1 \pmod n\]

What useful fact links $\gcd(a, b)$ and $\text{lcm}(a, b)$?
\[\text{gcd}(a, b) \cdot \text{lcm(a, b)} = ab\]

Suppose $a = p _ 1^{\alpha _ 1} p _ 2^{\alpha _ 2} \cdots p _ k^{\alpha _ k}$ and $b = p _ 1^{\beta _ 1} p _ 2^{\beta _ 2} \cdots p _ k^{\beta _ k}$. Then what is $\gcd(a, b)$?
\[p_1^{\delta_1} p_2^{\delta_2} \cdots p_k^{\delta_k}\]

where $\delta _ i = \min(\alpha _ i, \beta _ i)$.

Suppose $a = p _ 1^{\alpha _ 1} p _ 2^{\alpha _ 2} \cdots p _ k^{\alpha _ k}$ and $b = p _ 1^{\beta _ 1} p _ 2^{\beta _ 2} \cdots p _ k^{\beta _ k}$. Then what is $\text{lcm}(a, b)$?
\[p_1^{\mu_1} p_2^{\mu_2} \cdots p_k^{\mu_k}\]

where $\mu _ i = \max(\alpha _ i, \beta _ i)$.

Proofs

Prove, by appealing to Lagrange’s theorem, Euler’s theorem and its special case, Fermat’s little theorem:

Let $n \ge 2$ and let $a \in \mathbb Z$ be coprime with $N$. Then

\[a^{\varphi(n)} = 1 \pmod p\]

Todo.



Related posts