Question about Modular Arithmetic

91 Views Asked by At

Let $q$ be an integer number. Consider an integer number $N$ such that $\gcd(q-1,N) = 1$.

Question: How to show that if $q^d = 1 \pmod{N}$ for some positive integer $d$, then we get
$$ 1 + q + q^2 + \cdots + q^{(d-1)} = 0 \pmod N \tag{1} $$

Try: It follows from ($1$) that $$ 1 + q + q^2 + \cdots + q^{(d-1)}=\frac{q^d-1}{q-1} $$

Now the assumption $\gcd(q-1,N) = 1$ implies that $q-1\neq 0 \mod{N}$. Therefore, we get $$ \frac{q^d-1}{q-1}=\frac{1-1}{q-1}=0 \pmod{N} $$

Is the given proof correct?

Thanks for any suggestions.

1

There are 1 best solutions below

3
On BEST ANSWER

You almost have it. Note that although it's true $\gcd(q-1,N) = 1$ implies that $q-1 \not\equiv 0 \pmod{N}$, this is not sufficient. For example, if $N = 6 = 2 \times 3$, you also need to show that $q - 1 \not\equiv 2,3,4 \pmod 6$.

Given that $q^d \equiv 1 \pmod{N}$, this means that

$$q^d - 1 = kN \tag{1}\label{eq1}$$

for some integer $k$. Since $q - 1 \mid q^d - 1$, then $q - 1 \mid kN$. Since $\gcd(q-1,N) = 1$, this means no factors of $q - 1$ can divide into $N$, so $q - 1 \mid k$. Thus,

$$k = \left(q-1\right)m \tag{2}\label{eq2}$$

for some integer $m$. I trust you can finish the rest.

If you're familiar with certain number theory, note you can do this somewhat more simply using that given $\gcd(q-1,N) = 1$, then $q - 1$ has a multiplicative inverse modulo $N$. Thus, you can go directly from $q^d - 1 \equiv 0 \pmod{N}$ to $\frac{q^d - 1}{q - 1} \equiv 0 \pmod{N}$.