初等数论第七周笔记

7.1 Euler's $\varphi$-function

We wish to generalize Fermat's little theorem to composite $n$ by replacing $a^n$ with $a^{\varphi(n)}$, where $\varphi$ is some function if $n$.

Recall that an element $u$ in a commutative ring $R$ is called a unit if there some $v \in R$ s.t. $u\cdot v=1$. It's easy to show that the set of all units in $R$ forms an (abelian) group $U_{R}$. We will densite $U_{\mathbb{Z}_{n}}$ by $U_n$.

Theorem 7.15

\[ \sum_{d|n}\varphi(d)=n \]

We will give a very short proof later.

7.2

To find the order of $a\in U_{n}$ (aka the order of $a$ mod $n$), one does not have to check of if $a^i\equiv 1$ one by one.

Lemma 7.16

Suppose that $a\in U_n$ has order $k$. Then $a^k\equiv 1 \pmod{n}\text{ iff }k|h$.

pf

By the division algorithm, we can write $h=qk+r(r<k)$.
Then $a^h=a^{kq}+a^r=a^r\equiv1\pmod{n}$. Note that $a^r\equiv1\text{ iff }r=0$.

Prop. 7.17

If $l$ and $m$ are coprime pos. integer, then $2^l-1$ and $2^m-1$ are coprime.

pf

Let $n=\gcd(2^l-1, 2^m-1)$. $n$ is clearly odd so $2\in U_{n}$.
Let $k$ be the order of $2$ in $U_{n}$. Since $n|2^{l}-1$, we have $2^l=1$ in $U_n$.
So $k|l$ and similarly $k|m$. Then $k|\gcd(l,m)=1$. Thus $k=1$, which means that $2^1=1$ in $U_n$. We see that $n=1$.

In partcular, distinct Merserne numbers are coprime.

Problem 7.18

If $a$ has order $k \mod n$ and $h \in \mathbb{N}$, then $a^k$ has order $\frac{k}{\gcd(h,k)}$.

The order of $U_n$, namely $\varphi(n)$ does not determine the group $U_n$ uniquely.

Ex. 7.19

$U_5 \cong C_4$ and $U_8 \cong C_2\times C_2$.

Def 7.20

If $U_n$ is cyclic, then any generator $g$ for $U_n$ is called a primitive root $\mod n$.

Ex 7.21

$2,3$ are primitive roots $\mod5$, but there is no primitive roots $\mod8$.
$1,4$ are not primitive root $\mod5$.

Corollary 7.22

An element $a\in U_n$ is a primitive root $iff $a^{\frac{\varphi(n)}{q}}\not=1$ in $U_n$ for each prime $q|\varphi(n)$.

Ex 7.23

Find all primitive roots $\mod11$.

$\varphi(11)=10=2\times5$
$2^2\not\equiv1, 2^5\not\equiv1\mod11$
$3^2\not\equiv1, 3^5\equiv1\mod11$.

Prop 7.24

There are $\varphi(\varphi(n))$ primitive root $\mod{n}$ assumiy $U_n$ is cyclic.

pf

Let $g$ be a primitive root $\mod{n}$, then $U_n$ is cyclic of order $\varphi(n)$.
Then $g^i$ generate $U_n\text{ iff }\gcd(i,\varphi(n))=1$. There are exactly $\varphi(\varphi(n))$ such $i$.

Theorem 7.25

If $p$ is prime, then the group $U_p$ has $\varphi(d)$ elements of order $d$ for each $d$ dividing $p-1$.

pf

For each $d|p-1$, we define $\Omega_d=\{a\in U_p|a\text{ has order } d\}$. Let $\omega_d=|\Omega_d|$.
Our aim is to show $\omega(d)=\varphi(d)$ for such $d$. The order of $a$ must divides $p-1$. Since the sets $\Omega_d$ form a partition of $U_p$, and hence

\[ \sum_{d|p-1}\omega(d)=p-1 \]

On the order hand, we have from Theorem 7.15

\[ \sum_{d|p-1}\varphi(d)=p-1. \]

So if suffices to show that $\omega\leq\varphi(d)$ for all $d|p=1$. By the definition of $\Omega_d$ the powers $a,a^2,\dots,a^d=1$ are all distinct and satisfies $x^d-1\equiv 0 \mod p$. So they are a complete set of roots for $f(x)=x^d-1$(Theorm 5.4). We shall show that $a^i\Omega_d \text{ iff }\gcd(i,d)=1$. Suppose that $a^i$ is a root of $f(x)$ and $j=\gcd(i,d)$.
Then $(a^i)^\frac{d}{j}=(a^d)^\frac{i}{j}=1^{\frac{i}{j}}=1$. But $d$ is the order of $a^i$, facing $j=1$.