4
$\begingroup$

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero.

I've started the proof, but I need a bit of help midway through.

Assume there exists a run of length n, which we currently assume is the longest possible chain.

If we induct on n, we can assume there is a run of the form $m_1p_1^2, m_2p_2^2, ..., m_np_n^2$ (where each of the $p_i$ are prime).

If I add $M = lcm(m_1p_1^2, m_2p_2^2, ..., m_np_n^2)$ to each number, I get another run of length n.

So here's where the issue starts. When I talked to my advisor about it, he referenced a theorem where there exists a prime $p$ congruent to $1\ mod\ M$.

I am unfamiliar with this theorem, so I'm not sure how to use this information. Any chance I can get some help? Or else is there a simpler way to go about this problem?

$\endgroup$
3
$\begingroup$

Simpler solution: we seek $n$ to satisfy all of the following:

$$n\equiv 0\pmod{p_1^2}$$

$$n+1\equiv 0\pmod{p_2^2}$$

$$n+2\equiv 0\pmod{p_3^2}$$

$$\vdots$$

$$n+k\equiv 0\pmod{p_k^2}$$

Now use the Chinese remainder theorem.

$\endgroup$
  • $\begingroup$ Thanks for the help! I really appreciate it. $\endgroup$ – Barney Nov 20 '14 at 20:47
3
$\begingroup$

There are two relevant theorems at play. A theorem that guarantees a prime congruent to $1 \bmod M$ is Dirichlet's Theorem on Primes in Arithmetic Progressions, which says that as long as $x$ and $y$ are coprime, then the sequence $x + ny$ as $n$ increases contains infinitely many primes.

The second theorem at play is the Chinese Remainder Theorem, which allows you to skip the induction and directly prove the result.

$\endgroup$
  • $\begingroup$ Thank you! I believe that was just what I needed. I'm going to give the CRT version a chance as well, since that one definitely seems much more intuitive. $\endgroup$ – Barney Nov 20 '14 at 20:46
0
$\begingroup$

Instead of induction, how about using the Chinese Remainder Theorem to find a number that is $n$ modulo $(p_n)^2$ for $1\le n\le k$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.