Linear Congruences and The Chinese Remainder Theorem

note

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

Problem 1

The program LinCon applies the extended Euclidean algorithm to find the complete solution set of the linear congruence $a x \equiv b (\bmod m)$.

You now have two methods for finding solutions of linear congruences. You can use either (i) LinCon or (ii) PolySolv. Try both methods on the congruence $2 x \equiv 1$ (mod 10000001). Which method takes longer to run? Estimate the running time for the two methods as a function of $m$. Which method is asymptotically faster?

Problem 2

Let $m$ and $n$ be given, and put $g=\gcd (m, n)$. The intersection of an arithmetic progression $a(\bmod m)$ with an arithmetic progression $b(\bmod n)$ is an arithmetic progression $(\bmod \mathrm{lcm}(m, n))$ if $a \equiv b (\bmod g)$, and is otherwise empty (Recall Problem 20 at the end of $\S 2.3$ of NZM.). The program IntAPTab presents these intersections in a manner reminiscent of the table on p. 68 of NZM. Rows are indexed by residues $a(\bmod m)$, and columns by $b(\bmod n)$. Run IntAPTab with parameters $m=5, n=8$. Note that in the body of the table, each of the numbers $0, \ldots, 39$ occurs exactly once. That is, the simultaneous congruences $x \equiv a (\bmod 5), x \equiv b (\bmod 8)$ are equivalent to the single congruence $x \equiv c (\bmod 40)$, for some suitable value of $c$. The more general assertion that this is true whenever $\gcd (m, n)=1$ is known as the Chinese Remainder Theorem (Theorem 2.18 of NZM). Take $m=101, n=103$ in IntAPTab, and take a stroll around the table. There are now so many entries that it is no easy to see, by inspection, that each number $0, \ldots, 10402$ occurs exactly once in the body of the table. Now take $m=102$, $n=104$ in IntAPTab. What proportion of the entries are blank? Why? This phenomenon becomes more pronounced when $\gcd (m, n)$ is large. Try taking $m=25, n=35$.

Problem 3

The program CRT (meaning "Chinese Remainder Theorem") determines the intersection of two given arithmetic progressions. For example, the numbers $x$ such that both $x \equiv 3(\bmod 4)$ and $x \equiv 2(\bmod 5)$ are precisely the numbers for which $x \equiv 7$ $(\bmod 20)$. Run CRT with suitable parameters and watch the results. On the other hand, there are no $x$ for which both $x \equiv 1(\bmod 12)$ and $x \equiv 19(\bmod 28)$. To see why this is so, run CRT with suitable parameters.

Problem 4

By repeated use of CRT, find a number $x$ such that $0<x<10^{9}$ and none of $x$, $x+1$, $\ldots$, $x+6$ is squarefree. Thus we have a gap of length at least 8 between consecutive squarefree numbers. (Hint: What if $x \equiv 0(\bmod 4)$, $x \equiv-1(\bmod 9)$, $x \equiv -2 (\bmod 25)$, $x \equiv -3 (\bmod 49)$, $x \equiv -4 (\bmod 121)$, $x \equiv -5 (\bmod 169)$, $x \equiv -6 (\bmod 289)$.) Apply the program Factor to each of the numbers $x$, $x+1$, $\ldots$, $x+6$ to verify your results. Are $x-1$ and $x+7$ both squarefree?

Problem 5

Take $m=15, n=13$ in IntAPTab. Note that an entry in the body of the table is printed in White if and only both the column and row labels of that entry are printed in White. More generally, if $\gcd (m, n)=1, x \equiv a(\bmod m)$, and $x \equiv b(\bmod n)$, then $\gcd (c, m n)=1$ if and only if $\gcd (a, m)=1$ and $\gcd (b, n)=1$. Hence the number of reduced residues $(\bmod m n)$ is the number of reduced residues $(\bmod m)$ times the number of reduced residues $(\bmod n)$. That is, $\phi(m n)=\phi(m) \phi(n)$ whenever $(m, n)=1$. Since it is easy to see that $\phi\left(p^{\alpha}\right)=p^{\alpha}-p^{\alpha-1}=p^{\alpha}(1-1 / p)$, we deduce that

$$\phi(n)=\prod_{p^{\alpha} \parallel n}\left(p^{\alpha}-p^{\alpha-1}\right)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right) .$$

Thus we can calculate $\phi(n)$ easily, once the factorization of $n$ has been determined. The program Phi proceeds in this way: First the argument is factored, and then the above formula is used. Try using Phi for the input 42. You can confirm this answer by taking $m=42$ in CngArTab, and viewing the multiplication table with only the reduced residues displayed.

Problem 6

By using PolySolv, find two distinct residue classes $x_{1}$ and $x_{2}$ modulo 31 so that $x^{3}+x+1 \equiv 0 (\bmod 31)$. Similarly, find three distinct residue classes $y_{1}, y_{2}, y_{3}$ modulo 47 so that $x^{3}+x+1 \equiv 0(\bmod 47)$. By using CRT, find six residue classes $u$ modulo $31 \cdot 47=1457$ so that $u \equiv x_{i} (\bmod 31)$ and $u \equiv y_{j}(\bmod 47), i=1,2, j=1,2,3$. Apply PolySolv with $f(x)=x^{3}+x+1, m=1457$. Interpret your findings. Note the conformity of this with Theorem 2.20 in NZM.

Problem 7

Recall that the only solutions of $x^{2} \equiv 1(\bmod p)$ are $x \equiv \pm 1(\bmod p)$ (See Lemma 2.10 of NZM.). Given that $4757=67 \cdot 71$, use the program CRT to find four roots of the congruence $x^{2} \equiv 1(\bmod 4757)$. Verify your results by using PolySolv. When $m$ is composite you now have two methods for locating all the roots of a polynomial congruence $f(x) \equiv 0 (\bmod m)$. You can (i) apply PolySolv directly to the modulus $m$, or (ii) factor $m$ into primepowers, apply PolySolv to each of these primepowers, and then use CRT to combine these solutions to construct the solutions modulo m. Estimate the running time of these two approaches. Which one is faster for a typical large composite number?