1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\text {gcd} (q-1,N) = ?$ $\endgroup$ – Dbchatto67 Mar 31 at 13:17
  • $\begingroup$ @Dbchatto67 - $\text{gcd}$ is a very common notation for the greatest common divisor function. $\endgroup$ – Paul Sinclair Mar 31 at 21:15
  • 1
    $\begingroup$ 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$. $\endgroup$ – Paul Sinclair Mar 31 at 21:21
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ (+) Nice and perfect answer. I like it. $\endgroup$ – user0410 Mar 31 at 22:22
  • 1
    $\begingroup$ @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. $\endgroup$ – John Omielan Mar 31 at 22:27
  • $\begingroup$ You are not just a user, but a good teacher. I appreciate your description. $\endgroup$ – user0410 Mar 31 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.