## Tag Archives: modular arithmetic

### On the factors of a cyclotomic polynomial over ZZ/(p)

Let $\ell$ be a prime and let $\Phi_\ell(x) = \frac{x^\ell-1}{x-1} \in \mathbb{Z}[x]$ be the $\ell$th cyclotomic polynomial. (Remember that $\Phi_\ell$ is irreducible over $\mathbb{Z}$.) Let $p$ be a prime and let $\zeta$ denote any fixed primitive $\ell$th root of unity.

1. Show that if $p=\ell$ then $\Phi_\ell(x) = (x-1)^{\ell-1} \in \mathbb{F}_p[x]$.
2. Suppose $p \neq \ell$ and let $f$ denote the order of $p$ in $\mathbb{F}_\ell$. (That is, $f$ is minimal such that $p^f \equiv 1$ mod $\ell$.) Show that $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$. Conclude that the minimal polynomial of $\zeta$ over $\mathbb{F}_p$ has degree $f$.
3. Show that $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ for any integer $a$ not divisible by $\ell$. Conclude that, in $\mathbb{F}_p[x]$, $\Phi_\ell(x)$ is the product of $\frac{\ell-1}{f}$ distinct irreducible polynomials of degree $f$.
4. As an example, find the degrees of the irreducible factors of $\Phi_7(x)$ over $\mathbb{F}_p$.

1. Mod $p=\ell$, we have $x^\ell-1 = (x-1)^\ell$. So $\Phi_\ell(x) = (x-1)^{\ell-1}$ as desired.
2. Note that $\zeta \in \mathbb{F}_{p^f}$ precisely when $\zeta$ is a root of $x^{p^f-1}-1$. Since $p^f \equiv 1$ mod $\ell$, we have that $\ell$ divides $p^f-1$. By this previous exercise, $x^\ell - 1$ divides $x^{p^f-1}-1$. Since $\zeta$ is a $\ell$th root of unity, $\zeta \in \mathbb{F}_{p^f}$. Conversely, suppose $\zeta \in \mathbb{F}_{p^t}$. Now $\zeta^\ell \equiv 1$, so $\ell$ divides $p^t-1$ by Lagrange’s theorem in the group $\mathbb{F}_{p^t}^\times$. Thus $p^t \equiv 1$ mod $\ell$, and so $f$ divides $t$. So $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$.

Next we claim that $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^f}$. The $(\subseteq)$ inclusion is clear since $\zeta \in \mathbb{F}_{p^f}$. $(\supseteq)$ $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^t}$ for some $t$, since finite fields are essentially unique. By the preceding argument, $f|t$, so $\mathbb{F}_{p^f} \subseteq \mathbb{F}_{p^t} = \mathbb{F}_p(\zeta)$ using this previous exercise.

3. It is clear that $\mathbb{F}_p(\zeta^a) \subseteq \mathbb{F}_p(\zeta)$. Conversely, since $\ell$ does not divide a$, by Bezout’s identity there exist $x,y \in \mathbb{Z}$ such that $ax + \ell y = 1$. Now $(\zeta^a)^x = \zeta^{ax}$ $= \zeta^{1-\ell y}$ $= \zeta$. So $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ provided $\ell$ does not divides $a$. Now consider $\Phi_\ell(x)$ as a polynomial over $\mathbb{F}_p$. Let $\zeta_i$ be the distinct primitive $\ell$th roots of unity. By part (b), $\mathbb{F}_p(\zeta_i)$ has degree $f$ over $\mathbb{F}_p$ for each $i$, so the minimal polynomial of $\zeta_i$ over $\mathbb{F}_p$ has degree $f$. So the irreducible factors of $\Phi_\ell$ have degree $f$, and there are $\frac{\ell-1}{f}$ such factors. Moreover, since $\Phi_\ell$ is separable, its factors are distinct. 4. If $p \equiv 1$ mod 7, then $\Phi_7(x) = (x-1)^6$ by part (a). Evidently 2 and 4 have order 3 mod 7, so if $p \in \{2,4\}$ mod 7 then $\Phi_7(x)$ factors into two irreducible cubics. Similarly, 3 and 5 have order 6 mod 7, so that if $p \in \{3,5\}$ mod 7 then $\Phi_7(x)$ is irreducible. Since 6 has order 2 mod 7, if $p \equiv 6$ mod 7, then $\Phi_7(x)$ factors into three irreducible quadratics. ### A fact about multivariate polynomials over ZZ Let $f(x_1,\ldots,x_n) \in \mathbb{Z}[x_1,\ldots,x_n]$, and let $p$ be a prime. Prove that $f(x_1,\ldots,x_n)^p = f(x_1^p,\ldots,x_n^p)$ mod $p$. Remember that $\alpha^p \equiv \alpha$ mod $p$ for all $\alpha$. Say $f = \sum_i c_i \prod_j x_j^{e_{i,j}}$. Then $f(x_1,\ldots,x_n)^p = (\sum_i c_i \prod_j x_j^{e_{i,j}})^p$ $= \sum_i c_i^p \prod_j x_j^{e_{i,j}p}$ $= \sum_i c_i \prod_j (x_j^p)^{e_{i,j}}$ $= f(x_1^p,\ldots,x_n^p)$ as desired. ### pn choose pk and n choose k are congruent mod p Show that $\binom{pn}{pk} \equiv \binom{n}{k}$ mod $p$. Note that $(1+x)^{pn} = \sum_{t=0}^{pn} \binom{pn}{t}x^t$ by the binomial theorem. The coefficient of $x^{pk}$ is $\binom{pn}{pk}$. Over $\mathbb{F}_p$, we have $(1+x)^{pn} = ((1+x)^p)^n$ $= (1+x^p)^n$ $= \sum_{t=0}^n \binom{n}{t}(x^p)^t$, and now the coefficient of $x^{pk}$ is $\binom{n}{k}$. In particular, we have $\binom{pn}{pk} \equiv \binom{n}{k}$ mod $p$. ### Wilson’s Theorem Prove that $x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha)$. Conclude that $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}$. Deduce Wilson’s Theorem: if $p$ is an odd prime, then $(p-1)! \equiv -1$ mod $p$. Recall that $x^{p^n}-x = \prod_{\alpha \in \mathbb{F}_{p^n}^\times}(x-\alpha)$ by definition, and that $0 \in \mathbb{F}_{p^n}$ is merely the root having minimal polynomial $x$. So $x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha)$. Comparing constant coefficients, we have $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} (-\alpha) = -1$, so that$latex $(-1)^{p^n-1} \prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = -1$, and hence $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}$.

