9

Let $z=e^{\dfrac{2\pi i}{101}},w=e^{\dfrac{2\pi i}{10}}$,show that $$A=\prod _{a=0}^{9}\prod_{b=0}^{100}\prod_{c=0}^{100}(w^a+z^b+z^c)$$ find $A\equiv ?\pmod {101}$

I guess this problem maybe is USA problem,but I can't find it,and I can't solve it(this problem is from people sent to me)

math110
  • 93,304

1 Answers1

4

No official sources, but this agrees with iF9n's (half-numerical) solution here. If $\omega$ is a primitive $n$th root of unity, then $$\prod_{k=0}^{n-1} (x - \omega^k) = x^n - 1$$ and so $$\prod_{k=0}^{n-1} (x + \omega^k) = (-1)^n \prod_{k=0}^{n-1} (-x - \omega^k) = (-1)^n ((-x)^n - 1) = x^n + (-1)^{n+1}.$$

Now we have $$\begin{align*} \prod_{a=0}^9 \prod_{b=0}^{100} \prod_{c=0}^{100} (w^a + z^b + z^c) &= \prod_{a=0}^9 \prod_{b=0}^{100} ( (w^a + z^b)^{101} + 1) \\ &\equiv \prod_{a=0}^9 \prod_{b=0}^{100} (w^{101a} + z^{101b} + 1) \pmod {101} \\ &= \prod_{a=0}^9 \prod_{b=0}^{100} (w^{a} + 2) \\ &= \left[ \prod_{a=0}^9 (w^a + 2) \right]^{101} \end{align*}$$ because $w^{100} = z^{101} = 1$ and the binomial coefficients $p \choose n$ for $p$ prime, besides ${p \choose 0} = {p \choose p} = 1$, are multiples of $p$.

The modular reduction here is subtle, as the binomial expansion of $(w^a + z^b)^{101}$ contains non-integer terms. But every term in the expansion, except $w^{101a}$ and $z^{101b}$, is $101$ times some element in $\mathbb{Z}[w, z] = \mathbb{Z}[\omega_{1010}]$, where $\omega_n$ is an $n$th primitive root of unity. Thus, we can interpret "reduction modulo $101$" as reduction from $\mathbb{Z}[\omega_{1010}]$ to $\mathbb{Z}[\omega_{1010}]/(101)$, which does kill all the middle terms in the binomial expansion. Such reduction may turn a non-integer (like, say, $5 + 101 z$) into an integer, but that's not a problem here: $A$ is an algebraic integer and it's invariant under the Galois automorphisms of $\mathbb{Q}[\omega_{1010}]/\mathbb{Q}$ given by $\omega_{1010} \mapsto \omega_{1010}^k$ (which also take $\omega_{10} \mapsto \omega_{10}^k$ and $\omega_{101} \mapsto \omega_{101}^k$ where $\gcd(k, 1010) = 1$—thanks to Erick Wong in comments for pointing this out), so $A \in \mathbb{Q} \cap \mathbb{Z}[\omega_{1010}] = \mathbb{Z}$, and reduction modulo $101$ won't spuriously turn $A$ into an integer.

Finally, $$\prod_{a=0}^9 (2+w^a) = 2^{10} - 1 = 1023,$$ so the whole expression (by Fermat's little theorem) is congruent to $1023^{101} \equiv 1023 \equiv 13 \pmod {101}$.

Connor Harris
  • 7,070
  • This was done independently from iF9n's similar (and correct-looking) solution posted in a link to a comment on the OP. – Connor Harris May 16 '17 at 15:06
  • I got tripped up by that too at first, because I thought there was something sketchy about applying the formula to $n$th roots of unity for composite $n$. But there's no problem in doing so; the tricky thing with composite $n$ in such problems is that the cyclotomic polynomial is no longer $1 + x + \cdots + x^{n-1}$, but that's irrelevant here. – Connor Harris May 16 '17 at 15:20
  • You need to move "by the fact that w^10=1 and so w^100=1" up because you used it the first time too. – i9Fn May 16 '17 at 15:29
  • Better still: in the same place, I wrote $z^b$ instead of $z^{101b}$, and as $z$ is a 101st root of unity, the entire product over $b$ basically drops out. – Connor Harris May 16 '17 at 15:41
  • ...why? The roots of $x^n - 1$ are precisely the $n$th rooots of unity. – Connor Harris May 16 '17 at 16:33
  • Oops, I meant $(w^a + z^b)^{101} \equiv w^{101a} + z^{101b}$ – i9Fn May 16 '17 at 16:46
  • $(w^a + z^b)^{101} = {101 \choose 0} (w^{a})^{101} (z^b)^0 + {101 \choose 1} (w^{a})^{100} (z^b)^1 + \cdots + {101 \choose 101} (w^a)^0 (z^{b})^{101}$ – Connor Harris May 16 '17 at 17:05
  • 1
    Wait, you're right; the powers of $w$ and $z$ aren't necessarily integers, so the reasoning is a bit more subtle than simply taking modular remainders. – Connor Harris May 16 '17 at 17:12
  • 2
    Since this is a product of algebraic integers, to show that it's an integer it's sufficient to show that it's rational. And for that, standard Galois methods should apply: this is an element of $\mathbb Q(\xi)$ where $\xi = e^{2\pi i/1010}$, $w=\xi^{101}$, $z=\xi^{10}$. The Galois group of this extension consists of $\xi \mapsto \xi^k$ for nice values of $k$, and your expression looks invariant under those mappings (unless I'm being dumb), so it belongs to the base field $\mathbb Q$. – Erick Wong May 17 '17 at 17:56
  • 1
    @ErickWong That argument looks correct; the key point (which I don't know why I missed) is that every automorphism of $\mathbb{Q}(\xi)$ also takes powers of $w$ and $z$ to other powers of $w$ and $z$. – Connor Harris May 17 '17 at 19:03