# Exercise 11 of section 3.2.2(The art of computer programming)

a) If $$f(z),\space a(z),\space b(z)$$ are polynomials with integer coefficients, let us write $$a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$$ if $$a(z) = b(z) + f(z)u(z) + mv(z)$$. Prove that the following statement holds when $$p^e>2$$ (p prime) , $$f(0)=1$$:

If $$z^\lambda \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e})$$ and $$z^\lambda \not\equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})$$ then $$z^{p\lambda} \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})\space but\space z^{p\lambda} \not\equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+2})$$

Here's my reasoning:
We have $$z^\lambda$$ has the form of $$f(z)u(z) + p^ev(z) + 1$$ where $$p^{e+1}|f(z)u(z),f(z)|p^ev(z)$$ and $$v(z)\not\equiv 0(\operatorname{mod} p)$$ (*)
Or we can just simplify it as: $$z^\lambda = Z + 1$$, where Z is a multiple of $$f(z)$$ and $$p^e$$ but not $$p^{e+1}$$'s one. So:$$z^{p\lambda} = 1+{p\choose 1}Z+{p\choose 2}Z^2+...$$
$$z^{p\lambda}-1$$ is certainly divisable by f(z). Also, we can see that $${p\choose k}Z^k(1\leqslant k\leqslant p-1)$$ is a multiple of $$p^{e+1}$$ and $$p^{e+2}|Z^p$$(due to the fact $$p^e>2$$,$$p^{pe}|Z^p$$ implies $$p^{e+2}|Z^p$$). We now can conclude: $$z^{p\lambda} \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e+1})$$

Next, it's easy to establish: $$p^{e+2}|p^{(e+1)k}$$,where $$k\geqslant$$ 2. And that shows: $$z^{p\lambda} \equiv 1 + p^{e+1}v(z) (\operatorname{mod} p^{e+2}\space and\space f(z))$$ Due to (*),$$1+ p^{e+1}v(z) \not\equiv 1(\operatorname{mod} p^{e+2})$$, completing the proof

My proof is based on the answer of excercise 11. And the difference between it and mine makes me confused.

If $$p^{e+1}v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p^{e+2})$$, there must exist $$a(z)$$ and $$b(z)$$ such that $$p^{e+1}(v(z) +pa(z)) = f(z)b(z)$$. Since $$f(0)=1$$, this implies $$p^{e+1}|b(z)$$(by Guass's lemma 4.6.1G); hence $$v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p)$$, a contradiction.

So, my questions are:
1. Why is the above argument necessary?
2. Is the Gauss's lemma 4.6.1G the one in wikipedia?

• It is common to add a space after punctuation marks. – Yuval Filmus Jun 9 at 10:23

We have $$z^\lambda$$ has the form of $$f(z)u(z) + p^ev(z) + 1$$ where $$p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$$ and $$v(z)\not\equiv 0\pmod p\$$ (*)

You misunderstood the definition of $$a(z)\equiv b(z)\pmod {f(z)\text { and }m}$$. If $$z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$ for some $$u(z), v(z)$$. There is no further requirement on $$u(z)$$ and $$v(z)$$. It is incorrect to deduce $$p^{e+1}\mid f(z)u(z)$$. It is incorrect to deduce $$f(z)\mid p^ev(z)$$.

However, if we also have $$z^\lambda \not\equiv 1 \pmod{ f(z)\text{ and }p^{e+1}}$$, then we must have $$v(z) \not\equiv 1 \pmod{ f(z)\text{ and }p}.$$

Why is the above argument necessary?

Now that you can understand the notation correctly, you can figure it out by yourself.

Is the Gauss's lemma 4.6.1G the one in Wikipedia?

Yes, lemma 4.6.1G in the book is the same as the Gauss's lemma on Wikipedia.

• As i understand, Gauss's lemma is about irreducibility of a polynomial. It also points out the definition of primitive polynomials which i think it is enough to follow the proof. Due to $f(0)=1$,$f(z)$ should be a primitive polynomial with its constant equals 1. So, $p^{e+1}$ relatively prime to $f(z)$,leading to $p^{e+1}|b(z)$. Do i misunderstand again? – MathematicsBeginner Jun 10 at 9:32
• You got it. As shown on that Wikipedia article, $\Bbb Z[x]$ is a unique factorization domain (UFD) because of $\Bbb Z$ is a UFD. – Apass.Jack Jun 10 at 9:47