Congruences

note

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

Problem 1

The program CngArTab displays the addition and multiplication tables of congruence arithmetic. After entering an initial modulus $n$. invertible residue classes are displayed in white, to aid in distinguishing them from non-invertible residue classes, in yellow. In the multiplication table, which rows constitute a complete residue system (each residue once and only once)? Refer to Theorem 2.6 of NZM.

Problem 2

If two invertible residue classes are multiplied, is their product necessarily a invertible residue class? Experiment, and recall Theorem 1.8 of NZM.

Problem 3

When viewing the multiplication table, the display can be restricted to the invertible residue classes by hitting the checkbox. Try this with $n=15$, for example. Do the numbers in a given row of the table constitute a system of invertible residues? Refer again to Theorem 2.6 of NZM. Try this also with $n=91$, and note the location of the gaps in the invertible residues.

Problem 4

Take $n=35$ in CngArTab. For which $a (\bmod 35)$ does there exist an $x$ such that $a x \equiv 1 (\bmod 35) ?$ That is, in which rows of the multiplication table do you see a 1? Is there any row containing more than one 1? (Numbers in the first column don't count.) Refer to Theorem 2.9 of NZM.

Problem 5

Use the program PowerTab to investigate the following questions. For which values of $a(\bmod n)$ is the sequence $a^{0}, a^{1}, a^{2}, \ldots(\bmod n)$ eventually periodic? Purely periodic? Try all values of $a$ for several moduli (say $n=4,5,6,7$ ), and note the results. Formulate conjectures concerning the general situation. How does the behavior for prime $n$ differ from composite $n$? Is the value of $\gcd (a, n)$ relevant? For now you can assume that PowerTab computes the powers of $a(\bmod n)$ sequentially. Actually, this program can skip forward to calculate $a^{k}(\bmod n)$ quickly, without determining the intervening powers.

Problem 6

The number of invertible residue classes (mod $n$ ) is called $\phi(n)$. (See pp. 50, 51 of NZM.) Determine the value of $\phi(91)$ by the following method: There are precisely 13 numbers $a, 0 \leq a<91$ such that $7 \mid a$. Similarly, there are precisely 7 numbers $a$, $0 \leq a<91$ for which $13 \mid a$, and precisely 1 number $a, 0 \leq a<91$ for which both $7 \mid a$ and $13 \mid a$. Hence $\phi(91)=91-13-7+1=72$. By using CngArTab to view the multiplication table (mod 91) with only invertible residues displayed, you can confirm that this calculation is correct. More generally, if $n=p_{1} p_{2}$ where $p_{1}$ and $p_{2}$ are distinct primes, then $\phi(n)=n-n / p_{1}-n / p_{2}+1=n\left(1-1 / p_{1}\right)\left(1-1 / p_{2}\right)$. This approach can be extended to numbers with more prime factors, by means of the principle of Inclusion-Exclusion (see pp. 209, 210 of NZM). Use PowerTab to view the powers of $b$, invertible modulo 91 . Note that $b^{72} \equiv 1(\bmod 91)$ whenever $\gcd (b, 91)=1$, as predicted by Euler's Theorem (Theorem 2.8 of NZM). Is there a smaller exponent with this same property?

Problem 7

The program FctrlTab generates a table of the numbers $k!(\bmod n)$. Use FctrlTab to view the factorials modulo 345345 . What is the least $k$ such that $k!\equiv 0(\bmod 345345)$ ? Is it necessarily the case that $\gcd (k, 345345)>1$ ? Use Factor to determine the factorizations of $k$ and of 345345. Use FctrlTab to view the factorials $(\bmod p)$ for several prime numbers $p$. Is there any pattern exhibited by $(p-1)!(\bmod p)$ ? By $(p-2)!(\bmod p)$ ? By $(p-3)$ ! $(\bmod p)$ ? Formulate conjectures. Can you prove that each one of these conjectures implies the others? See Wilson's Theorem (Theorem 2.11 of NZM).

Problem 8

For each integer $n$ let $k(n)$ denote the least positive integer $k$ such that $k! \equiv 0 (\bmod n)$. Clearly $k(p)=p$ if $p$ is prime. If $n$ is composite then $k(n)$ is smaller. How much smaller? Is it usually small? Is it usually large? Does it oscillate a lot? Use FctrlTab to determine $k(n)$ for several values of $n$, and interpret your findings.

Problem 9

The program PolySolv allows you to define a polynomial $f(x)$, and then find the roots of the congruence $f(x) \equiv 0 (\bmod n)$. The program runs rather slowly when $n$ is large, since $f(a)$ is evaluated $(\bmod n)$ for every $a, 0 \leq a<n$. Use PolySolv to find the roots of $x^{2} \equiv 1(\bmod p)$ for several small primes $p$, and note that the results conform to Lemma 2.10 of NZM.