# Question about Modular Arithmetic

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.

• $\text {gcd} (q-1,N) = ?$ – Dbchatto67 Mar 31 at 13:17
• @Dbchatto67 - $\text{gcd}$ is a very common notation for the greatest common divisor function. – Paul Sinclair Mar 31 at 21:15
• No, your proof is inadequate. $q-1 \not\equiv 0 \mod N$ does not necessarily mean you can divide by $q-1$. When $N$ is composite, $\Bbb Z_N$ has zero divisors, which do not have inverses, despite not being $0$. – Paul Sinclair Mar 31 at 21:21

## 1 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}$$.

• (+) Nice and perfect answer. I like it. – user0410 Mar 31 at 22:22
• @user0410 I'm glad you liked it. I usually try to give more basic, thorough answers that try to not assume too much about what the user already knows & is familiar with. – John Omielan Mar 31 at 22:27
• You are not just a user, but a good teacher. I appreciate your description. – user0410 Mar 31 at 22:31