# MAT 338 Day 10 2011

## 2661 days ago by kcrisman

We have seen some neat stuff regarding $\mathbb{Z}_p$ now!  And there will be a lot more to come.   Today, we wrap up some preliminary ideas, so that we can forge ahead into specific questions about $\mathbb{Z}_p$ soon.  The midterm is scheduled for Wednesday, by the way; it would be on all the preliminary ideas and algorithms we've discussed, whether it's Wednesday or Friday.

One homework question was to show that Wilson's theorem fails for $p=10$.  That is, that $(10-1)!\not\equiv -1$ mod ($10$).  So does it work or not for other moduli?

@interact def _(n=range_slider(2,100,1,(3,9))): for modulus in [n[0]..n[1]]: html("$(%s-1)!\equiv %s$ mod $(%s)$"%(modulus,mod(factorial(modulus-1),modulus),modulus))

## Click to the left again to hide and once more to show the dynamic interactive window

Recall your proof thing from last time.  The idea was to prove Fermat's Little Theorem, that if $gcd(a,p)=1$ for $p$ a prime, then $$a^{p-1}\equiv 1\text{ mod }(p)\, .$$

• Prove: If $gcd(a,p)=1$ and $p$ is prime, show that $\{a,2a,3a,\ldots,(p-1)a,pa\}$ is a complete residue system mod ($p$).  That is, show that the set $\{[a],[2a],[3a],\ldots,[pa]\}$ is the whole set $\{[0],[1],[2],\ldots,[p-1]\}$, though of course in a different order!
• Prove: If $p$ is prime and $p$ does not divide $a$, then $$a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ mod }(p)\, .$$
• Use these (with or without Wilson's Theorem) to prove our conjectured theorem!

You should keep trying to do this.

Next up is our question of how many solutions there are to $x^2-1\equiv 0$ mod ($n$) for arbitrary $n$.

@interact def _(n=(12,[10..110])): counter = 0 html("Values of $x^2-1$ mod %s"%(n,)) html("<ul>") for m in [0..n]: html("<li>$%s^2-1\equiv %s\\text{ mod }(%s)$"%(m,mod(m,n)^2-1,n)) if mod(m,n)^2-1==0: counter += 1 html("</ul>") html("There are $%s$ solutions to $x^2-1\equiv 0$ mod ($%s$)."%(counter,n))

## Click to the left again to hide and once more to show the dynamic interactive window

It turns out that there is a really neat answer to this question.  We can compute it with the help of this important corollary to the CRT, which we have alluded to before:

• Let $n_1,n_2,\cdots ,n_k$ be a set of $k$ moduli, all of which are relatively prime to each other.  Suppose that for some polynomial $f(x)$ you know that there are $N_i$ (congruence classes of) solutions to $$f(x)\equiv 0 \text{ mod }(n_i)\; .$$  Then the congruence $$f(x)\equiv 0 \text{ mod }\left(\prod_{i=1}^k n_i\right)\text{ has }\prod_{i=1}^k N_i\text{ total solutions.}$$

For instance, if $f(x)\equiv 0$ has 2 solutions modulo 3, 1 solution modulo 5, and 3 solutions modulo 7, it would have $2\cdot 1\cdot 3=6$ solutions modulo 105.

The proof is essentially that each set $a_1,a_2,\cdots a_k$ of solutions of $$f(x)\equiv 0\text{ mod }(n_i)$$ gives exactly one solution to $$f(x)\equiv 0\text{ mod }\left(\prod_{i=1}^k n_i\right)\; .$$  The Chinese Remainder Theorem says so.  In that case, we simply multiply how many there are for each $n_i$ to get the total number of combinations of solutions for individual $n_i$, and that gives $\prod_{i=1}^k N_i$.  There aren't any additional answers, because any answer to the 'big' congruence automatically also satisfies the 'little' ones, since if $\prod_{i=1}^k n_i|f(a)$, then certainly $n_i|f(a)$ as well.

As a result, if you want to get the total number of solutions of $f(x)\equiv 0\text{ mod }(n)$, then the best thing to do is write $n$ as a product of prime powers $n=\prod_{i=1}^k p_i^{e_i}$, find out how many solutions $N_i$ each prime power modulus congruence $f(x)\equiv 0$ mod ($p_i^{e_i}$) has, and then get as your final solution $N=\prod_{i=1}^k N_i$ total solutions modulo $n$.

That means that the Chinese Remainder Theorem has reduced our work needed in solving polynomial congruences modulo $n$ to finding solutions modulo each prime power divisor of $n$, and as a bonus it has also made it easier to count such solutions if we only need to know the number, not the actual solutions themselves!

So now we can answer the question about $x^2-1$.  As you all noted, $p|(x-1)(x+1)$ implies $x\equiv \pm 1$ mod ($p$).  But in fact, this is also (almost) true for any prime power $p^e$; $p^e|(x-1)(x+1)$ implies $p$ divides $x-1$ or $x+1$, and so all the factors of $p$ need to divide this one.  That is, $p^e|(x+1)$ or $p^e |(x-1)$, and the powers of $p$ are not spread out between $x+1$ and $x-1$.

The only time this isn't true is if it's possible for $p$ to divide both $x-1$ and $x+1$, which is the case precisely when $p=2$.  As it turns out, we know that $\pm 1$ are still the only solutions for $2^1$ (where $+1\equiv -1$) and $2^2$.

However, for $2^3$ it's possible that $2|(x+1)$ and $2^2|(x-1)$, or vice versa, so that $2^2\pm 1$ are also solutions to the congruence.  For higher powers of $2$ this can happen, too - for instance, one could have $2|(x+1)$ and $2^4|(x-1)$.  However, it's not possible that $2^2|(x+1)$ and $2^3|(x-1)$ because numbers two apart can't both be divisible by four, so this is the only other thing that can happen.

That means we get a very intriguing answer, based on the number $k$ of odd primes that divide $n$!

• There are $2^k$ solutions if $n$ is odd.
• There are $2^k$ solutions if $n$ is divisible by 2 but not by 4 (if $n\equiv 2$ mod ($4$))
• There are $2^{k+1}$ solutions if $n$ is divisible by 4 but not by 8 (if $n\equiv 4$ mod ($8$) but $n\equiv 0$ mod ($4$))
• There are $2^{k+2}$ solutions if $n$ is divisible by 8.

The book notates this slightly differently, but I like this way of thinking about it.

There are two morals to this:

• Finding solutions to prime power congruences is really important!
• Sometimes solutions themselves can be expressed in terms of congruences.

Both of these things will come back again and again.

So how do we deal with prime power congruences?  This is a non-trivial subject!  However, because we will be focusing (in this class) on the already plenty interesting subject of $\mathbb{Z}_p$, I will only put in one tidbit of the lore of prime powers.

Let $f(x)=2x-3$.  The only solution of $2x\equiv 3$ mod (5) is clear - it is $x=[4]$.  How might we get solutions mod (25) from this?  Here are some steps.

• Any solution of $2x\equiv 3$ mod ($5^2$) is also a solution of $2x\equiv 3$ mod (5).
• So $x\equiv 4+5k$ mod (25) for some $k$, since $[4]=\{4+5k|k\in\mathbb{Z}\}$.
• Plugging this in the congruence yields $$2x\equiv 2(4+5k)\equiv 2\cdot 4+2\cdot 5k\equiv 3\text{ mod (25),}$$ or, rearranging (but keeping everything unmultiplied), $$3-2\cdot 4\equiv 2\cdot 5k\text{ mod }(5^2)\, .$$
• Now, we know that $5\mid 3-2\cdot 4$, because we already know that $3\equiv 2\cdot 4$ mod (5) solved our original congruence.  So we can cancel out $5$ from the entire congruence to get that $$\frac{3-2\cdot 4}{5}\equiv 2k\text{ mod (5)}\; .$$
• This simplifies to $-1\equiv 2k$ mod (5), which has solution $k\equiv 2$ mod (5).
• Hence, using this $k$ and plugging it back in to get a solution to $2x\equiv 3$ mod ($5^2$), we get $$4+5k=4+5\cdot 2=14\text{ mod }(5^2)$$ as the solution.
• And indeed $2\cdot 14=28\equiv 3$ mod ($25$).  !

Now, that was a lot. If you do it again, shorter, to get to $5^3$, it looks like this:

• I already know that $[14]$ is the solution to $2x\equiv 3$ mod ($5^2$).
• That means that a solution to $2x\equiv 3$ mod ($5^3$) must look like $14+5^2 k$.
• Plugging this in gives me $2(14+5^2 k)\equiv 3$ mod ($5^3$), which rearranges to $$2\cdot 5^2 k \equiv 3-2\cdot 14\text{ mod }(5^3)\; .$$
• Since we know that $14$ solves $2x\equiv 3$ mod ($5^2$), that means (by definition of congruence) that $$5^2|3-2\cdot 14\; ,$$ so we can divide "all three sides" of the last congruence by $5^2$.
• This yields $$2k\equiv \frac{3-2\cdot 14}{5^2}\equiv \frac{-25}{5^2}\equiv -1\text{ mod }(5)\; .$$
• Solving this yields, of course, $k\equiv 2$ mod (5), so $$x\equiv 14+5^2 \cdot 2\equiv 64\text{ mod }(125)\; ,$$ and indeed $2\cdot 64=128\equiv 3$ mod (125) works.

You can do this as often as you like, and (properly interpreted) it will yield all solutions of your congruence modulo $p^e$, one step at a time.  In general, we have this basic form of:

Hensel's Lemma: Suppose you already know that any solution of $$f(x)\equiv 0\text{ mod }\left(p^{e-1}\right)$$ looks like $$x_{e-1}\text{ mod }\left(p^{e-1}\right)\; .$$  Then any solution to $$f(x)\equiv 0\text{ mod }\left(p^e\right)$$ looks like $$x_{e}=x_{e-1}+kp^{e-1}\; .$$  In fact, $k$ will be a number such that $$\frac{f(x_{e-1})}{p^{e-1}}+k\cdot f'(x_{e-1})\equiv 0\text{ mod (}p\text{)}\, .$$  This is even interpretable as Newton's method, e.g. $$x_{e}=x_{e-1}-\frac{f(x_{e-1})}{f'(x_{e-1})}$$ since $p^{e-1}\mid f(x_{e-1})$ and $f'(x_{e-1})$ has an inverse.   In our case, $f(x)=2x-3$, so $f'(x)=2$ and it wasn't as obvious that was involved.

