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 qth roots of unity modulo p. Let the qth 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 qth roots of unity in \mathbb{C} by the qth roots of unity modulo p. This is okay since the qth roots of unity modulo p satisfy every algebraic relation over \mathbb{Z} that the qth 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).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: