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 $(101)!\not\equiv 1$ mod ($10$). So does it work or not for other moduli?
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^{p1}\equiv 1\text{ mod }(p)\, .$$
You should keep trying to do this.
Next up is our question of how many solutions there are to $x^21\equiv 0$ mod ($n$) for arbitrary $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:
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_if(a)$, then certainly $n_if(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^21$. As you all noted, $p(x1)(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(x1)(x+1)$ implies $p$ divides $x1$ or $x+1$, and so all the factors of $p$ need to divide this one. That is, $p^e(x+1)$ or $p^e (x1)$, and the powers of $p$ are not spread out between $x+1$ and $x1$.
The only time this isn't true is if it's possible for $p$ to divide both $x1$ 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(x1)$, 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(x1)$. However, it's not possible that $2^2(x+1)$ and $2^3(x1)$ 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$!
The book notates this slightly differently, but I like this way of thinking about it.
There are two morals to this:
Both of these things will come back again and again.
So how do we deal with prime power congruences? This is a nontrivial 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)=2x3$. 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.
Now, that was a lot. If you do it again, shorter, to get to $5^3$, it looks like this:
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^{e1}\right)$$ looks like $$x_{e1}\text{ mod }\left(p^{e1}\right)\; .$$ Then any solution to $$f(x)\equiv 0\text{ mod }\left(p^e\right)$$ looks like $$x_{e}=x_{e1}+kp^{e1}\; .$$ In fact, $k$ will be a number such that $$\frac{f(x_{e1})}{p^{e1}}+k\cdot f'(x_{e1})\equiv 0\text{ mod (}p\text{)}\, .$$ This is even interpretable as Newton's method, e.g. $$x_{e}=x_{e1}\frac{f(x_{e1})}{f'(x_{e1})}$$ since $p^{e1}\mid f(x_{e1})$ and $f'(x_{e1})$ has an inverse. In our case, $f(x)=2x3$, 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 nontrivial 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^21\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...
Click to the left again to hide and once more to show the dynamic interactive window 
Proof:
Handedin Homework for Monday, but from Friday:
Things to think about as well, which are not due, but things similar to which could be on the exam.