Anyway, this certainly further finishes us, having gone from composite numbers to prime powers, and now to just primes, for moduli.  Our final thing for the day finishes off our discussion of solutions of polynomial congruences, and again confirms our reliance on primes.

Lagrange's Theorem:

If $p$ is prime and $f(x)$ is a non-trivial polynomial with integer coefficients of degree $d$, then there are at most $d$ congruence classes of solutions modulo $p$.

We already saw this wasn't true for general moduli - we got as many as $2^{k+2}$ solutions to $x^2-1\equiv 0$ for moduli that looked like $8p_1 p_2\cdots p_k$, after all.

In any case, this means that whatever the solution to the $x^2\pm 1$ problems are mod ($p$), there cannot be more than 2 solutions to them there!  Which means if we have solutions, we have all of them.

Of course, we also might not get all two solutions, as we can see here...

@interact def _(n=(13,prime_range(100))): counter = 0 html("Zero values of $x^2+1$ mod %s"%(n,)) html("<ul>") for m in [0..n-1]: if mod(m,n)^2+1==0: html("<li>$%s^2+1\equiv %s\\text{ mod }(%s)$"%(m,mod(m,n)^2+1,n)) counter += 1 html("</ul>") html("There are $%s$ solutions to $x^2+1\equiv 0$ mod ($%s$)."%(counter,n))

