Solutions of Congruences and Binomial Coefficients

note

This is Lab 5 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

The program PolySolv allows you to specify a polynomial $f$ with integral coefficients, and a modulus $m$, and then it evaluates $f(a)(\bmod m)$ for each $a, 0 \leq a<m$.

Problem 1

Use PolySolv to find all roots of $7 x \equiv 1 (\bmod 91) ;$ all solutions of $7 x \equiv 35(\bmod 91)$; all solutions of $2 x \equiv 1 (\bmod 101)$. Note conformity with Theorem 2.17 of NZM.

Discriminants

In the next three problems, you are asked to gather data concerning the number of roots of a polynomial $f(x) \equiv 0(\bmod p)$, for various $f$ and $p$, and then to formulate a conjecture. Do not be disturbed if your numerical evidence is too meager to be compelling. Each polynomial $f$ has a discriminant, denoted $D(f)$, and defined on p. 487 of NZM. It can be computed using the program PolynomialDiscriminant. Prime factors of the discriminant are apt to be exceptional, and may not obey the general pattern.

Problem 2

Let $f(x)=x^{3}+x+1$, with discriminant $D(f)=-31$. Using PolySolv, for each prime number $p<100$ determine the value of $N_{f}(p)$. What is the biggest value attained? What values are attained, and with what frequencies? What is the average of the values calculated? Formulate conjectures regarding the general situation.

Problem 3

Let $g(x)=x^{3}+x^{2}-2 x-1$, with discriminant $D(g)=49$. Using PolySolv, for each prime number $p<100$ determine the value of $N_{g}(p)$. What is the biggest value attained? What values are attained, and with what frequencies? What is the average of the values calculated? Formulate a conjecture regarding the general situation.

Problem 4

Let $h(x)=x^{2}+x+1$, with discriminant $D(h)=-3$. Using PolySolv, for each prime number $p<100$ determine the value of $N_{h}(p)$. What is the biggest value attained? What values are attained, and with what frequencies? What is the average of the values calculated? Formulate a conjecture regarding the general situation.

Discussion

The situation touched on in Problems 2-4 above is quite complicated. Suppose that $f(x)$ is a polynomial of degree $d$ with integral coefficients. Then $0 \leq N_{f}(p) \leq d$; see Corollary 2.27 in NZM. The three polynomials considered above are irreducible (over the field $\mathbb{Q}$ of rational numbers). For such polynomials, additional patterns emerge in the statistics of the $N_{f}(p)$. For each $k, 0 \leq k \leq d$, the primes $p$ for which $N_{f}(p)=k$ have a certain relative density $d_{k}$. That is, the limit

$$d_{k}=\lim_{x\rightarrow\infty}\frac{1}{\pi(x)}\sum_{\substack{p\leq x \\ N_{f}(p)=k}}1$$

exists. These densities are determined by the Chebotarev Density Theorem in terms of the Galois group of $f$. Thus the densities depend on the particular polynomial, although only finitely many configurations can arise. In the case of the polynomial of Problem 2, the Galois group is $S_{3}$, and the densities are $d_{0}=1 / 3, d_{1}=1 / 2, d_{2}=0, d_{3}=1 / 6$. In Problem 3, the Galois group is $C_{3}$, and the densities are $d_{0}=2 / 3, d_{1}=d_{2}=0$, $d_{3}=1 / 3$. (For this polynomial, $N_{f}(p)=1$ if and only if $p=7$.) In Problem 4 the Galois group is $C_{2}$, and the densities are $d_{0}=1 / 2, d_{1}=0, d_{2}=1 / 2$, but the situation is more elementary, since by quadratic reciprocity we find that $N_{f}(p)=2$ if $p \equiv 1 (\bmod 3)$, and $N_{f}(p)=0$ if $p \equiv 2 (\bmod 3)$. The densities then follow by the prime number theorem for arithmetic progressions.

Concerning the densities $d_{k}$, it is obvious that $\sum_{k=1}^{d} d_{k}=1$, and it is easy to show that $d_{d-1}=0$. Not so obviously, the $d_{k}$ also satisfy the relation $\sum_{k=1}^{d} k d_{k}=1$. That is,

$$\lim_{x\rightarrow\infty}\frac{1}{\pi(x)}\sum_{p\leq x}N_{f}(p)=1$$

for any irreducible polynomial with integral coefficients. This is a consequence of the prime ideal theorem (which is a natural extension of the prime number theorem to algebraic number fields). For a more detailed account of how the densities $d_{k}$ are calculated, see H. Heilbronn, Zeta-functions and L-functions, Algebraic Number Theory (Brighton, 1965), Thompson, Washington, 1967, pp. 204-230, especially pp. 227-229.

Problem 5

For any two polynomials $f(x)$ and $g(x)$, one can define their resultant, $R(f, g)$. We skip the definition and fundamental theorems concerning this quantity, and mention just three useful properties: (i) If $f$ and $g$ have integral coefficients, then $R(f, g)$ is an integer. (ii) $R(f, g)=0$ if and only if $f$ and $g$ have a common factor (i.e., a common polynomial divisor of degree $>0$ ). (iii) There exist polynomials $u(x)$ and $v(x)$ with integral coefficients such that

