Progressions in every two-coloration of Z_n

For each positive integer n, G(n) is defined to be the largest integer k such that no matter how Z_n is two-colored, some progression a, a + d, a + 2d, ..., a + (k - 1)d of k distinct elements of Z_n will appear in one color. Our main theorem shows constructively that if Z_n can be two-colored in such a way that the longest monochrome progression has m distinct terms mod n and any monochrome progression of k distinct terms with common difference d ≢ 0 (mod n) has the property that kd ≢ 0 (mod n), then G(rn) ≤ m for 1 ≤ r ≤ m and G(rn) ≤ r for r > m. One lower bound on G(n) says G(rn) ≥ G(n) for r ≥ 1 and n ≥ 1. Two main results with corollaries, a "quadratic-residue coloration" on Z_p for p a prime, and the van der Waerden numbers W(k) for 2 ≤ k ≤ 5, together with a computer search, have been used to determine the exact value of G(n) for 1 ≤ n ≤ 53, for all primes up to 71, and for a few more cases, the highest of which is G(695) = 5 which guarantees that W(6) ≥ 696.