I tried to solve this question, but realized I have no idea how to justify the intermingling of complex numbers and modular arithmetic. I know how to justify rational numbers, it is easy to realize you just treat the denominator as inverse. Is there any way to justify it?

Here is my (possibly flawed) solution:

Q: find $A \mod 101$ where $w = e^{2\pi i/10}$ and $z = e^{2\pi i/101}$: $$A=\prod _{a=0}^{9}\prod_{b=0}^{100}\prod_{c=0}^{100}(w^a+z^b+z^c)$$ For a moment consider only the last part of the product for some number: $$\prod_{c=0}^{100}(x+z^c)=\prod_{c=0}^{100}-(-x-z^c)=(-1)^{101}*\prod_{c=0}^{100}((-x)-z^c)=-((-x)^{101}-1)$$ The idea here is that the product all over roots of unity is equal $x^n-1$. By Fermat little theorem, $$-(-x^{101}-1) \equiv -(-x-1) \equiv > x+1 \pmod {101}$$ so, applying for each $w^a+z^b$: $$\prod _{a=0}^{9}\prod_{b=0}^{100}(w^a+z^b)+1$$ Again apply the same idea: $$\prod _{a=0}^{9}\prod_{b=0}^{100}(w^a+1)+z^b=\prod _{a=0}^{9}(-1)^{101}\prod_{b=0}^{100}(-w^a-1)-z^b=\prod _{a=0}^{9}-((-w^a-1)^{101}-1)\equiv \prod _{a=0}^{9}-(-w^a-1-1)= \prod _{a=0}^{9}w^a+2 \equiv 1023 \equiv 13 \mod 101$$ I'm not sure the last product is correct because I computed it with WA numerically (it give up on everything together and it is $3*10^{-12}i$ off). Edit: I computed it with all roots of unity in $C_{101}$ and got the same result.

My question is: Can we rigorously make sense of the above "solution" or complex numbers in modular arithmetic in general?

  • $\begingroup$ I would assume the notation $e^{2\pi i / 101}$ just means the 101st root of unity in $\mathbb{Z}/101\mathbb{Z}$, rather than a complex number. $\endgroup$ – mathematician May 16 '17 at 15:03
  • $\begingroup$ You can't directly apply Fermat's little theorem if $x$ isn't an integer, but you can use the fact that $x$ is an $n$th root of unity where $n$ divides $100$. $\endgroup$ – Connor Harris May 16 '17 at 15:07
  • 1
    $\begingroup$ @mathematician: there are no 101st roots of unity in $\mathbb{Z}/101 \mathbb{Z}$, because the group of units in $\mathbb{Z}/101 \mathbb{Z}$ has order 100 (in fact, it is the cyclic group of order 100, as you can see by calculating the order of $2$). $\endgroup$ – Connor Harris May 16 '17 at 15:25
  • 1
    $\begingroup$ @i9Fn You can generalize "modular arithmetic" to complex numbers; you'll just be dealing with rings of the form $\mathbb{Z}[\omega]$ instead of $\mathbb{Z}$, and taking modular residues by ideals of $\mathbb{Z}[\omega]$. This doesn't matter ultimately: the quantity we're trying to calculate is a member of $\mathbb{Z}[e^{2\pi/1010}]$ and equals its own complex conjugate, and the only elements of a cyclotomic extension of $\mathbb{Z}$ that equal their own conjugates are the integers (I believe). I've elaborated on this in my answer to the original question. $\endgroup$ – Connor Harris May 16 '17 at 17:32
  • 1
    $\begingroup$ @i9Fn So this is the same question ? Why don't you write here what is $w,z$ ? $\endgroup$ – reuns May 16 '17 at 18:03

Your Answer

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

Browse other questions tagged or ask your own question.