$$f(x) u(x)+g(x) v(x)=R(f, g) .$$

Suppose that $f$ and $g$ have a common root $(\bmod p)$. That is, there is an $a(\bmod p)$ such that both $f(a) \equiv 0(\bmod p)$ and $g(a) \equiv 0 (\bmod p)$. On setting $x=a$ in the identity above, we see that the left hand side is divisible by $p$, and hence that $p \mid R(f, g)$. Thus if $p \nmid R(f, g)$ then $f$ and $g$ have no common root, and it follows that $N_{f g}(p)=N_{f}(p)+N_{g}(p)$. Let $f$ be as in Problem 2, and $g$ as in Problem 3, so that $f(x) g(x)=x^{6}+x^{5}-x^{4}+x^{3}-x^{2}-$ $3 x-1$. It can be shown that $R(f, g)=13$ in this case. By applying PolySolv, confirm that $f$ and $g$ have a common root when $p=13$. Without performing any additional calculation, list the roots of $f(x) g(x)(\bmod 13)$. Apply PolySolv to $f g$, to confirm your guess.

Problem 6

Apply PolySolv with $f(x)=x^{1732}-1, m=1733$. Having determined the number of roots of $f$, can you deduce that $m$ is prime? Is this a time-effective method of proving primality? Apply PolySolv with $f(x)=x^{1738}-1, m=1739$. After determining the number of roots of $f$, can you deduce that $m$ is composite? (Recall Euler's Theorem Theorem 2.8 of NZM.) Is this a time-effective method of proving compositeness?

Problem 7

Let $p=101$, say, and consider $f$ of the form $f(x)=x^{3}+a x^{2}+b x+c$. For various randomly-selected triples $a, b, c$ use PolySolv to determine the value of $N_{f}(101)$. Formulate a conjecture regarding the average number of solutions of a polynomial congruence modulo a prime $p$, when $p$ is fixed and the polynomial runs over all monic polynomials of some given degree. (A polynomial is monic if its leading coefficient is 1.) Can you prove your conjecture?

Problem 8

Let $f$ be defined as in Problem 2 above. Suppose that $p$ is a prime such that $N_{f}(p)=2$, and that $q$ is a prime such that $N_{f}(q)=3$ (for example $p = 31$ and $q = 47$). Use PolySolv to determine the value of $N_{f}(p q)$. Try some further examples of this kind. Formulate a conjecture concerning the relationship between $N_{f}(m), N_{f}(n)$, and $N_{f}(m n)$ when $\gcd(m, n)=1$. (This conjecture is established as Theorem 2.20 in NZM, as an application of the Chinese Remainder Theorem.)

Problem 9

Suppose that $p \nmid x$. Explain why $x^{(p-1) / 2} \equiv \pm 1 (\bmod p)$. For how many $x$ does the $+$ sign occur? Take $f(x)=x^{(p-1) / 2}-1$ in PolySolv. Try this for several values of $p$. Formulate a conjecture. (This conjecture can be derived as an application of the more general Theorem 2.37 of NZM.)

Problem 10

The program PascalsT displays the entries of Pascal's Triangle (i.e., binomial coefficients), reduced $(\bmod m)$. Start with $m=2$. The pattern created by rows $0-3$ is repeated twice in rows $4-7$, with an inverted triangle of 0 's between. Does this generalize? How would you express this in terms of equations?

Problem 11

For $0 \leq n \leq 15$, count the number of odd entries in the $n$-th row of Pascal's triangle. (Take $m=2$ in PascalsT.) The totals that arise in this way form a special class of integers. Describe it.

Problem 12

When $n$ is written in binary, the number of ones in the expansion is called the binary weight of $n$, and is denoted $w(n)$. That is, if $n=2^{i_{1}}+2^{i_{2}}+\cdots+2^{i_{k}}$ with $0 \leq i_{1}<i_{2}<$ $\cdots i_{k}$ then $w(n)=k$. Compute $w(n)$ for $0 \leq n \leq 15$. Note the relation between these values, and the totals computed in the preceding problem. Form a conjecture. (Problem 16 at the end of $\S 2.2$ of NZM is relevant here.)

Problem 13

Let $p$ be a prime number. What is the least $n$ such that $p \mid \binom{n}{k}$ for all $k$ in the range $0<k<n$ ? (Take $m=p$ in PascalsT, and look for zeros.) What is the second such $n$ ? The third? (Problem 14 at the end of $\S 2.2$ of NZM is relevant here.)

Problem 14

For what $k, 0 \leq k \leq 15$, is it true that $3 \nmid\binom{15}{k}$ ? For what $k, 0 \leq k \leq 15$, is it true that $5 \times\binom{ 15}{k}$ ? Does this suggest something?

Problem 15

Let $p$ be a prime number. Describe all the patterns that you can find in the sequence of residues $\binom{n}{p}\left(\bmod p^{2}\right)$.