4
$\begingroup$

Does anyone know how to prove that $\dfrac{q^n -1}{(q-1)\gcd(n,q-1)}$ is an integer for $q = p^k$, $p$ prime using only basic algebra?

It is possible to show this by showing that there is a subgroup $C$ of $\mathbb{F}_{q^n}^*$ such that $ \#C = (q-1)\gcd(n,q-1)$, but is it possible to find a simpler proof?

$\endgroup$

1 Answer 1

4
$\begingroup$

In modulo $\gcd(n,q-1)$ we have:

\begin{align*} \frac{q^n-1}{q-1} & = q^{n-1} + \cdots + q + 1 \\ & = 1 + \cdots + 1 + 1 \\ & \equiv n \ \equiv \ 0 \end{align*}

$\endgroup$
5
  • 1
    $\begingroup$ is the condition $q=p^k$ necessary ? $\endgroup$
    – G Cab
    Aug 31, 2016 at 15:14
  • $\begingroup$ @GCab I haven't noticed that. Well, it seems we don't need that condition, if I am not mistaken. $\endgroup$
    – iamvegan
    Aug 31, 2016 at 15:23
  • $\begingroup$ $\gcd(q,a)=1$ with $a=\gcd(n,q-1)$? $\endgroup$
    – Maman
    Aug 31, 2016 at 16:01
  • $\begingroup$ @Maman yes. Because of its definition, in modulo $a$ we have $q-1\equiv 0$ which implies $q \equiv 1$. Hence $\gcd(q,a)=1$. $\endgroup$
    – iamvegan
    Aug 31, 2016 at 16:08
  • 1
    $\begingroup$ in fact, it seems also to me that it is superfluous: $gcd(q,q-1)=1$ for all $q$ $\endgroup$
    – G Cab
    Aug 31, 2016 at 16:36

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.