3

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?

Connor Harris
  • 7,070
i9Fn
  • 496
  • 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. – mathematician May 16 '17 at 15:03
  • 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$. – Connor Harris May 16 '17 at 15:07
  • 1
    @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$). – Connor Harris May 16 '17 at 15:25
  • $\prod_{c=1}^{100}(x+z^c)$ depends on $z$. It is $x^{100}-1$ iff $z$ is a generator of $\mathbb{F}_{101}^\times$. Otherwise (if $z \ne 0$) it will be $(x^d-1)^{100/d}$ where $d$ is the order of $z$ – reuns May 16 '17 at 16:16
  • You should specify the values of $w$ and $z$ here :). Often we can justify these types of arguments by passing to an extension field of $\mathbb F_{101}$ which contains the desired root of unity and still has the same characteristic (so it's still true that $101\cdot x = 0$ for any field element $x$). I haven't yet thought about whether this is appropriate here, but I don't see an obvious reason why not. – Erick Wong May 16 '17 at 16:21
  • @user1952009 can you elaborate in the original question on how to prove it? – i9Fn May 16 '17 at 16:25
  • What you wrote is unclear. What is $w,z$ ? – reuns May 16 '17 at 16:32
  • @user1952009 it is written in the original question $z=e^{\dfrac{2\pi i}{101}},w=e^{\dfrac{2\pi i}{10}}$ – i9Fn May 16 '17 at 16:33
  • 1
    @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. – Connor Harris May 16 '17 at 17:32
  • Derp, I mean $\mathbb{Z}[e^{2\pi i/1010}]$. – Connor Harris May 16 '17 at 17:37
  • 1
    @i9Fn So this is the same question ? Why don't you write here what is $w,z$ ? – reuns May 16 '17 at 18:03
  • Wait, sorry, there are cyclotomic integers that aren't actual integers (one example being $2 \sin 72^\circ = e^{2\pi i/5} + e^{-2 \pi i/5}$ ). There's another way of guaranteeing that $A$ is an integer short of computing it fully, though; again, see my answer to the other question. – Connor Harris May 16 '17 at 18:09
  • @user1952009 No, this an attempted solution of the original question with some parts unjustified, this question ask to justify these step and suggest a general framework to extend modular arithmetic to complex numbers. – i9Fn May 16 '17 at 18:24
  • I don't think we need it here, but you should look at the ring $\mathbb{Z}{101}[i] = { a+ib, (a,b) \in \mathbb{Z}{101}}$ with the usual addition modulo $101$ and the multiplication $(a+ib)(c+id) =ac-bd+i(ad+bc)$ where $ac-bd$ and $ad+bc$ are computed modulo $101$. In the same way we have the ring $\mathbb{Z}{101}[e^{2i \pi / 101}]$ which works in the same way, except that its element are of the form $\sum{n=0}^{99} a_n e^{2i n \pi / 101}$ where $a_n \in \mathbb{Z}_{101}$ @ConnorHarris – reuns May 16 '17 at 18:34
  • @user1952009 You correctly note that it isn't important, but the extension $\mathbb Z_{101}[i]$ doesn't work very well since $\mathbb Z_{101}$ already contains $\sqrt{-1}$ (namely $\pm10$), so you're getting a ring that has zero divisors. – Erick Wong May 17 '17 at 16:35

0 Answers0