Question on invertibility in finite fields

  • #1
Albert01
12
0
Hello all,

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

1693031347473.png


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.
 
Physics news on Phys.org
  • #2
Albert01 said:
1.) If ##n## divides ##p-1##, why does this imply that ##n## is invertible?
Because then ##p## cannot divide ##n##.
Albert01 said:
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.
 
  • Like
Likes Albert01
  • #3
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.##
 
  • Love
Likes Albert01
  • #4
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?
 
  • #5
Albert01 said:
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##.
Albert01 said:
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.##)
 

Similar threads

  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
702
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
780
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
2
Replies
43
Views
5K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Advanced Physics Homework Help
Replies
5
Views
1K
  • General Engineering
Replies
3
Views
988
  • Calculus and Beyond Homework Help
Replies
8
Views
4K
Back
Top