Posted by: holdenlee | July 14, 2010

## PftB, 23.14

Problem: Suppose $p,q$ are primes and $r$ is a positive integer so that $q\mid p-1$, $q\nmid r$, and $p>r^{q-1}$. Let $a_1,\ldots, a_n$ be integers such that $a_1^{\frac{p-1}{q}}+\cdots + a_r^{\frac{p-1}{q}}$ is a multiple of $p$. Prove that at least one of the $a_i$‘s is a multiple of $p$. [Problems from the Book, 23.14]

Solution: The nonzero $a_i^{\frac{p-1}{q}}$ are just the $q$th roots of unity modulo $p$. Let the $q$th roots of unity be $r_i$. We want to show that if $c_1r_1+\cdots +c_qr_q=0$ for nonnegative integers $c_i$ then either $c_1=\cdots =c_r$ (in which case $q\mid r$) or $c_1+\cdots +c_q>\sqrt[q-1]{p}$. Assume the latter is not true.

Let $\omega$ be a primitive root of unity (in $\mathbb{C}$). The Galois group of $\mathbb{Q}[\omega]/\mathbb{Q}$ consists of the maps $\omega\to\omega^i$ for $1\leq i\leq q-1$. By the Fixed Field Theorem the fixed field is $\mathbb{Q}$.  Hence

(Alternatively, just see that the coefficients will be symmetric polynomials of the $\omega^i$.) Now

Considering the polynomial modulo $p$, we see that $\sum_i c_ir_i$ is a root (replace the $q$th roots of unity in $\mathbb{C}$ by the $q$th roots of unity modulo $p$. This is okay since the $q$th roots of unity modulo $p$ satisfy every algebraic relation over $\mathbb{Z}$ that the $q$th roots of unity in $\mathbb{C}$ do.). Since it is zero modulo $p$, the constant term must be zero modulo $p$, and $\prod_k \sum_i c_i\omega^{ik}=0$ (since its absolute value is less than $p$). This means that one of the factors is zero and all the $c_i$ are equal (since $x^{q-1}+\cdots +x+1$ is the irreducible polynomial of $\omega^i,1\leq i\leq q-1$).