Restrict now to the field $\mathbb{F}_p \cong \mathbb{Z}/(p)$ with $p$ odd. Then $\prod_{\alpha \in \mathbb{F}_p} \alpha = (p-1)!$, and $(-1)^p = -1$. Thus $(p-1)! \equiv -1$ mod $p$.

(I’d like to point out that this is a really roundabout way to prove Wilson’s Theorem. The easy(ier) way is to note that in $\mathbb{Z}/(p)^\times$, every element but -1 is distinct from its inverse.)

### Every prime congruent to 1 mod 4 is a sum of squares

Prove that every prime integer $p$ congruent to 1 mod 4 is a sum of two squares. Show that every product of two such primes is also a sum of two squares.

Let $p$ be such a prime. We know that $p$ is not irreducible in $\mathbb{Z}[i]$; thus there exist nonunits $\alpha,\beta$ such that $p = \alpha\beta$. Note that neither of $\alpha$ and $\beta$ can have norm 1. Since $p^2 = N(p) = N(\alpha)N(\beta)$, letting $\alpha = a+bi$, we see that $a^2 + b^2 = p$ as desired.

Now suppose $p,q$ are integer primes congruent to 1 mod 4. As above, we have $p = \alpha_1\beta_1$ and $q = \alpha_2\beta_2$, where $\alpha_i$ and $\beta_i$ have norm $p$ and $q$ as needed. Now $N(\alpha_1\beta_2) = pq$. In particular, if $\alpha_1\beta_2 = a+bi$, then $a^2+b^2 = pq$.

### The Frobenius endomorphism in ZZ/(p)

Prove that $(a+b)^p \equiv a^p + b^p \mod p$ for all integers $a$ and $b$.

We proved this in greater generality in this previous exercise. (See part 4.)

### Possible norms of Gaussian integers mod 4

Show that the norm of a Gaussian integer cannot be congruent to 3 mod 4.

Let $a+bi$ be a Gaussian integer. Recall that $N(a+bi) = a^2 + b^2$. Note that the squares mod 4 are 0 and 1; the possible sums of two squares mod 4 are 0, 1, and 2.

### A public key code

Let $N$ be a positive integer. Let $M$ be an integer which is relatively prime to $N$ and let $d$ be an integer relatively prime to $\varphi(N)$, where $\varphi$ denotes the Euler totient function. Prove that if $M_1 \equiv M^d \mod N$ then $M \equiv M_1^e \mod N$, where $e$ is a multiplicative inverse of $d$ mod $\varphi(N)$; that is, $de \equiv 1 \mod \varphi(N)$.

Note that $M^{de} \equiv M^{k\varphi(N) + 1} \equiv (M^{\varphi(N)})^k \cdot M^1 \mod N$. By Euler’s Theorem (proved here), we have $M^{\varphi(N)} \equiv 1 \mod N$, so that $M_1^e \equiv M \mod N$ as desired.

