# Congruence modulo prime power

In the book "A Classical Introduction to Modern Number Theory", I saw the following theorem (p. 43):

If $p\neq 2$, and $p\nmid a$ then $p^{l-1}$ is the order of $(1+ap)$ mod $p^l.$

i.e. $(1+ap)^{p^{l-1}}\equiv 1(\text{mod } p^{l})$, and $(1+ap)^{p^k}\not\equiv 1(\text{mod } p^l)$ for $0< k< p^{l-1}.$

The question is:

Suppose we consider the finite field $\mathbb{F}_{p^l}$ , $p\neq 2$, and take $a=1$. Then by above theorem, the multiplicative order of $(1+p)$ in $\mathbb{F}_{p^l}$ is $p^{l-1}$. But, as $1+p$ is non-zero element of the Field $\mathbb{F}_{p^l}$, so it is an element of the cyclic group $\mathbb{F}^*_{p^l}$ of order $p^l-1$, so its multiplicative order should divide $p^l-1$, and hence can not be prime power, hence the order can not be $p^{l-1}.$

What's going wrong here?

-
In fact, it is of order $p^{l-1}(p^{l}-1)$ which absolutely confirms your assertion, doesn't it? – awllower Apr 11 '11 at 12:14
By the way, it is easy to verify the congruence mentioned by you using the binomial theorem and the fact that, just as noted by one answer, the finite field is of characteristic $p$. – awllower Apr 11 '11 at 12:17
@allower: It is well known fact that the non-zero elements of a finite field form Cyclic group under multiplication. So in the field $\mathbb{F}_{p^l}$, there are $p^{l}-1$ non-zero elements, forming cyclic group of order $p^{l}-1$. – user8186 Apr 11 '11 at 12:19
@allower: Oh! OK...now its clear.....Thank you so much.... – user8186 Apr 11 '11 at 12:26
awllower: The multiplicative group of a finite field does indeed consist of all the non-zero elements. A finite field is not the integers mod some prime power. – Tobias Kildetoft Apr 11 '11 at 12:49

$\mathbb{F}_{p^l}$ has nothing to do with $\mathbb{Z}/p^l\mathbb{Z}$. When you do stuff mod $p^l$, you do stuff in the ring $\mathbb{Z}/p^l\mathbb{Z}$, whose group of invertible elements, $(\mathbb{Z}/p^l\mathbb{Z})^*$, has $\phi(p^l) = p^{l-1}(p-1)$ elements, and is not necessarily cyclic.

-
Well done, @chandok. – awllower Apr 11 '11 at 12:21
Thank you! – user8186 Apr 11 '11 at 12:26
It might be added that although the multiplicative group of $\mathbb{Z}/p^l\mathbb{Z}$ is not always cyclic, it is almost always so. It is cyclic whenever $p$ is odd or $l \leq 2$ – Tobias Kildetoft Apr 11 '11 at 13:19

The finite field $\mathbb{F}_{p^\ell}$ is not the same thing as the ring of integers modulo $p^{\ell}$! (Except in the case $\ell=1$, of course.)

To construct $\mathbb{F}_{p^\ell}$, take a root $\alpha$ of an irreducible degree $\ell$ polynomial over $\mathbb{F}_p$; then $\mathbb{F}_{p^\ell} \simeq \mathbb{F}_p(\alpha)$.

The integers modulo $p^\ell$ form a ring, not a field. Another big difference is that $\mathbb{F}_{p^\ell}$ has characteristic $p$ (so $p \alpha = 0$), but of course there are many integers $a$ such that $pa \not \equiv 0 \pmod{p^{\ell}}$.

-
Uh, are you injured, @Jonas Kibelbek? I was kidding, but it looks funny, sorry if you mind. – awllower Apr 11 '11 at 12:18
I fixed my LaTeX. My first inclination is always to write \isom instead of \simeq. (even though it hasn't worked for me yet!) – Jonas Kibelbek Apr 11 '11 at 12:26
Thank you!! – user8186 Apr 11 '11 at 12:26