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 \ellth cyclotomic polynomial. (Remember that \Phi_\ell is irreducible over \mathbb{Z}.) Let p be a prime and let \zeta denote any fixed primitive \ellth 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 \ellth 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 \ellth 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

We already did this here.

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.