1
$\begingroup$

Prove that there exist 135 consecutive positive integers so that the second least is divisible by a perfect square $> 1$, the third least is divisible by a perfect cube $> 1$, the fourth least is divisible by a perfect fourth power $> 1$, and so on.

How should I go about doing this?

I thought perhaps I should use Fermat's little theorem, or its corollary?

Thanks!

$\endgroup$
  • $\begingroup$ Wow, this problem sounds painful. $\endgroup$ – Don Thousand Mar 19 at 4:08
3
$\begingroup$

Use the Chinese Remainder Theorem. Pick $134$ distinct primes. The perfect square is the square of the first, the cube is the cube of the second, and so on. All your moduli are distinct, so CRT guarantees a solution. If you use the smallest primes in order and $N$ is the least of your $135$ numbers, you have $N+1 \equiv 0 \pmod {2^2}, N+2 \equiv 0 \pmod {3^3}, N+3 \equiv 0 \pmod {5^4}\ldots$

$\endgroup$
3
$\begingroup$

By the Chinese remainder theorem, there is an integer $n$ such that $n\equiv -k\ (\text{mod}\ p_k^{k+1})$ for all $k=1,2,\dots 134$, (where $p_k$ is the $k^\text{th}$ smallest prime). Then $n, n+1, \dots, n+134$ satisfy the required condition.

$\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.