Question on invertibility in finite fields

[Albert01]

Hello all,

I have here an excerpt from Wikipedia about the discrete Fourier transform:

My question(s) are about the red underlined part.

1.) If ##n## divides ##p-1##, why does this imply that ##n## is invertible?
2.) Why does Wikipedia take the effort to write out the ##n## as ##n = 1+1+...+1##, what is behind this?

I would be glad if someone could help me a little bit here.

 

[martinbn]

1.) If ##n## divides ##p-1##, why does this imply that ##n## is invertible?

Because then ##p## cannot divide ##n##.

2.) Why does Wikipedia take the effort to write out the ##n## as ##n = 1+1+...+1##, what is behind this?

That is the definition of ##n## in a field.

 

[fresh_42]

If you already accept that ##GF(q)=GF(p^m)## is a field, then all elements except zero are invertible. And zero in a field of characteristic ##p## is
$$
0=\underbrace{1+1+\ldots+1}_{p\text{ times}}
$$
Now consider any natural number ##n,## as @martinbn mentioned, defined as
$$
n=\underbrace{1+1+\ldots+1}_{n\text{ times}}
$$
and assume ##n=k\cdot p.## Then
$$
n=\underbrace{\underbrace{1+1+\ldots+1}_{p\text{ times }=0}+\underbrace{1+1+\ldots+1}_{p\text{ times }=0}+\ldots+\underbrace{1+1+\ldots+1}_{p\text{ times }=0}}_{k\text{ times }=0}=0
$$
and all other numbers are unequal zero modulo ##p## hence invertible. The Euclidean algorithm allows us to write
$$
n=r\cdot p + s\qquad , \qquad 0<s<p
$$
if ##p## does not divide ##n## so ##n\equiv s \neq 0 \pmod{p}## and as @martinbn mentioned, ##n<p## prevents that ##p\,|\,n## or ##s=0.## Furthermore, ##n## and ##p## are coprime, i.e. their greatest common divisor is ##1.## This means by Bézout's identity that we can write
$$
1=a \cdot n + b \cdot p \quad \text{ or }\quad a\cdot n \equiv 1\pmod{p}
$$
and ##a## is the inverse of ##n## modulo ##p.##

 

[Albert01]

Thank you for the very good answer!

A few questions:
1.) Why can we assume ##n=kp##? You only do this here as an example to show the difference between ##n = kp## and ##n = rp + s##, right?

2) The inequality ##n < p## is due to the fact that all elements in the field are smaller than ##p##, right?

 

[fresh_42]

Thank you for the very good answer!

A few questions:
1.) Why can we assume ##n=kp##? You only do this here as an example to show the difference between ##n = kp## and ##n = rp + s##, right?

Yes. I assumed ##n=kp## to show why multiples of ##p## do not have an inverse modulo ##p##.

2) The inequality ##n < p## is due to the fact that all elements in the field are smaller than ##p##, right?

That was a misunderstanding on my side. All we need is ##p\,\nmid \,n##.
(If ##p\,|\,n## and ##n\,|\,(q-1)=p^m-1## then ##p\,|\,(p^m-1)## which is impossible. Thus ##p\,\nmid \,n.##)