- #1

Albert01

- 14

- 0

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