## Click to the left again to hide and once more to show the dynamic interactive window

Proof:

• If there are no solutions to $f(x)\equiv 0$ mod ($p$), then there is nothing further to prove, since $0\leq d$ for any polynomial.  This is certainly the case if the degree is $d=0$ and $f(x)=c$ for $c\neq 0$.  (If $c=0$, of course, you have the trivial polynomial, which is not a covered case.)
• Suppose that the degree $d=1$.  Then we have $ax+b\equiv 0$ mod ($p$), which is the same as $ax\equiv -b$ mod ($p$), which we already know cannot have more than one solution since $gcd(a,p)=1$ if $ax+b$ is actually going to have a linear term (otherwise $p|a$).
• Now we'll use some induction.
• Let's assume that all polynomials with degree $e$ less than $d$ have at most $e$ solutions modulo $p$.
• So assume that $f$ has degree $d$, i.e. $$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\; .$$
• We already dealt with the case where $f$ has no solutions, so assume that $f(b)\equiv 0$ mod ($p$) for at least one congruence class $[b]$.
• Remember the factorization $$\left(x^k-b^k\right)=(x-b)\left(x^{k-1}+\cdots+b^{k-1}\right)$$ which we used when we proved that exponentiation was well-defined in modular arithmetic.
• Now let's apply that to $$f(x)-f(b)\equiv f(x)\equiv$$ $$\left(a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0\right)-\left(a_d b^d+a_{d-1}b^{d-1}+\cdots +a_1 b+a_0\right)=$$ $$a_d\left(x^d-b^d\right)+a_{d-1}\left(x^{d-1}-b^{d-1}\right)+\cdots +a_1(x-b)$$ to get $$(x-b)\cdot \left(\text{A bunch of stuff, but factored out - and hence lower degree!}\right)\; .$$
• Hence the condition that $f(x)\equiv 0$ can be written in two ways, recalling that $f(b)\equiv 0$:
• $f(x)\equiv 0$
• $f(x)\equiv f(x)-f(b)\equiv (x-b)\cdot \text{Stuff}(x)$
• Since the 'Stuff' function must have lower degree, we can assume there are at most $d-1$ solutions to it modulo $p$.
• Therefore $$f(x)\equiv (x-b)\cdot \text{Stuff}(x)\equiv 0\text{ mod }(p)$$ implies that $p$ divides the product of $x-b$ and the stuff.  There are at most $d-1$ ways to divide the Stuff, and only one extra way to divide $x-b$, so there are at most $d$ solutions available, including $b$, which proves it works for $f$.
• But $f(x)$ was an arbitrary polynomial of degree $d$, so it works for all polynomials of degree $d$.
• So by induction, it works for any polynomial.

