I 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.$)