Undergrad Question on Primitive Roots and GCDs

[Albert01]

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$?

 

[martinbn]

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:

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.

• 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?

 

[Albert01]

Hi @martinbn,

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)?