Groups HT23, Modular arithmetic
Flashcards
@Define what it means for $\bar a \in \mathbb Z _ n$ to be a multiplicative unit.
i.e. has multiplicative inverse.
How is the set of multiplicative units (elements with a multiplicative inverse) in $\mathbb Z _ n$ denoted?
When will some $a \in \mathbb Z _ n$ be a multiplicative unit?
i.e. coprime
@Define Euler’s totient function $\varphi(n)$.
The number of positive integers less than $n$ coprime to $n$.
What set makes up the group $\mathbb Z _ n^\ast$?
What well-known number-theoretic function is equal to the size of the group $\mathbb Z _ n^\ast$?
When $p$ is prime, what is $\varphi(p)$ where $\varphi$ is Euler’s totient function?
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)\]@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\]@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 $\mathrm{lcm}(a, b)$?
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)$?
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 $\mathrm{lcm}(a, b)$?
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 n\]
Todo.