Putnam 55/B4 solution

15th Putnam 1955

Problem B4

Can we find n such that μ(n) = μ(n + 1) = ... = μ(n + 1000000) = 0? [The Möbius function μ(r) = 0 iff r has a square factor > 1.]

Solution

Answer: yes.

Straightforward.

Let p_n be the nth prime. We show how to find a_n such that p₁² divides a_n, p₂² divides a_n + 1, p₃² divides a_n + 2, ... , p_n² divides a_n + n - 1.

Evidently we can take a₁ = 4. We now use induction. a_n + k p₁² ... p_n² has the same property as a_n. So we need to pick k such that a_n + k p₁² ... p_n² = 0 (mod p_n+1²). But that is always possible (by Euclid's algorithm, for example) since p_n+1² is relatively prime to p₁² ... p_n².

15th Putnam 1955