### Compute inverses modulo n

For each of the following pairs of integers $a$ and $n$, show that $a$ is relatively prime to $n$ and determine the inverse of $a$ mod $n$.

1. $a = 13$, $n = 20$
2. $a = 69$, $n = 89$
3. $a = 1891$, $n = 3797$
4. $a = 6003722857$, $n = 77695236973$

### If n divides m, then the natural ring homomorphism from ZZ/(m) to ZZ/(n) is surjective on the units

Let $m$ and $n$ be positive integers with $n$ dividing $m$. Prove that the natural surjective ring homomorphism $\varphi : \mathbb{Z}/(m) \rightarrow \mathbb{Z}/(n)$ is also surjective on the units.

[With help from Ravi Vakil’s notes.]

Given a unital ring homomorphism $\varphi : R \rightarrow S$, it is certainly the case that $\varphi[R^\times] \subseteq S^\times$. If we have equality, we say that $\varphi$ is surjective on the units of $S$. If $\varphi$ and $\psi$ are unital ring homomorphisms which are surjective on the units and the composition makes sense, then so is $\varphi \circ \psi$. Clearly isomorphisms are surjective on the units.

We begin with some lemmas.

Lemma 1: Let $\{R_i\}_I$ be a nonempty set of rings with $1 \neq 0$. Then $(a_i) \in \prod R_i$ is a unit if and only if $a_i \in R_i$ is a unit for all $i \in I$. Proof: $(\Rightarrow)$ Let $(a_i)$ be a unit. Then there exists $(b_i) \in \prod R_i$ such that $(a_i)(b_i) = (a_ib_i) = 1$, and thus $a_ib_i = 1$ for all $i$. Similarly, $b_ia_i = 1$. Thus $a_i$ is a unit for each $i$. $(\Leftarrow)$ If $a_i \in R_i$ is a unit, then there exists $b_i \in R_i$ such that $a_ib_i = b_ia_i = 1$. Then $(a_i)(b_i) = (b_i)(a_i) = 1$. $\square$

Lemma 2: Let $p$ be a prime and let $0 \leq s \leq t$. Then the natural surjective ring homomorphism $\pi : \mathbb{Z}/(p^t) \rightarrow \mathbb{Z}/(p^s)$ given by $\pi([a]_{p^t}) = [a]_{p^s}$ is surjective on the units. Proof: Now let $[a]_{p^s}$ be a unit in $\mathbb{Z}/(p^s)$. Then $\mathsf{gcd}(a,p^s) = 1$, so that $\mathsf{gcd}(a,p) = 1$, and thus $\mathsf{gcd}(a,p^t) = 1$. So $[a]_{p^t}$ is a unit in $\mathbb{Z}/(p^t)$. Since $\pi([a]_{p^t}) = [a]_{p^s}$, $\pi$ is surjective on the units. $\square$

Lemma 3: Let $\{R_i\}_I$ and $\{S_i\}_I$ be rings with $1 \neq 0$, and let $\varphi_i : R_i \rightarrow S_i$ be a surjective ring homomorphism which is surjective on the units; that is, $\mathsf{im}\ \varphi|_{R^\times} = S^\times$. Then $\prod \varphi_i$ is surjective on the units. Proof: Follows from Lemma 1. $\square$

Now let $m = \prod p_i^{t_i}$. Since $n|m$, we have $n = \prod p_i^{s_i}$ where $0 \leq s_i \leq t_i$ for all $i$. Now the $(p_i^{t_i})$ are pairwise comaximal, so that by the Chinese remainder Theorem we have isomorphisms $\varphi : \mathbb{Z}/(m) \rightarrow \prod \mathbb{Z}/(p_i^{t_i})$ and $\psi : \mathbb{Z}/(n) \rightarrow \prod \mathbb{Z}/(p_i^{s_i})$ given by $\varphi([a]_m) = ([a]_{p_i^{t_i}})$ and $\psi([a]_n) = ([a]_{p_i^{s_i}})$. Note also that $\pi : \mathbb{Z}/(m) \rightarrow \mathbb{Z}/(n)$ given by $\pi([a]_m) = [a]_n$ is a well-defined ring homomorphism. Likewise we have well-defined surjective ring homomorphisms $\pi_i : \mathbb{Z}/(p_i^{t_i}) \rightarrow \mathbb{Z}/(p_i^{s_i})$ for each $i$ given by $\pi_i([a]_{p_i^{t_i}}) = [a]_{p_i^{s_i}}$. It is clear that $\psi \circ \pi = (\prod \pi_i) \circ \varphi$.

By Lemmas 2 and 3, $\prod \pi_i$ is surjective on the units. Thus $\pi = \psi^{-1} \circ (\prod \pi_i) \circ \varphi$ is surjective on the units.