Skip to main content
Asked
Modified 4 months ago
Viewed 342 times
3
$\begingroup$

Prove that for any positive integers $m$ and $n$ , there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$, where $d$ is some positive integer not equal to $1$.

I don't know how to approach this question.

$\endgroup$
11
  • 6
    $\begingroup$ Hint: Chinese remainder theorem. $\endgroup$
    – Wojowu
    Commented Aug 14, 2016 at 17:21
  • $\begingroup$ What if you take $d=1$? $\endgroup$ Commented Aug 14, 2016 at 17:22
  • $\begingroup$ haven't studied that yet :p. Any other way? $\endgroup$
    – user354595
    Commented Aug 14, 2016 at 17:22
  • $\begingroup$ @RickDecker that's a loophole. I should have closed that. $\endgroup$
    – user354595
    Commented Aug 14, 2016 at 17:23
  • 1
    $\begingroup$ The first term of such a sequence is precisely what CRT guarantees $\endgroup$ Commented Aug 14, 2016 at 17:25

2 Answers 2

2
$\begingroup$

Hint. The trick is to start by choosing the $d_k$s such that $(d_k)^m \mid x+k$. If you make the $d_k$s mutually coprime (say, choose different primes), then the Chinese Remainder Theorem will tell you what $x$ is.

$\endgroup$
1
$\begingroup$

For the OP we can choose $S$ below to be the $m$'th powers of elements of any sequence of coprimes (e.g. the primes, or coprimes generated as in Euclid's proof of infinitely many primes).

Hint $\ $ If $\, S\subset \Bbb Z\,$ contains infinitely many pairwise coprime integers $\,s_i\,$ then for all $\,n> 0\,$ there is a sequence of $\,n\,$ consecutive integers each of which is a multiple of some element of $\,S,\,$ since there exists an integer $\,x\,$ satisfying $\, \color{#0a0}{s_1\mid x\!+\!1},\,\ s_2\mid x\!+\!2,\, \ldots,\ \color{#c00}{s_n\mid x\!+\!n},\,$ by applying CRT to

$$\begin{align} \color{#0a0}{x\equiv -1\!\!\pmod{\!s_1}}\\ x\equiv -2\!\!\pmod{\!s_2}\\ \cdots\qquad \quad\cdots\quad\ \\ \color{#c00}{x\equiv -n\!\!\pmod{\!s_n}}\end{align}$$

Note $ $ CRT = Chinese Remainder Theorem guarantees that a solution exists when the moduli are pairwise coprime. In fact there are infinitely many solutions $\,x + k\:\! \color{#0a0}{s_1}\cdots \color{#c00}{s_n},\,$ for every integer $\:\!k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .

th powers - Mathematics Stack Exchange">
Skip to main content
Asked
Modified 4 months ago
Viewed 342 times
3
$\begingroup$

Prove that for any positive integers $m$ and $n$ , there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$, where $d$ is some positive integer not equal to $1$.

I don't know how to approach this question.

$\endgroup$
11
  • 6
    $\begingroup$ Hint: Chinese remainder theorem. $\endgroup$
    – Wojowu
    Commented Aug 14, 2016 at 17:21
  • $\begingroup$ What if you take $d=1$? $\endgroup$ Commented Aug 14, 2016 at 17:22
  • $\begingroup$ haven't studied that yet :p. Any other way? $\endgroup$
    – user354595
    Commented Aug 14, 2016 at 17:22
  • $\begingroup$ @RickDecker that's a loophole. I should have closed that. $\endgroup$
    – user354595
    Commented Aug 14, 2016 at 17:23
  • 1
    $\begingroup$ The first term of such a sequence is precisely what CRT guarantees $\endgroup$ Commented Aug 14, 2016 at 17:25

2 Answers 2

2
$\begingroup$

Hint. The trick is to start by choosing the $d_k$s such that $(d_k)^m \mid x+k$. If you make the $d_k$s mutually coprime (say, choose different primes), then the Chinese Remainder Theorem will tell you what $x$ is.

$\endgroup$
1
$\begingroup$

For the OP we can choose $S$ below to be the $m$'th powers of elements of any sequence of coprimes (e.g. the primes, or coprimes generated as in Euclid's proof of infinitely many primes).

Hint $\ $ If $\, S\subset \Bbb Z\,$ contains infinitely many pairwise coprime integers $\,s_i\,$ then for all $\,n> 0\,$ there is a sequence of $\,n\,$ consecutive integers each of which is a multiple of some element of $\,S,\,$ since there exists an integer $\,x\,$ satisfying $\, \color{#0a0}{s_1\mid x\!+\!1},\,\ s_2\mid x\!+\!2,\, \ldots,\ \color{#c00}{s_n\mid x\!+\!n},\,$ by applying CRT to

$$\begin{align} \color{#0a0}{x\equiv -1\!\!\pmod{\!s_1}}\\ x\equiv -2\!\!\pmod{\!s_2}\\ \cdots\qquad \quad\cdots\quad\ \\ \color{#c00}{x\equiv -n\!\!\pmod{\!s_n}}\end{align}$$

Note $ $ CRT = Chinese Remainder Theorem guarantees that a solution exists when the moduli are pairwise coprime. In fact there are infinitely many solutions $\,x + k\:\! \color{#0a0}{s_1}\cdots \color{#c00}{s_n},\,$ for every integer $\:\!k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .