0
$\begingroup$

I want to prove the following identity: $$1+\omega^{k\hspace{0.1cm}mod \hspace{ 0.1cm}d}+\omega^{(2k)\hspace{0.1cm}mod \hspace{ 0.1cm}d}+...+\omega^{[(d-1)*k]\hspace{0.1cm}mod \hspace{ 0.1cm}d}=d*\delta_{k,0}$$ where $\omega$ is $d^{th}$ root of unity and $0\leq k\leq d-1$.

By inspection I found the identity to be true but, I am still not able to prove it rigorously.

I tried to write a proof considering two cases. One in which $k$ divides $d$ and in the other one it doesn't. When $k$ doesn't divide $d$ then, the above identity reduces to: $$1++\omega+\omega^2+...+\omega^{d-1}$$ which is zero. But, when $k$ divides $d$ I am not able to prove the same. Is my approach correct? I would like to get some hints on how to approach towards proving the identity. I don't expect any complete answers as I would like to try it out myself.

$\endgroup$
  • $\begingroup$ What is $$\omega^{k\hspace{0.1cm}mod \hspace{ 0.1cm}d}$$ exactly? Do you mean $$\omega^k$$ instead? // What is an identity without equal sign? $\endgroup$ – Did Aug 20 '16 at 14:36
  • $\begingroup$ What is $\delta _{k,0}$? $\endgroup$ – MereMortal47 Aug 20 '16 at 14:46
  • 1
    $\begingroup$ @Asemismaiel: It's a Kronecker delta, which is $1$ if $k=0$ and $0$ otherwise. $\endgroup$ – Henning Makholm Aug 20 '16 at 14:49
2
$\begingroup$

As Did points out in comments, taking mod $d$ in the exponents is redundant exactly because $\omega$ is a $d$th root of unity -- we have $$ \omega^{ad+b} = (\omega^d)^a\omega^b = 1^a\omega ^b = \omega^b = \omega^{(ad+b)\bmod d} $$ for all $a\in\mathbb Z$ and $b\in\{0,1,\ldots,d-1\}$.

Your sum is therefore the same as $$ 1 + \omega^k + \cdots + \omega^{(d-1)k} = 1 + (\omega^k)^1 + \cdots + (\omega^k)^{d-1} $$ which is a geometric series with common factor $\omega^k$, so the sum is $$ \frac{1-(\omega^k)^d}{1-\omega^k} = \frac{1-(\omega^d)^k}{1-\omega^k} = \frac{1-1^k}{1-\omega^k} = 0$$ as long as $\omega^k\ne1$.


Beware that $\omega^k$ may be $1$ even for nonzero $k$ if $\omega$ is not a primitive $d$th root of unity.

$\endgroup$

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.