Handed-in Homework for Monday, but from Friday:

1. Solve:
• $18x\equiv 42$ mod ($50$)
• $6x\equiv 3$ mod ($9$)
• $980x \equiv 1540$ mod ($1600$)
2. When eggs in a basket are removed two, three, four, five, or six at a time, there remain, respectively, one, two, three, four, or five eggs.  When they are taken out seven at a time, none are left over.  Find the smallest number of eggs that could have been contained in the basket.  (Brahmagupta, 7th century AD)
3. Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.
4. Show that the system of congruences $$x\equiv a\text{ mod }(m)$$ $$x\equiv b\text{ mod }(n)$$ has a solution precisely if $gcd(m,n)|(a-b)$.
5. Use our conjectured theorem about $a^{p-1}$ mod ($p$) to help you calculate each of the following very quickly:
• $512^{372}$ mod (13)
• $3444^{3233}$ mod (17)
• $123^{456}$ mod (23)
6. Write out the multiplication table for $\mathbb{Z}_7$ completely, by hand.
7. Show that Wilson's Theorem fails for $p=10$ and check that it works for $p=11$ by hand.
8. Do exploration to try to find a criterion for which primes $p$ there are square roots of $-1$.  You will have to examine primes less than 10 by hand to make sure you are right!
9. Do exploration to find out anything you can about how many square roots of $1$ there are for a given $n$.
10. Prove our conjectured theorem that $a^{p-1}\equiv 1$ mod ($p$), in three steps:
• Prove: If $gcd(a,p)=1$ and $p$ is prime, show that $\{a,2a,3a,\ldots,(p-1)a,pa\}$ is a complete residue system mod ($p$).  That is, show that the set $\{[a],[2a],[3a],\ldots,[pa]\}$ is the whole set $\{[0],[1],[2],\ldots,[p-1]\}$, though of course in a different order!
• Prove: If $p$ is prime and $p$ does not divide $a$, then $$a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ mod }(p)\, .$$
• Use these (with or without Wilson's Theorem) to finish the proof.

Things to think about as well, which are not due, but things similar to which could be on the exam.

1. Prove that Wilson's Theorem fails if the modulus is not prime.  Hint: use the fact that the modulus $n$ then has factors $m$ other than $1$ or $n$.
2. Keep on trying to figure out the pattern (if there is one) for square roots of negative one modulo a prime.  We now know there can be at most two!
3. Do Exercise 3.13 and 3.17, using our CRT strategy above.
4. Find out how many solutions $x^3+x^2+x+1\equiv 0$ mod ($n$) has using the same idea, for $n=8,15,24,40,120$.
5. Find solutions to $3x-4\equiv 0$ mod ($343$) and $x^2+8\equiv 0$ mod ($121$) using the method above (Hensel's Lemma).
6. Do Exercise 4.16.