Question on Primitive Roots and GCDs

  • I
  • Thread starter Albert01
  • Start date
  • Tags
    Gcd
  • #1
Albert01
12
0
I have a question about a certain fact from the book of Nussbaumer "Fast Fourier Transform and Convolution Algorithms" in the chapter of Number-theoretic transformation. I have quoted the relevant passage once.

There it says:

##(g^t -1)S \equiv g^{Nt} - 1 \equiv 0 \text{ mod } q \quad (1)##

Thus, ##S \equiv 0## provided ##g^t - 1 \not\equiv 0 \text{ mod } q## for ##t \not\equiv 0 \text{ mod } N##. This implies that ##g## must be a root of unity of order ##N \text{ mod } q##, that is to say, ##g## must be an integer such that ##N## is the smallest nonzero integer for which ##g^N \equiv 1 \text{ mod } q##.

This quotation refers to ##q## being a prime number. But then it continues with a consideration of ##q## as a composite number. There it is stated:

Equation ##(1)## implies not only that ##g## is a root of order ##N \text{ mod } q##, but also, since ##q## is composite, that ##[(g^t-1), q] = 1##.
Questions:

  • My question is actually "only" how one comes to the conclusion that from equation ##(1)## follows ##[(g^t-1), q] = 1##, when ##q## is composite; and what benefit you get out of it.
  • A second question that follows from this would then be whether ##[(g^t-1), q] = 1## (must) hold for ##t=1,...,N-1##?
 
Physics news on Phys.org
  • #2
Albert01 said:
I have a question about a certain fact from the book of Nussbaumer "Fast Fourier Transform and Convolution Algorithms" in the chapter of Number-theoretic transformation. I have quoted the relevant passage once.

There it says:
This quotation refers to ##q## being a prime number. But then it continues with a consideration of ##q## as a composite number. There it is stated:

Albert01 said:
Questions:

  • My question is actually "only" how one comes to the conclusion that from equation ##(1)## follows ##[(g^t-1), q] = 1##, when ##q## is composite; and what benefit you get out of it.
It doesn't fillow. It is an additional requirement in oder to have the same conclusion.
Albert01 said:
  • A second question that follows from this would then be whether ##[(g^t-1), q] = 1## (must) hold for ##t=1,...,N-1##?
Isn't ##t## fixed?
 
  • #3
Hi @martinbn,

martinbn said:
It doesn't fillow. It is an additional requirement in oder to have the same conclusion.

Can you please explain this a little bit more?



If ##\text{gcd}(g^t-1,q) = 1## we can write ##(g^t-1) \cdot x + q \cdot y = 1##. On the other hand, we have ##g^t-1 \not\equiv 0 \text{ mod } q##, which we can write as ##g^t-1 \neq 0 + c \cdot q##. I don't see now how far you get to the same conclusion.



Should I add more info (to the passage from the textbook)?
 
Last edited:

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
719
  • Linear and Abstract Algebra
Replies
10
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
719
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
880
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
Back
Top