Existence of AP of interesting integers

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

310,918 topics

13 users

TOPICS

No tags match your search

Existence of AP of interesting integers

G H J

Reveal topic tags

G H BBookmark kLocked kLocked NReply

Source: 2018 China TST Day 1 Q2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DVDthe1st

339 posts

DVDthe1st

#1 h Jan 2, 2018, 3:22 AM • 2 Y

Y by chessgocube, Adventure10

A number $n$ is interesting if 2018 divides $d(n)$ (the number of positive divisors of $n$ ). Determine all positive integers $k$ such that there exists an infinite arithmetic progression with common difference $k$ whose terms are all interesting.

This post has been edited 2 times. Last edited by DVDthe1st, Jan 2, 2018, 3:43 AM
Reason: variable name

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ThE-dArK-lOrD

4071 posts

ThE-dArK-lOrD

#2 h Jan 2, 2018, 8:20 AM • 3 Y

Y by chessgocube, Adventure10, Mango247

This is wrong.
Thanks @angiland for pointing out the mistakes. I'll try to fix it when I've time

This post has been edited 3 times. Last edited by ThE-dArK-lOrD, Jan 26, 2020, 5:48 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

angiland

364 posts

angiland

#3 h Jan 2, 2018, 5:01 PM • 4 Y

Y by ThE-dArK-lOrD, chessgocube, Adventure10, Mango247

ThE-dArK-lOrD wrote:

2. There exists two distinct prime numbers $q,r$ that $v_q(k)\geq 1009$ and $v_r(k)\geq 2$ .

This is more than necessary. As long as $v_q(k) \geq 1009$ and $q$ is odd, you can find a desirable sequence such that no term is a perfect square. Then each term has an even number of divisors. This suggests we do not need $v_r(k) \geq 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6858 posts

v_Enhance

#4 h Jan 6, 2018, 3:09 AM • 17 Y

Y by ThE-dArK-lOrD, nmd27082001, liekkas, yiwen, l1090107005, smy2012, e_plus_pi, ChiefEditorQuibbler, MarkBcc168, v4913, RedFlame2112, HamstPan38825, centslordm, SerdarBozdag, chessgocube, Adventure10, bhan2025

I got a different set of $k$ . Hope I didn't mess anything up. Please point out if I did.

The answer is that $k$ must have a prime divisor $p$ with $\nu_p(k) \ge 1009$ , and $k \neq 2^{1009}$ .

Say $k$ that satisfy the condition are ``good''. We begin with two simple observations: (i) multiples of good numbers are good, (ii) to show $k$ is bad it's enough to show each residue class modulo $k$ contains arbitrarily large non-interesting numbers.

We begin by proving that all numbers of the form claimed earlier are good. Let $p$ and $q$ be odd primes:

If $p > 2$ , we claim $p^{1009}$ is good. Let $t$ be a quadratic non-residue modulo $p$ . Consider the numbers $n \equiv tp^{1008} \pmod{p^{1009}}$ . All of these numbers have $\nu_p(n) = 1008$ . Moreover, $n$ is not a perfect square, since $\frac{n}{p^{1008}} \equiv t \pmod p$ . Thus $d(n)$ is even and divisible by $\nu_p(n)+1=1009$ , hence $n$ is interesting.
We claim $2^{1009} q$ is good. Letting $t$ be a quadratic non-residue modulo $q$ , the numbers $n \equiv t \cdot 2^{1008} \pmod{2^{1009}}$ are all interesting for the same reason.
The number $2^{1010}$ is also good, by taking $n \equiv 3 \cdot 2^{1008} \pmod{2^{1010}}$ since no perfect square is $3 \pmod 4$ .

Combined with observation (i) earlier this resolves one direction.

Next, we prove that:

Claim: All numbers of the form $k = (p_1 p_2 \cdots)^{1008}$ are bad, for any primes $p_i$ (possibly including $2$ ).

Proof. Consider a residue class $c \pmod k$ . Note that we can find an element $a$ in this residue class modulo $k$ with $\nu_p(a) \neq 1008$ for all $p \mid k$ . Indeed, this follows by Chinese remainder theorem:

if $\nu_p(c) \ge 1008$ we require $p^{1009} \mid a$ ,
else we require $a \equiv p^{\nu_p(c)} \pmod{p^{1009}}$ , for each prime $p$ .

Now let $M = \prod_{p \mid k} p^{1009}$ and consider the residue class $a \pmod M$ (a subset of the arithmetic progression). By Dirichlet theorem, there exist arbitrarily large numbers of the form $n = q \gcd(a,M)$ in this sequence, where $q \nmid M$ is prime. Since $\nu_p(n) \in \{0, 1, 2, \dots, 1007, 1009\}$ for every prime $p$ , the number $n$ is not interesting. $\blacksquare$

Finally, we show $2^{1009}$ is bad. Consider the residue class $a \pmod{2^{1009}}$ . If $a \equiv 0$ then $2^{2018i-2}$ is uninteresting for all $i$ . If $a \equiv 2^{1008}$ then $m^2 \cdot 2^{1008}$ is uninteresting for $m$ an odd integer. For any other $a$ , we can find uninteresting numbers of the form $q\gcd(a,2^{1009})$ , where $q$ is an odd prime, again by Dirichlet theorem. Thus $2^{1009}$ is bad.

This post has been edited 3 times. Last edited by v_Enhance, Nov 21, 2018, 5:28 PM
Reason: fix mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ltf0501

191 posts

ltf0501

#5 h Jan 6, 2018, 12:13 PM • 2 Y

Y by chessgocube, Adventure10

I have the same idea as Evan Chen's.

This post has been edited 1 time. Last edited by ltf0501, Jan 6, 2018, 12:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#6 h Jan 6, 2018, 12:27 PM • 3 Y

Y by chessgocube, Adventure10, Mango247

v_Enhance wrote:

[*]We claim $2^{1009} q$ is good. Letting $t$ be non-residue modulo $q$ , the numbers $n \equiv tp^{1008} \pmod{p^{1009}}$ are all interesting for the same reason.

There is a typo.
And a little correction: $t$ has to be odd.

This post has been edited 1 time. Last edited by liekkas, Jan 6, 2018, 12:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zschess

92 posts

zschess

#7 h Jan 12, 2018, 1:33 PM • 2 Y

Y by chessgocube, Adventure10

We claim that the only solutions are the positive integers $k$ with $v_{p}(k) \ge 1009$ for some prime $p$ and $k \neq 2^{1009}$ .

First, we claim that all such $k$ are solutions. Let $k = p^{1008} \cdot X$ . Choose the arithmetic progression $p^{1008}(Xn + r)$ , where $r$ is a quadratic non-residue modulo $X$ (which exists since $X > 2$ ). Note that $Xn + r$ is coprime to $p$ and also note that for every positive integer $n$ , the number $Xn + r$ is never a perfect square because of the choice of $r$ . Thus, $d(p^{1008}(Xn + r)) = d(p^{1008})d(Xn + r) = 1009d(Xn + r)$ is divisible by 2018 because $d(Xn + r)$ is always even (it's not a perfect square).

Now, we claim that the rest aren't solutions. Let's rewrite the arithmetic progression as $C(Dx + E)$ , where $\gcd(D, E) = 1$ . By Dirichlet's Theorem, there exist infinitely many primes in the arithmetic progression $Dx + E$ , so we can choose some $P > C$ and we have $2018 \mid d(CP) = 2d(C)$ , or $1009 \mid d(C)$ . Since $1009$ is a prime, there exist a prime $p$ such that $v_{p}(C) \ge 1008$ .

If $k = 2^{1009}$ , then the arithmetic progression is either of the form $2^{1009}(x + C)$ or $2^{1008}(2x + O)$ , where $O$ is some odd positive integer. In the first case, we can choose $x$ such that $x + C$ is a prime while for the second case we can choose $x$ so that $2x + O$ is a perfect square. In any case, the number of divisors of the chosen term will not be divisible by $2018$ .

Finally, suppose $k \neq 2^{1009}$ and $v_{p}(k) \le 1008$ for all $p$ . Consider an arithmetic progression $C(Dx + E)$ with $CD = k$ and $\gcd(D, E) = 1$ . Rewrite $C$ as $Y \cdot X^{1008}$ , where $X$ is the product of all primes $p$ with $v_{p}(C) = 1008$ (note that we have proven above that $X > 1$ ). Note that $Y$ is coprime to $X$ and also $D$ is coprime to $X$ because $v_{p}(k) \le 1008$ for all $p$ . Let $x = X^{2}q + r$ , where $0 \le r < X^{2}$ . Then, $Dx + E = DX^{2}q + (Dr + E)$ . Since $D$ is coprime to $X$ (and thus $X^{2}$ ), we can choose $r$ such that $Dr + E \equiv X \pmod{X^{2}}$ . We claim that there exist a $q$ such that the term $C(DX^{2}q + (Dr + E))$ is not interesting. Let $g = \gcd(DX^{2}, Dr + E)$ . Since $\gcd(D, E) = 1$ , $g = \gcd(X^{2}, Dr + E)$ . Note that $g \neq X^{2}$ by our choice of $r$ , thus $g \mid X^{2}$ and $g < X^{2}$ . Choose $q$ such that $\frac{DX^{2}}{g}q + \frac{Dr + E}{g}$ is a prime larger than $Cg$ (which exists by Dirichlet's Theorem). Our term is thus $Z = Y \cdot X^{1008} \cdot g \cdot P$ , for some prime $P > Cg$ . We claim that $1009$ does not divide $d(Z)$ . Clearly, $Z$ and $Y$ does not contribute anything to the divisibility of $d(Z)$ by $1009$ , because $Z$ and $Y$ are both coprime to $Xg$ (recall that $g \mid X^{2}$ ) and their prime powers are all strictly less than $1008$ . Write $g = Xg'$ , where $X \nmid g'$ . The number $X^{1008}g = X^{1009}g'$ cannot have number of divisors divisible by $1009$ , because the prime power of each element in $g'$ is at most $2$ (because $X$ is squarefree and $g' \mid X^{2}$ ), and thus there is no prime $p$ with $1009 \mid v_{p}(X^{1009}g') + 1$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#9 h Dec 13, 2018, 1:13 PM • 2 Y

Y by chessgocube, Adventure10

Darn the details are WAYYYY trickier than I was envisioning. We'll replace $d(x)$ with $f(x)$ .

The answer is all $k$ which have $\nu_p(k)\ge 1009$ for some $p$ , and $k\not=2^{1009}$ . We first show that if $\nu_p(k)\le 1008$ for all primes $p$ , then $k$ fails.

Firstly, take a subset of the AP such that $\nu_p(k)=1008$ for all primes $p\mid k$ , and say the primes are $p_1,\ldots,p_r$ . Our AP consists of sufficiently large $n$ with $n\equiv a\pmod{k}$ for some fixed $a$ . Let $d=\gcd(a,k)$ . By Dirichlet, we can pick $n=dP$ for some very large prime $P$ (I think bigger than $d$ suffices). We then have $f(dP)=2f(d)$ , so we must have $1009\mid f(d)$ . Since $1009$ is prime, and $\nu_p(k)\le 1008$ for all $p=p_i$ , we see that to get $1009\mid f(d)$ , we must have $p^{1008}\mid d$ for some $p=p_i$ .

WLOG, suppose $p_1^{1008},\ldots,p_\ell^{1008}\mid d$ and no others. Letting $M=kp_1^2\cdots p_{\ell}^2$ , pick $n\equiv ap_1\cdots p_{\ell}\pmod{M}$ . It is not hard by CRT to see that this implies $n\equiv a \pmod{k}$ , so this is a further subset of the AP. However, the way this is set up, we have that $\nu_{p_i}(n)=1009$ for $1\le i\le\ell$ , and $\nu_{p_i}(n)\le 1007$ for $\ell+1\le i\le r$ . Now, $\gcd(ap_1\cdots p_\ell,M)=p_1\cdots p_\ell d$ , so again by Dirichlet, we can choose $n=ap_1\cdots p_\ell P$ for some really huge prime $P$ . We now have that $f(n)$ has factors $2,3,\ldots,1008,1010$ by the observation about the $\nu_{p_i}$ so since $1009$ is prime, we cannot possibly have $1009\mid f(n)$ .

Therefore, we must have $\nu_p(k)\ge 1009$ for some prime $p$ . Now pick $n\equiv p^{1008}a\pmod{k}$ where $a$ is a quadratic non-residue mod $k/p^{1008}$ and $\gcd(a,k)=1$ , if it exists. Note that if $q>2$ is a prime factor of $k$ , then it clearly exists as we can take a QNR mod $q$ . Else, $k=2^{1009+j}$ for some $j\ge 0$ . If $j\ge 1$ , then we can pick $a=3$ , as it is not a square mod $4$ . So the only case left is $k=2^{1009}$ , and we'll deal with this later. So unless $k=2^{1009}$ , this $a$ exists. Therefore, $\nu_p(n)=1008$ and since $n$ can't be a square, $f(n)$ must be even. Thus, $1009,2\mid f(n)$ , so $2018\mid f(n)$ , as desired.

Finally, let us dispose of the case $k=2^{1009}$ . By the same Dirichlet argument, if $\gcd(a,k)<2^{1008}$ , then we can pick $n=P\cdot 2^\ell$ for $\ell\le 1007$ , and this clearly fails. Therefore, $a=2^{1008}$ , so $n=2^{1008}(1+2y)$ . We see that $1+2y$ is a square for arbitrarily large $y$ , so $f(n)$ is odd, so $2018\nmid f(n)$ . Therefore, this case fails, and the solution is complete. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

seojinkim

15 posts

seojinkim

#10 h Feb 7, 2019, 12:08 PM • 2 Y

Y by chessgocube, Adventure10

Same idea with this problem!
https://artofproblemsolving.com/community/u218439h548036p7592324

This post has been edited 1 time. Last edited by seojinkim, Feb 7, 2019, 12:08 PM
Reason: Aaaaaa

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#12 h Dec 8, 2019, 9:34 AM • 2 Y

Y by chessgocube, Adventure10

Solution found with dantaxyz. This problem is so finnicky ahhh

We claim there exists an AP of only interesting numbers with common difference $k$ works iff $p^{1009} \mid k$ for $k\not = 2^{1009}$ . Throughout the following solution, we let $a$ be the first term of the AP.

First we show that we can construct an AP if $k=p^{1009}m$ for some $p\nmid m$ , $p\not = 2$ . Suppose $a=a'p^{1008}$ . Then a general term in the AP is $a+\ell k = a'p^{1008} + p^{1009}\ell m = p^{1008}(a'+p\ell m)$ , for $\ell \ge 1$ . The number of factors of this expression is a mutiple of 2019 iff there is some odd exponent in the p.f. of $a'+p\ell m$ , which happens iff $a'+p\ell m$ is not a square. We want $a'+pm\ell$ to not be a square for any $\ell \ge 1$ , so choose some $a'$ such that $a'$ is an QNR mod $pm$ . Then the sequence $\{a+\ell k\}_{\ell \ge 0}$ contains only interesting numbers.

Now suppose there exists no $p$ such that $p^{1009} \mid k$ . Then we claim that $k$ is not good. Let $k=p_1^{e_1}p_2^{e_2}\cdots p_j^{e_j}$ , so $e_1,e_2,\ldots,e_j \le 1008$ . Note that by Dirichlet, our AP contains infinitely many primes iff $\gcd(a,k)=1$ . But it clearly cannot contain infinitely many primes, so $\gcd(a,k) > 1$ . Let $\gcd(a,k)=g>1$ . Then $\gcd(a/g,k/g)=1$ , so there are infintely many primes in $\{\tfrac{a}{g} + \tfrac{k}{g}\ell\}_{\ell \ge 0}$ by Dirichlet. Take some prime $p$ such that $\gcd(p,g)=1$ in this sequence; then $a+k\ell = gp$ , so $gp$ is in the original AP. So $2018\mid d(gp)=2d(g) \implies 1009\mid d(g)$ . So $q^{1008} \mid g$ for some prime $q$ . Thus, $q^{1008} \mid k$ .

There are two cases, 1) some other prime divides $k$ , 2) no other prime except $q$ divides $k$ .

Case 1: Say $r\mid k, r\not=q$ . So $rq^{1008} \mid k$ . Then a general term is $q^{1008}(\tfrac{a}{q^{1008}} + \tfrac{k}{q^{1008}}n)$ . But $\gcd(q,\tfrac{a}{q^{1008}} + \tfrac{k}{q^{1008}}n)$ will be greater than 1 for some $n$ unless $q\mid \tfrac{k}{q^{1008}}$ , which is a contradiction since $q^{1009} \nmid k$ by assumption.

Case 2: So suppose $q$ is the only prime dividing $k$ . But since $q^{1009} \nmid k$ , we must have $k=q^{1008}$ . The terms in the AP are $a+q^{1008}\ell$ for $\ell \ge 0$ . But $q^{1008} \mid a$ , (since $q^{1008} \mid g = \gcd(a,k)$ ), So the terms in the AP are $yq^{1008}$ for all $y$ sufficiently large. Then take some prime $s$ such that $s^2q^{1008}$ is a term of the sequence. This must be interesting, so $2018 \mid 3\cdot 1009$ , a contradiction! So $k$ is not good.

If $k=2^{1009}m$ for some odd $m$ , then we claim there exists no good AP. Suppose $\{a+2^{1009}m \ell\}_{\ell \ge 0}$ contains only interesting numbers for some $a$ . This case is not too hard using the same Dirichlet idea we used before.

EDIT: This is incorrect

in particular the proof for case 1 is flawed. I'll try to fix this later by proving that $k=t^{1008}$ does not work for squarefree $t$ .

This post has been edited 1 time. Last edited by pad, Dec 10, 2019, 9:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aops29

452 posts

aops29

#13 h Jan 26, 2020, 3:33 AM • 4 Y

Y by AlastorMoody, chessgocube, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Stormersyle

2785 posts

Stormersyle

#14 h Mar 25, 2020, 10:38 PM • 2 Y

Y by chessgocube, Mango247

I claim the answer is all $k$ that have a prime factor with $\nu_p\ge 1009$ , except for $k=2^{1009}$ .

First I will show these work. Suppose $k=p^{1009}k_1$ ; then, let $a_1$ be a nonquadratic residue mod $pk_1$ (which is possible since $pk_1>2$ ). Next, set $a=p^{1008}a_1$ . To see that this works, note $\nu_p(a+nk)=1008$ for all $n$ , so $1009|\tau(a+nk)$ . Also, $a+nk=p^{1008}(a_1+pk_1)$ cannot be a square due to our choice of $a_1$ , so $2|\tau(a+nk)$ ; hence, $2018|\tau(a+nk)$ , as desired.

Next, suppose $k$ works, and I will prove that there exists $p$ such that $\nu_p(k)\ge 1009$ . Let $\gcd(a, k)=d$ , $a=dx, k=dy$ , where $\gcd(x, y)=1$ . Thus, the arithmetic progression is $dx, d(x+y), d(x+2y), ...$ . By Dirichlet theorem we can choose $n$ such that $x+ny=q>d$ for prime $q$ ; then, $dq$ is interesting, meaning there exist $p|d$ such that $\nu_p(d)\equiv -1\pmod{1009}$ . Now let $p_1, p_2, ..., p_j$ be all the prime factors of $d$ with $\nu_p(d)\equiv -1\pmod{1009}$ ; note that if for any $i$ we have $\nu_{p_i}(y)>0$ then we are done, so suppose FTSOC that $p_i\nmid y$ for all $i$ . Let $M=p_1p_2...p_j$ , and consider arbitary sufficiently large $z$ .

Then, note that for all $n$ where $n\equiv (M^z-x)y^{-1}\pmod{M^{z+1}}$ , we'll have $x+yn\equiv M^z\pmod{M^{z+1}}$ , so let $n_1, n_2, ...$ be the sequence of $n\ge 0$ which satisfy this. We see that $n_1, n_2, ...$ is an arithmetic progression with common difference $M^{z+1}$ , meaning $x+yn_1, x+yn_2, ...$ is an arithmetic progression with common difference $yM^{z+1}$ and starting term $aM^{z+1}+M^z$ for some $a$ . When we divide each term in this sequence by $M^z$ we get an arithmetic progression with starting term $aM+1$ and common difference $ym$ . Note that $aM+1|x+yn_1$ and $\gcd(x+yn_1, y)=\gcd(x, y)=1$ , so $\gcd(aM+1, y)=1$ . Thus $\gcd(aM+1, yM)=1$ , so by Dirichlet, there exist arbitrarily large primes in this arithmetic progression, meaning there exist $n$ such that $x+yn=qM^z$ for arbitrarily large prime $q$ . Thus, for this particular $n$ , we have $a+kn=dqM^z$ , so for all $p\in \{p_1, ..., p_j\}$ we have $\nu_p(a+kn)=1+z$ . But since $z$ is arbitrary we can let $1+z\ncong 0\pmod{1009}$ , meaning that $a+kn$ is not interesting, which is a contradiction.

Finally we show that $k=2^{1009}$ doesn't work. To see this, note that in this case we must have $d=2^{1008}$ , so thus $a=2^{1008}a_1$ for odd some $a_1$ , so thus $a+nk=2^{1008}(a_1+2n)$ for all $n$ . But then we can set $n=\frac{m^2-a_1}{2}$ for some odd $m$ , and $a+nk$ will not be interesting. Therefore, we are now done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Al3jandro0000

804 posts

Al3jandro0000

#15 h Mar 26, 2020, 3:28 AM

Y by

Stormersyle wrote:

your solution

Possibly my favorite solution, but just a little point; why must exists such $n\equiv (M^z-x)y^{-1}\mod M^{z+1} ?$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Stormersyle

2785 posts

Stormersyle

#16 h Mar 26, 2020, 12:57 PM • 3 Y

Y by Mango247, Mango247, Mango247

Al3jandro0000 wrote:

Stormersyle wrote:

your solution

Possibly my favorite solution, but just a little point; why must exists such $n\equiv (M^z-x)y^{-1}\mod M^{z+1} ?$

Well, we assumed FTSOC that $p_i\nmid y$ for all $i$ , meaning that $\gcd(y, M^{z+1})=1$ , so $y^{-1}\mod{M^{z+1}}$ must exist. So clearly $(M^z-x)y^{-1}$ is a valid residue $\mod{M^{z+1}}$ , and we can just set $x$ congruent to that

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amuthup

779 posts

amuthup

#17 h May 24, 2020, 4:08 AM

Y by

Can someone explain what (if anything) I am doing wrong when I prove the converse? I feel like I am oversimplifying things...

With a hint from v_enhance:
We claim that the answer is all $k$ such that $\nu_p(k)\ge 1009$ for some prime $p$ and $k\ne 2^{1009}.$

First, we show that all such $k$ satisfy the statement of the problem.

Let $k=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{m}^{e_{m}},$ where $e_1\ge 1009,$ and let $j=k/(p_{1}^{1008}).$ Additionally, let $q$ be any non-quadratic residue modulo $j$ (such a residue is guaranteed to exist by the Chinese Remainder Theorem).

We claim that all terms of the arithmetic sequence with starting term $p_{1}^{1008}q$ are interesting. Consider the $i$ th term, which can be written as $a_i=p_{1}^{1008}(q+ij).$ Since $q$ is not a quadratic residue modulo $j,$ we know $q+ij$ is not a perfect square, so it must have a prime factor $r$ such that $\nu_{r}(q+ij)$ is odd. Additionally, $q\not\equiv 0\pmod{p_{1}}$ and $j\equiv 0\pmod{p_{1}},$ so $\nu_{p_{1}}(a_{i})=1008.$ Therefore, $a_i$ is interesting, so we are done.

It remains to show that if $k$ does not have a prime factor $p$ such that $\nu_p(k)\ge 1009,$ then no arithmetic sequence of interesting numbers with common difference $k$ exists.

Suppose, for the sake of contradiction, that such an arithmetic sequence exists, and let the first term be $a.$

Then, by Dirichlet's Theorem, some term of the sequence is of the form $P\cdot\gcd(a,k),$ where $P$ is a prime larger than both $a$ and $k.$ Therefore, since all terms of the sequence are interesting, we must have $\nu_{p_{1}}(\gcd(a,k))=1008$ for some prime $p_1,$ so let $a=p_{1}^{1008}\cdot m,$ $k=p_{1}^{1008}\cdot n,$ where $\nu_{p_{1}}(n)=0.$

Then, the $i$ th term of the arithmetic sequence can be expressed as $p_{1}^{1008}(m+in).$ However, note that $\gcd(n,p_{1})=1,$ so we can always find some integer $r$ such that if $i\equiv r\pmod{p_{1}},$ then $m+in\equiv 0\pmod {p_{1}}.$ But clearly, we cannot have $m+in\equiv 0\pmod{p_{1}^{1008}}$ for all such $i.$

Hence, there must be another prime $p_2$ such that $m\equiv n\equiv 0\pmod{p_{2}^{1008}}.$

In this way, we can show that there are infinitely many primes $p$ such that $\nu_p(k)\ge 1008,$ which is impossible.

Finally, we show that we cannot have $k=2^{1009}.$ Assume there exists an arithmetic sequence with all terms interesting, starting term $a,$ and common difference $2^{1009}.$

Then, by Dirichlet, there is some prime $P$ greater than $a$ and $2^{1009}$ such that $P\gcd(a,2^{1009})$ is a term of the sequence. Since this expression must be interesting, we must have $\gcd(a,2^{1009})=2^{1008},$ so $a=2^{1008}.$

But $2^{1008}+4\cdot 2^{1009}=3^{2}2^{1008}$ is not interesting, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VulcanForge

624 posts

VulcanForge

#18 h May 27, 2020, 2:05 PM

Y by

The answer is any $k$ such that there exists a prime $p$ with $\nu_p (k) \geq 1009$ , with the exception of $k=2^{1009}$ which doesn't work.

First we show that this solution set works; in particular we will show $p^{1009}$ works for any odd prime $p$ . Let $q$ be a quadratic nonresidue $\pmod{p}$ ; consider the arithmetic sequence $p^{1008}(q), p^{1008}(q+p), p^{1008}(q+2p), \dots$ which has common difference $p^{1009}$ . Every term $x$ in this sequence has $\nu_p (x)=1008$ and since $q+np$ is never a perfect square for any $n$ , the number of factors of $x$ is always a multiple of $2018$ as desired. Now we just need to show $2^{1009} \cdot s$ is good for any integer $s>1$ , which follows by taking a quadratic nonresidure $q \pmod{2s}$ and considering the arithmetic sequence $2^{1008}(q), 2^{1008}(q+2s), 2^{1008}(q+4s), \dots$ .

Now we show all other $k$ are bad; in particular we first show that if $k$ is good, then there must be some $p$ with $\nu_p(k) \geq 1009$ . Assume for contradiction that for every prime $p$ we had $\nu_p(k) \leq 1008$ , and let the sequence be $\ell+kn$ as $n$ ranges over the positive integers. Letting $\text{gcd}(\ell,k)=d, \frac{\ell}{d}=a, \frac{k}{d}=b$ the sequence becomes $d(a+bn)$ . By Dirichlet since $\text{gcd}(a,b)=1$ we can find some $n$ such that $a+bn$ is a large prime; then there must be a prime $p$ such that $\nu_p(d)=1008$ . Let $p_1, p_2, \dots , p_j$ be the primes such that $\nu_{p_i}(d)=1008$ and let $t=p_1p_2 \cdots p_j$ ; note that we must have $\text{gcd}(a,t)=1$ by our assumption. By the chinese remainder theorem we can find an arithmetic progression $x_1, x_2, \dots$ with common difference $t^2$ such that $ax_i+b \equiv t \pmod{t^2}$ for each $i$ . If we let $ax_1+b=tm$ then the sequence $ax_i+b$ is $tm, t(m+at), t(m+2at), \dots$ . Note that $\text{gcd}(m, t)=1$ and $\text{gcd}(m, a) = \text{gcd}(tm -ax_1, a) = \text{gcd}(b,a)=1$ . Thus by Dirichlet there are infinitely many primes in the sequence $m, m+at, m+2at, \dots$ , and thus we can pick some $i$ such that $ax_i+b=tQ$ for some large prime $Q$ . Then $d(a+bx_i)=dtQ$ , and there does not exist a prime $p$ such that $\nu_p(dtQ)=1008$ , contradiction.

It remains to take care of $k=2^{1009}$ , assuming for contradiction there was a good arithmetic sequence. Let the sequence be $a+2^{1009}n$ as $n$ ranges over the positive integers. Letting $d=\text{gcd}(a,2^{1009}), \frac{a}{d}=x, \frac{2^{1009}}{d}=y$ the sequence becomes $d(x+yn)$ . Since $\text{gcd}(x,y)=1$ by Dirichlet we can pick $n$ such that $x+yn$ is a prime; thus we must have $d=2^{1008}$ . However, then we have $y=2$ so we can pick $n$ so that $x+yn$ is a perfect square. $d(x+yn)$ will then have an odd number of factors, contradiction as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jj_ca888

2726 posts

jj_ca888

#19 h Sep 5, 2020, 11:57 PM • 2 Y

Y by anonman, Aryan-23

Remark: Jesus christ !@(#@!& this !@(#@!&ing problem. I can't even express through words how !@(#@!&ing much this problem has destroyed my mental state. Nobody should go through the pain of trying this !@(#@!&ing problem. My condolences go out to the Chinese students who in 2018 had to do this !@(#@!&ing problem in their TST exam.

I claim that our answer is all $k$ with some prime $p \mid k$ satisfying $v_p(k) \geq 1009$ and $k \neq 2^{1009}$ . Call a $k$ satisfying the problem statement $\textit{hot}$ .

For our constructions, we will use the clear fact that if $k$ is hot then all multiples of $k$ are also hot. Consider the following:\begin{itemize}
\item Let $p$ be an odd prime. We provide a construction for $p^{1009}$ being hot. Consider all numbers of the form $n \equiv kp^{1008} \pmod{p^{1009}}$ where $k$ is a non-QR modulo $p$ . These numbers clearly form an arithmetic sequence with common term difference $p^{1009}$ . Note that all of these $n$ cannot be perfect squares since $\frac{n}{p^{1008}} \equiv k \pmod p$ and $k$ is non-QR. Hence $d(n)$ for all of these $n$ is even. Furthermore, if we write $n = kp^{1008} + rp^{1009} = p^{1008}(k + pr)$ for some nonnegative integer $r$ , clearly $p \nmid pr + k$ hence $v_p(n) + 1 = 1009$ for all of these $n$ . Thus $2018 \mid d(n)$ for all $n$ of above described form and thus all $p^{1009}$ for odd primes $p$ are hot. \newline
\item Let $p$ be an odd prime. We provide a construction for $2^{1009}p$ being hot. Similar to above, take all $n$ of the form $n \equiv k\times 2^{1008} \pmod{2^{1009}q}$ for some $k$ non-QR modulo $q$ . For similar reasons to the previous point we see that $2018 \mid d(n)$ for all these $n$ . \newline
\item Lastly, we prove that $2^{1010}$ is hot. Indeed, taking all $n \equiv 3 \times 2^{1008} \pmod{2^{1010}}$ suffices since squares are not $3$ modulo $4$ and the exponent of $2$ is clearly $1009$ .
\end{itemize}
From these, we can multiply to get that all $k$ that we originally claimed were hot are indeed hot. Hence our constructions are complete.

It remains to show that for the remaining $k$ there does not exist an arithmetic sequence with common term difference $k$ for which all terms are interesting.

First we tackle $k$ such that for all primes $p \mid k$ , $v_p(k) \leq 1008$ . Let $(s + kn)$ where ${n : 1 \to \infty}$ be such a working arithmetic sequence. By Dirichlet on arithmetic sequences, if $s$ and $k$ are coprime, then some term in this sequence is prime, hence we let $\gcd(s, k) = t > 1$ . Write $s = ts'$ and $k = tk'$ . Then the arithmetic sequence can be written as $t(s' + k'n)$ for $n: 1 \to \infty$ except now that $s'$ and $k'$ are relatively prime. Hence again by Dirichlet on arithmetic series we may choose $n$ so that $s' + k'n$ is some very large prime $p$ relatively prime to $t$ . We need $2018 \mid d(pt) \implies 1009 \mid d(t)$ and since $d(t) \mid d(k)$ we conclude that some prime $q$ satisfies $q^{1008} \mid k, t$ . Let $S$ be the set of all primes $\{p_1, \ldots p_m\}$ such that $v_{p_i}(t) = 1008$ . We go back to the sequence $t(s'+ k'n)$ . Consider the number $G = p_1p_2\ldots p_m$ . Clearly $\gcd(s', G) = 1$ and we can find an arithmetic sequence with difference $G^2$ satisfying $s'x + k' \equiv G \pmod{G^2}$ for all $x$ in that arithmetic sequence so every $s'x + k'$ can be written as $Gr$ for some positive integer $r$ . The sequence becomes $Gr, G(r + aG), G(r + 2aG), \ldots$ and so on. By Dirichlet again we may pick an $x$ so that the term becomes $tQ$ for large prime $Q$ and then no prime has $v_p$ of it $1008$ , which is bad, a contradiction.

We can use Dirichlet similarly to kill the case when $k = 2^{1009}$ . I am too morally discouraged to write it out. Otherwise, we are done. $\blacksquare$

This post has been edited 6 times. Last edited by jj_ca888, Sep 6, 2020, 12:28 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AwesomeYRY

579 posts

AwesomeYRY

#20 h Apr 21, 2021, 3:44 AM • 1 Y

Y by Mango247

First, note that an integer $n$ is interesting iff $n=p^{1008}\cdot (non-square)$

I claim that $k$ works iff there is $p$ such that $v_p(k)\geq 1009$ and $k\neq 2^{1009}$ . We first construct values for these.

Case 1: $p$ is odd. let $q$ be some quadratic nonresidue mod $p$ . Write $k=p^{1008}\cdot m$ , and take the sequence
$\forall n, x_n= p^{1008} (q+nm)$ Verify that $x_n$ increments by k. Next, clearly $v_p(x_n)=1008$ , and $x_n$ is never a square since $q+nm$ cannot be a square. Thus, $2018\mid d(x_n)$ .
$\square$

Case 2: $p=2$ . Let $k=2^{1010}\cdot m$ , then take the sequence
$\forall n, x_n = 2^{1008} (3+(4m)n)$ Verify that $x_{n+1}-x_n=k$ . Next, we clearly have $v_2(x_n)=1008$ , and $3+4mn$ cannot be a square, thus $2018\mid d(x_n)$ and we are done.

Alternatively, if $k=2^{1009}\cdot p$ , then we may take the sequence
$\forall n, x_n = 2^{1008} (q+(2p)n)$ which also works for some quadratic residue $q$ mod 2p.
$\square$

We now show that these are the only solutions. AFTSOC otherwise, write $n=\prod p_i^{1008}$ . WLOG we write the progression as $x_n=L(an+d)$ where $\gcd(a,d)=1$ and $k=aL$ . Then, due to Dirichlet's, we may find an arbitrarily large $P$ such that $P=an+d, \gcd(p,L)=1$ . Then, we have that $2018\mid d(L\cdot P)\Longrightarrow 1009\mid d(L)$ Thus, if we take the $p$ as the most commonly occuring prime in $L$ , then we have that $v_p(L)= 1008$ . We now break down into two cases. Similar logic holds for all other $p$ , thus $\forall p, v_p(L)\geq v_p(n)\Longrightarrow n\mid L$ , so $a=1$ . Thus, $x_n = k(n+d)$ . At which point, we clearly fail when we choose $n$ such that $\forall p_i$ , $v_{p_i}(n+d)=1009-e_i$ . Thus, $d(x_n) = 1010^{\text{something}}$ , so $x_n$ is not interesting, a contradiction.

Finally, we verify $k=2^{1009}$ , our sequence must be of the form
$2^i(a + n \cdot 2^{1009-i})$ We must have $i\geq 1008$ , and $1009-i\leq 1$ , however for both $2^0,2^1$ , there are no non-quadratic residues so we will be able to find a square $a + n \cdot 2^{1009-i}$ , a contradiction.

Thus, we are done $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AwesomeYRY

579 posts

AwesomeYRY

#21 h Apr 21, 2021, 3:44 AM • 1 Y

Y by Mango247

Remark: There are undoubtedly errors in my solutions.

First, note that an integer $n$ is interesting iff $n=p^{1008}\cdot (non-square)$

I claim that $k$ works iff there is $p$ such that $v_p(k)\geq 1009$ and $k\neq 2^{1009}$ . We first construct values for these.

Case 1: $p$ is odd. let $q$ be some quadratic nonresidue mod $p$ . Write $k=p^{1008}\cdot m$ , and take the sequence
$\forall n, x_n= p^{1008} (q+nm)$ Verify that $x_n$ increments by k. Next, clearly $v_p(x_n)=1008$ , and $x_n$ is never a square since $q+nm$ cannot be a square. Thus, $2018\mid d(x_n)$ .
$\square$

Case 2: $p=2$ . Let $k=2^{1010}\cdot m$ , then take the sequence
$\forall n, x_n = 2^{1008} (3+(4m)n)$ Verify that $x_{n+1}-x_n=k$ . Next, we clearly have $v_2(x_n)=1008$ , and $3+4mn$ cannot be a square, thus $2018\mid d(x_n)$ and we are done.

Alternatively, if $k=2^{1009}\cdot p$ , then we may take the sequence
$\forall n, x_n = 2^{1008} (q+(2p)n)$ which also works for some quadratic residue $q$ mod 2p.
$\square$

We now show that these are the only solutions. AFTSOC otherwise, write $n=\prod p_i^{1008}$ . WLOG we write the progression as $x_n=L(an+d)$ where $\gcd(a,d)=1$ and $k=aL$ . Then, due to Dirichlet's, we may find an arbitrarily large $P$ such that $P=an+d, \gcd(p,L)=1$ . Then, we have that $2018\mid d(L\cdot P)\Longrightarrow 1009\mid d(L)$ Thus, if we take the $p$ as the most commonly occuring prime in $L$ , then we have that $v_p(L)= 1008$ . We now break down into two cases. Similar logic holds for all other $p$ , thus $\forall p, v_p(L)\geq v_p(n)\Longrightarrow n\mid L$ , so $a=1$ . Thus, $x_n = k(n+d)$ . At which point, we clearly fail when we choose $n$ such that $\forall p_i$ , $v_{p_i}(n+d)=1009-e_i$ . Thus, $d(x_n) = 1010^{\text{something}}$ , so $x_n$ is not interesting, a contradiction.

Finally, we verify $k=2^{1009}$ , our sequence must be of the form
$2^i(a + n \cdot 2^{1009-i})$ We must have $i\geq 1008$ , and $1009-i\leq 1$ , however for both $2^0,2^1$ , there are no non-quadratic residues so we will be able to find a square $a + n \cdot 2^{1009-i}$ , a contradiction.

Thus, we are done $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bora_olmez

277 posts

bora_olmez

#22 h Sep 4, 2021, 3:15 PM

Y by

Cool problem.

We will solve the problem for any integer of the form $2p$ for some odd prime $p$ (i.e, $1009$ is replaced by $p$ for the remainder of this solution).

$\textbf{Lemma 1:}$ There is a prime $q$ such that $v_q(k) \geq p-1$
$\textbf{Proof)}$
Assume FTSOC that for all primes $q$ , $v_q(k) < p-1$ , if we write the arithmetic progression as $t(ax+b)$ with $a,b,t \in \mathbb{N}$ with $gcd(a,b)$ , setting $ax+b$ to be a prime that is relatively prime to $t$ by Dirichlet gives us that $v_q(t(ax+b)) < p-1$ meaning that $p \nmid t(ax+b)$ which is a contradiction. $\square$

$\textbf{Lemma 2:}$ There is a prime $q$ such that $v_q(k) \geq p$
$\textbf{Proof)}$
Assume that for all primes $q$ , $v_q(k) \leq p-1$ and let take $p_1,...,p_n$ to be the primes such that $v_{p_i}(t) = v_{p_i}(k) = p-1$ .
Then for each such prime, take $n \equiv \frac{-b}{a} \pmod{p_i}$ and notice that if we let $x \rightarrow p_ix+s$ such that $s \equiv \frac{-b}{a} \pmod{p_i}$ , then then we get a new arithmetic progression $t(ap_ix+as+b)$ where $gcd(ap_i,as+b) = p_i$ and after factoring out the $p_i$ we again get an arithmetic progression with relatively prime coefficients.

Then, we ultimately get an arithmetic progression of the form $tp_1...p_n(a'x+b')$ with $gcd(a',b') = 1$ and setting $a'x+b'$ to be a prime relatively prime to $tp_1...p_n$ , we have that $v_q(tp_1...p_n(a'x+b'))$ is either strictly less than $p-1$ or exactly $p$ meaning that $p \nmid d(tp_1...p_n(a'x+b')$ , as desired. $\square$

$\textbf{Lemma 3:}$ If there is some prime such that $v_q(k) \geq p$ with $k \neq 2^p$ , we can construct an arithmetic progression with common difference $k$ and only $\textit{interesting}$ terms.
$\textbf{Proof)}$
Unless $q = 2$ , take $t = q^{p-1}$ and $b$ to be a quadratic non-residue $\pmod{q}$ .
Otherwise, if $v_2(k) \geq p+1$ , take $t = 2^{p-1}$ and take $b \equiv 3 \pmod{4}$ , otherwise, if there is some prime $p_1 \neq 2$ such that $p_1 \mid k$ , then take again take $t = 2^{p-1}$ and take $b$ to be a quadratic non-residue $\pmod{p_1}$ .
On the other hand notice that, if $k = 2^p$ , we must have that $t = 2^{p-1}$ because we know that if we write the arithmetic progression as $t(ax+b)$ , then $t$ must be interesting, yet then there will always be a square of the form $2x+b$ meaning that for some $x \in \mathbb{N}$ , $2 \nmid d(2^{p-1}(ax+b))$ and consequently such values do not work. $\square$

Combining $\textbf{Lemma 1, Lemma 2}$ , and $\textbf{Lemma 3}$ , we have that only $k \in \mathbb{N}$ such that there is some prime $q$ with $v_q(k) \geq p$ and $k \neq 2^p$ works. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sprites

478 posts

Sprites

#23 h Sep 14, 2021, 3:46 PM • 1 Y

Y by JG666

2018 China TST Day 1 Q2 wrote:

The only $k$ which work are those which have $\nu_p(k) \ge 1009$ and $k \neq 2^{1009}$
Claim: All numbers of the form $k = (p_1 p_2 \cdots p_k)^{1008}$ don't work.
Proof: Let the arithmetic progression be $C(dX+e)$ denoted by the set $S$
Choose $M = \prod_{p \mid k} p^{1009}$ and let $X=p_1^{2007} p_2^{2007}............ \in S$
By Dirchlet's theorem, there exist arbitrarily large numbers of the form $n = q^{10} \gcd(X,M)$ in this sequence, where $q \nmid M$ is prime. Since $\nu_p(n) =1009^k \cdot 11$ for every prime $p$ , the number $n$ is not interesting. $\blacksquare$
Claim: $p^{1009}$ works for all $p$
Claim: Let $q$ be a quadratic nonresidue $\pmod{p}$ ; consider the arithmetic sequence $p^{1008}(q), p^{1008}(q+p), p^{1008}(q+2p), \dots$ which has common difference $p^{1009}$ . Every term $x$ in this sequence has $\nu_p (x)=1008$ and since $q+np$ is never a perfect square for any $n$ , the number of factors of $x$ is always a multiple of $2018$ as desired. $\blacksquare$
Claim: $2^{1009}$ doesn't work.
Proof: Let the sequence be $a+2^{1009}n$ for $n \in \mathbb{N}$ Let $d=\text{gcd}(a,2^{1009}), \frac{a}{d}=x, \frac{2^{1009}}{d}=y$ the sequence becomes $d(x+yn)$ .
Since $\text{gcd}(x,y)=1$ by Dirichlet we can pick $n$ such that $x+yn$ is a prime; thus we must have $d=2^{1008}$ .
However,we have $y=2$ so we can pick $n$ so that $x+yn$ is a perfect square then $d(x+yn)=\text{odd}$ ,contradiction as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8853 posts

HamstPan38825

#24 h Oct 10, 2021, 2:30 PM • 1 Y

Y by centslordm

The answer is $\boxed{m \cdot p^{1009}}$ for any prime $p$ and any positive integer $m$ , excluding the number $2^{2009}$ . Observe that there must exist at least one $p$ such that $\nu_p (a_0) \geq 1008$ , where $a_0$ is the first term.

Construction. Assume that $p>2$ . Take the first term equal to $a_0 = n \cdot p^{1008}$ for any $n > 1$ relatively prime to $p$ . Evidently $\nu_p(a_0+ik) = \nu_p(n \cdot p^{1008} + mi \cdot p^{1009}) = 1008,$ by $\nu_p$ properties. Now $1009 \cdot 2 = 2018 \mid d(a_0+ik)$ for all $i$ because there exists another factor of $a_0+ik$ .

Now assume $p=2$ . $2^{2009}$ fails, because for any term of the form $a^2 \cdot 2^{2008}$ has $d(n) \equiv 1009 \pmod {2018}$ -- and such terms exist because all odd $a \cdot 2^{2008}$ are in the sequence. For numbers of the form $m \cdot 2^{1009}$ for $m>1$ , let the first term be $n \cdot 2^{1008}$ where $n$ is a NQR mod $2m$ , which always exists for $m>1$ . This trivially works, so we have resolved the $p=2$ case.

Proof of Necessity Assume that $\nu_p(k) < 1009$ for all $p$ . If $\nu_p(k) < 1008$ for any $p$ , then $\nu_p(a_0 + ik) = \min(\nu_p(a_0), \nu_p(ik)) < 1008$ for any $\gcd(i, p) = 1$ as the index. On the other hand, for all $p$ with $\nu_p(k) = 1008$ , we claim there exists some $i$ such that $\nu_p(a_0+ik) > \min(\nu_p(a_0), \nu_p(ik)) = 1008.$ In particular,

Claim. There exists an index $i$ such that $\nu_p(a_0+ik) = 1009$ for all $p$ with $\nu_p(k) = 1008$ .

Label all such $p$ $p_0, p_1, \cdots, p_n$ for some $n$ . If $\nu_{p_j}(a_0) < 1008$ , there is nothing to prove. If $\nu_{p_j}(a_0) > 1008$ , then take $i \equiv p_j \pmod {p_j^2}$ as the index. If $\nu_{p_j}(a_0) = 1008$ , then set $a_0 = p_j^{1008} a_0'$ and $k = p_j^{2008} \cdot k'$ for $k', a_0'$ relatively prime to $p_j$ . Then $\nu_{p_j}(a_0+ik) = \nu_{p_j}(p_j^{1008} (a_0' + ik')) =1009$ must hold, which identifies a class of the $p_j-1$ solutions $i \equiv r + sp_j \pmod {p^2}$ for $0 \leq r \leq p_j-1$ and any $0 \leq s \leq p_j-1$ that we can pick, excluding the solution which causes $p_j^2 \mid a_0' + ik'$ . Combining throughout all $j$ , this becomes a system of $n$ congruences wrt $p_0^2, p_1^2, p_2^2$ , which has a solution by CRT; hence such an $i$ exists. $\blacksquare$

This means that we can always find a counterexample for any starting $a_0$ and prime $p$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8853 posts

HamstPan38825

#25 h Oct 10, 2021, 2:31 PM • 1 Y

Y by centslordm

If this solution works, I believe it is the first one in this thread without invoking Dirichlet.

The answer is $\boxed{m \cdot p^{1009}}$ for any prime $p$ and any positive integer $m$ , excluding the number $2^{2009}$ . Observe that there must exist at least one $p$ such that $\nu_p (a_0) \geq 1008$ , where $a_0$ is the first term.

Construction. Assume that $p>2$ . Take the first term equal to $a_0 = n \cdot p^{1008}$ for any $n > 1$ relatively prime to $p$ . Evidently $\nu_p(a_0+ik) = \nu_p(n \cdot p^{1008} + mi \cdot p^{1009}) = 1008,$ by $\nu_p$ properties. Now $1009 \cdot 2 = 2018 \mid d(a_0+ik)$ for all $i$ because there exists another factor of $a_0+ik$ .

Now assume $p=2$ . $2^{2009}$ fails, because for any term of the form $a^2 \cdot 2^{2008}$ has $d(n) \equiv 1009 \pmod {2018}$ -- and such terms exist because all odd $a \cdot 2^{2008}$ are in the sequence. For numbers of the form $m \cdot 2^{1009}$ for $m>1$ , let the first term be $n \cdot 2^{1008}$ where $n$ is a NQR mod $2m$ , which always exists for $m>1$ . This trivially works, so we have resolved the $p=2$ case.

Proof of Necessity. Assume that $\nu_p(k) < 1009$ for all $p$ . If $\nu_p(k) < 1008$ for any $p$ , then $\nu_p(a_0 + ik) = \min(\nu_p(a_0), \nu_p(ik)) < 1008$ for any $\gcd(i, p) = 1$ as the index. On the other hand, for all $p$ with $\nu_p(k) = 1008$ , we claim there exists some $i$ such that $\nu_p(a_0+ik) > \min(\nu_p(a_0), \nu_p(ik)) = 1008.$ In particular,

Claim. There exists an index $i$ such that $\nu_p(a_0+ik) = 1009$ for all $p$ with $\nu_p(k) = 1008$ .

Label all such $p$ $p_0, p_1, \cdots, p_n$ for some $n$ . If $\nu_{p_j}(a_0) < 1008$ , there is nothing to prove. If $\nu_{p_j}(a_0) > 1008$ , then take $i \equiv p_j \pmod {p_j^2}$ as the index. If $\nu_{p_j}(a_0) = 1008$ , then set $a_0 = p_j^{1008} a_0'$ and $k = p_j^{2008} \cdot k'$ for $k', a_0'$ relatively prime to $p_j$ . Then $\nu_{p_j}(a_0+ik) = \nu_{p_j}(p_j^{1008} (a_0' + ik')) =1009$ must hold, which identifies a class of the $p_j-1$ solutions $i \equiv r + sp_j \pmod {p^2}$ for $0 \leq r \leq p_j-1$ and any $0 \leq s \leq p_j-1$ that we can pick, excluding the solution which causes $p_j^2 \mid a_0' + ik'$ . Combining throughout all $j$ , this becomes a system of $n$ congruences wrt $p_0^2, p_1^2, p_2^2$ , which has a solution by CRT; hence such an $i$ exists. $\blacksquare$

This means that we can always find a counterexample for any starting $a_0$ and prime $p$ , so we are done.

This post has been edited 1 time. Last edited by HamstPan38825, Oct 10, 2021, 2:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IvoBucata

46 posts

IvoBucata

#26 h Nov 15, 2021, 1:15 PM • 1 Y

Y by Sprites

The answer is all positive integers $k$ for which there exists a prime $p$ such that $v_p(k)>1008$ except $2^{1009}$ .

We have that $2018=2.1009$ . Assume that for all $k$ there exists such an arithmetic progression and let $T$ be it's first element, thus all elements are of the form $T+ak$ where $a$ is a non negative integer. Let $d=gcd(T,k)$ thus $T=d.t$ ; $k=d.k_0$ and $gcd(t,k_0)=1$ and $d$ is a divisor of $k$ . Now $T+ak=d(t+ak_0)$ and from Dirichlet's there exists a prime $q$ larger than $d$ of the form $q=t+ak_0$ for some $a$ , so we get that $d$ should have a prime divisor $p$ with $v_p(d)=1009k-1$ and thus $v_p(d)> \geq 1008$ , thus $k$ should have a prime divisor $p$ with $v_p(k)\geq 1008$

Now I'll prove that it is not possible that for every prime $p$ to have $v_p(k)<1009$ . Let $d=p_1^{1008}p_2^{1008}\cdots p_k^{1008}.x$ and $k_0=y$ , where we have that for every prime $q$ $v_q(x)<1008$ ; also $gcd(y,t)=gcd(y,p_1p_2\cdots p_k)=1$ . Now $T+ak=d(t+ak_0)=p_1^{1008}p_2^{1008}\cdots p_k^{1008}.x(t+ay)$ Now let $x$ be an integer such that $t+xy\equiv 0 (mod p_1p_2\cdots p_k)$ , which exists because $ay$ goes trough all residues $(mod p_1p_2\cdots p_k)$ . Now let $a=bp_1p_2\cdots p_k +x$ for an integer $b$ which we can vary. Now $t+ay=t+byp_1p_2\cdots p_k+xy=t+xy+byp_1p_2\cdots p_k=p_1p_2\cdots p_k(\frac{t+xy}{p_1p_2\cdots p_k}+by)$ Now since $gcd(t+xy,y)=gcd(t,y)=1$ we have by Dirichlet that there exists a prime $q>k$ such that $q=\frac{t+xy}{p_1p_2\cdots p_k}+by$ for some $b$ $\Leftrightarrow$ There exists an integer $a$ for which $t+ay=qp_1p_2\cdots p_k$ . But this integer can't be interesting $\Leftrightarrow$ In order for an integer $k$ to satisfy the criteria there should be a prime $p$ such that $v_p(k)>1008$ .

Now if $p>2$ pick $d=p^{1008}$ and let $k_0=px$ . Now $T+ak=p^{1008}(t+apx)$ Pick a $t$ such that $t$ is equivalent to a non quadratic residue $mod$ $p$ and $t\equiv 1$ $mod$ every prime divisor of $k$ different than $p$ . This assures us that $p$ doesn't divide $t+apx$ and $t+apx$ is never a square(because of $mod$ $p$ ),thus all integers in this arithmetic progression are interesting. Now if $p=2$ and $k$ has some other prime divisor $q$ and $d=2^{1008}; k = 2^{1009}qx$ , then $T+ak=2^{1008}(t+a2qx)$ Now we can choose $t$ by CRT such that $t$ is equivalent to a non quadratic residue mod $q$ and $gcd(t,k)=1$ , so $t+a2qx$ is never a perfect square and it's not divisible by 2, so this works. Now if the only prime dividing $k$ is $2$ we have that if $v_2(k)\geq 1010$ by picking $d=2^{1008}$ and $t\equiv 3(mod$ $4)$ we can guarantee that $t+ak_0$ is never a square and it's not divisible by $2$ , so all such numbers work. If $k=2^{1009}$ we should have $d=2^{1009}$ and $k_0=2$ , but then $t+a2$ is going to be a perfect square and $2018$ won't divide $d(2^{1009}(t+2a))$ , so $k=2^{1009}$ doesn't work and we're done!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

guptaamitu1

656 posts

guptaamitu1

#27 h Feb 3, 2022, 8:39 PM

Y by

Here's an elementary solution without Dirichilet which uses size in NT (we will bound stuff).

Note Assume $v_p(k) \le 1008$ for all primes $p$ and FTSOC assume $k$ is interesting. Observe $2018 = 2 \cdot 1009$ and $1009$ is a prime. Suppose $a_1,a_2,\ldots$ was the arithmetic progression. For each $a_i$ , let $p_i$ be a prime satisfying $1009 \mid v_{p_i} (a_i) + 1$ .

Claim: For each $p \mid k$ , $\exists ~ c$ such that if $i \equiv c \pmod{p^2}$ , then $p_i \ne p$ .

Proof: Let $v_p(k) = e_1 \le 1008$ and $v_p(a_1 - k) = e_2$ . We have several cases:

$e_1 > e_2$ . As then $e_2 < 1008$ , so any $c$ works.
$e_1 = e_2$ . If $1008 \nmid e_2 + 1$ then $c = p$ works. Otherwise, a appropriate $c$ can be chosen so that $v_p(a_i)$ for $i \equiv c$ is $e_1 + 1$ .
$e_2 > e_1$ . If $1008 \nmid e_1 + 1$ , then any $c$ not divisible by $p$ works. Otherwise, if $e_2 = e_1 + 1$ then $c=0$ works and if $e_2 \ge e_1 + 2$ then $c = p$ works.

This proves our claim. $\square$

Now by CRT, we can find a constant $m$ such that all of $p_m,p_{m+n},p_{m + 2n},\ldots$ are co prime to both $k,n$ , where
$n = \prod_{p \mid k} p^2$ Define $q_i = p_{m + n(i-1)} ~ \forall ~ i \ge 1$ and $k ' = k \cdot n$ . Observe that:

$q_i^{1008} \le l + k' \cdot i$ for all $i$ , where $l$ is some fixed constant.
If $q_i = q_j = q$ , then $q^{1008} \mid n(i - j) \implies q^{1008} \mid i-j$ (as $\gcd(q,n) = 1$ ), in particular $|i - j| \ge q^{1008}$ .

Now for a sufficiently large $s$ , look at the set
$X = \{q_1,q_2,\ldots,q_{s^{1007}} \}$ By first condition, all elements of $X$ are $\le s$ . For each $j \in \{2,3,\ldots,s\}$ , denote by $b_j$ the number of time $j$ occurs in $X$ . By second condition we must have
$(b_j - 1) \cdot j^{1008} \le s^{1007} \qquad \forall~ 2 \le j \le s$ But we also have $b_2 + b_3 + \cdots + b_s = s^{1007}$ . This gives
$\begin{align*} s^{1007} - s &\le \sum_{j=2}^s (b_j - 1) \le \sum_{j=2}^s \frac{s^{1007}}{j^{1008}} \end{align*}$ So to obtain our contradiction, it suffices to show $\displaystyle \sum_{j \ge 2} \frac{1}{j^{1008}} < 1 - \epsilon$ for some fixed $\epsilon > 0$ . This just follows by $\frac{1}{1^2} + \frac{1}{2^2} + \cdots = \frac{\pi^2}{6}$ . But for an elementary proof, note
$\begin{align*} \sum_{j \ge 2} \frac{1}{j^{1008}} &\le \sum_{j \ge 2} \frac{1}{j^3} = \sum_{i \ge 1} \left( \sum_{j=2^i}^{2^{i+1}} \frac{1}{j^3} \right) \le \sum_{i \ge 1} \left( \frac{2^i}{2^{3i}} \right) = \sum_{i \ge 1} \frac{1}{4^i} = \frac{1}{3} \end{align*}$ So we obtain our desired contradiction, completing the proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7303 posts

DottedCaculator

#28 h Feb 7, 2022, 4:03 PM • 1 Y

Y by centslordm

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5000 posts

IAmTheHazard

#29 h Apr 11, 2022, 2:17 PM • 1 Y

Y by centslordm

Here's a solution that uses bullet points three times!

The answer is all $k$ such that there exists a $p$ with $\nu_p(k) \geq 1009$ , except for $k=2^{1009}$ .
Call a number satisfying the (arithmetic progression) condition good, and call it bad otherwise. Note that if a number of good, so is any multiple of it, so if a number is bad, all divisors of it are bad too. Further, $k$ is bad if and only if every residue class of $k$ contains arbitrarily large uninteresting numbers. Finally, note that $1009$ is prime.
To begin, we prove that all of the claimed numbers are good:

If $p>2$ , it suffices to show that $p^{1009}$ is good. Let $r$ be an NQR modulo $p$ . Then every number $n \equiv rp^{1008} \pmod{p^{1009}}$ has $\nu_p(n)=1008$ , so $1009 \mid d(n)$ . Also, $\tfrac{n}{p^{1008}}$ is never a square (else $r$ is a quadratic residue), hence $n$ isn't either so $2 \mid d(n)$ . Combined these imply $2018 \mid d(n)$ as advertised.
For $p=2$ , $k=2^{1009}p$ is good for all $p \neq 2$ . Again, take $r$ to be an NQR modulo $p$ , and let $n$ satisfy $n \equiv 2^{1008} \pmod{2^{1009}}$ and $n \equiv r \pmod{p}$ . Then for mod $p$ reasons $n$ is never a square, and we also have $\nu_2(n)=1008$ , so $2018 \mid d(n)$ .
Also for $p=2$ , $k=2^{1010}$ is good for all $p$ by taking $n \equiv 3\cdot 2^{1008} \pmod{2^{1010}}$ . This works as $\nu_2(n)=1008$ , so $n=2^{1008}(4k+3)$ , and $4k+3$ is never a square so $2 \mid d(n)$ .

Most of the rest of the problem is resolved with the following claim.

Claim: For any distinct primes $p_1,\ldots,p_k$ , $N=(p_1\ldots p_k)^{1008}$ is bad.
Proof: Let $1 \leq r \leq N$ and consider the residue class $r \pmod{N}$ . Let $M=(p_1\ldots p_k)^{1010}$ , and consider the residue class $c \pmod{M}$ satisfying (by Chinese Remainder Theorem):

For all primes $p_i$ such that $\nu_{p_i}(r)<1008$ , let $c \equiv r \pmod{p_i^{1010}}$ . Clearly $c \equiv r \pmod{p_i^{1008}}$ as well.
For all primes $p_i$ such that $\nu_{p_i}(r)\geq 1008$ , let $c \equiv p_i^{1009} \pmod{p_i^{1010}}$ . Then $c \equiv r \equiv 0 \pmod{p_i^{1008}}$ .

This implies that the residue class $c \pmod{M}$ is a subset of the residue class $r \pmod{N}$ . By Dirichlet, there exist arbitrarily large elements of this residue class that are $n=q \cdot \gcd(c,M)$ where $q \nmid M$ is a prime. Since $\nu_{p_i}(c) \in \{0,\ldots,1007,1009\}$ , $\nu_{p_i}(M)=1010$ , and there are no other primes dividing $M$ , it follows that any prime $p \mid n$ satisfies $\nu_p(n) \not \equiv -1 \pmod{1009}$ , hence $1009 \nmid d(n)$ . It then follows that $n$ is uninteresting, so $N$ is bad as desired.

All that remains is to show that $2^{1009}$ is bad. We split this into three cases based on the residue of $n$ :

For $n \equiv 0 \pmod{2^{1009}}$ , take $n=2^{1009i}$ , so $1009 \nmid d(n)=1009i+1$ .
For $n \equiv 2^{1008} \pmod{2^{1009}}$ , we can write $n=2^{1008}(2k+1)$ . Taking $2k+1$ to be some arbitrarily large square (which trivially exists) makes $n$ a square as well, whence $2 \nmid d(n)$ .
Otherwise, let $\nu_2(n)=a \leq 1008$ , and let $n'=\tfrac{n}{2^a}$ . Then we can write $n=2^a(2^{1009-a}k+n')$ . If $a \geq 1$ , we can apply the above claim (since there exist arbitrarily large $n$ with $1009 \nmid d(n)$ ). Otherwise $a=0$ , and we can get $n$ to equal arbitrarily large primes, in which case $1009 \nmid d(n)=2$ .

Combined, these cases imply that $2^{1009}$ is bad as desired, so we obtain the solution set as described. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cali.Math

128 posts

Cali.Math

#30 h Jul 10, 2023, 3:42 PM

Y by

We uploaded our solution https://calimath.org/pdf/ChinaTST2018-2.pdf on youtube https://youtu.be/Ci8d0jYGuzc.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

thdnder

193 posts

thdnder

#31 h Oct 3, 2023, 4:02 PM

Y by

The answer is $k$ such that there exist $p$ such that $\nu_{p}(k) \ge 1009$ and $\frac{k}{p^{1008}} \neq 1, 2$ , i.e $k \neq 2^{1009}$ .

Firstly, we'll construct such arithmetic progression for such $k$ . Let $a$ be a first number of the arithmetic progress. Take $a = p^{1008} \cdot b$ , where $b$ satisfies $(\frac{b}{p}) = -1$ . Then the $n$ th number of the arithmetic progression is $p^{1008}(b + \frac{k}{p^{1008}}n)$ .Since $b + \frac{k}{p^{1008}}n$ isn't divisible by $p$ and $(b + \frac{k}{p^{1008}}n)$ isn't perfect square, so $2018 \mid d(p^{1008}(b + \frac{k}{p^{1008}}n))$ .

Now we'll prove that there exist $p$ such that $\nu_{p}(k) \ge 1009$ . Let $a$ be first number of the arithmetic progression. Then by Dirichlet's theorem, there exists $n$ such that $\frac{a}{\gcd(a, k)} + \frac{kn}{\gcd(a, k)}$ is prime. Thus $2018 \mid 2d(\gcd(a, k))$ , so $1009 \mid \gcd(a, k)$ . Therefore there exists prime $p$ such that $\nu_p(k) \ge 1008$ . Assume $\nu_p(k) = 1008$ . Let $\gcd(a, k) = p^{1008}\cdot d$ and $a_1 = \frac{a}{\gcd(a, k)}$ and $k_1 = \frac{k}{\gcd(a, k)}$ . Then take $r$ such that $\nu_p(a_1 + k_1n) = 1$ . By Dirichlet's theorem, there exists $n$ such that $a_1 + k_1(r + p^2n) = pq$ for some prime $q$ . Thus $d(a + k(r + p^2n))$ isn't divisible by $2018$ , a contradiction. Thus there exists $p$ such that $\nu_p(k) \ge 1009$ . And it's not hard to check that $2^{1009}$ isn't the answer. This completes proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

711 posts

Mathandski

#32 h Aug 21, 2024, 8:41 PM

Y by

$\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

791 posts

shendrew7

#33 h Oct 5, 2024, 3:16 AM

Y by

We claim the answer is all $k$ such that $v_pk \ge 1009$ some prime $p$ except $k = 2^{1009}$ . Suppose our starting term is $a$ :

Construction: Factor each term as
$a+kn = p^{1008}(p^{v_pk-1008}+a').$
Suppose we set $a'$ to be a NQR modulo $p$ if $p$ odd or a NQR modulo 4 if working with $v_2k \ge 1010$ . The two factors are relatively prime, and since all squares have an even number of divisors,
$d(a+kn) = d(p^{1008}) \cdot d(p^{v_pk-1008}+a') = 1009 \cdot \text{even} \equiv 0 \pmod{2018}.$
Counterexample: Our first case otherwise is to eliminate the case $k = 2^{1009}$ , which is easy using casework on $v_pa$ and factoring out $2^{1009-v_pa}$ .
Otherwise, we must have $n = \prod p_i^{e_i} \mid \pi p_i{1008}$ . Suppose $\gcd(a,n) = \prod p_i^{f_i}$ . If we factor out $\gcd(a,n)$ from $a+kn$ , we have two factors which are sometimes coprime but sometimes share prime factors $p_i$ through CRT. It's easy to use this to our advantage to show that we have some term whose divisor count is not a multiple of 1009 using casework on whether we have some $f_i = e_i = 1008$ or not. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

962 posts

bjump

#34 h Dec 26, 2024, 2:06 AM

Y by

MERRY CHRISTMAS !!!

We claim that all possible $k$ must have an odd prime $p$ such that $p^{1009}$ divides $k$ , be divisible by $2^{2010}$ , or be able to be written in the form $q \cdot 2^{2009}$ where $q$ is has an odd prime divisor.

For a construction if an odd prime $p$ exists such that $p^{1009}$ divides $k$ take an NQR modulo $p$ call it $b$ and make the sequence $a_n = b\cdot p^{1008} + nk$ . If $k$ is divisible by $2^{1010}$ take the sequence $a_n = 3 \cdot 2^{1008} + nk$ . If $k = q \cdot 2^{2009}$ take an NQR for some odd prime that divides $q$ call it $c$ take the sequence $a_n = c \cdot 2^{1008} + kn$ , unless $c$ is even then increase it by that odd prime amount.

Now if $\nu_p (k ) \le 1008$ for all prime $p$ . Then each term of the arithmetic sequence isn't divisible by $p$ or there exist periodic terms with period $p^{2010-\nu_p (k)}$ such that $\nu_p (k) =1009$ . By infinite CRT there exists a term that satisfies one of these properties for each prime $p$ , a contradiction because if this was true then $d(\text{that term}) =1010^z$ for some $z$ which contains no factors of $1009$ . If $k=2^{1009}$ then obviously every term of the sequnce must be in the for $a_n = \text{odd} \cdot 2^{1008} + 2^{1009}n = 2^{1008}(\text{odd}+2n)$ for each odd there exists a value of $n$ such that $a_n$ is a square so $d(a_n) \equiv 1 \pmod{2}$ a contradiction and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1720 posts

OronSH

#35 h Yesterday at 9:13 PM

Y by

Answer is multiples of a power of $1009$ , other than $2^{1009}$ .

Construction for $cp^{1009}$ is pick numbers $\equiv n\pmod{cp}$ times $p^{1008}$ where $p\nmid n$ and $n$ is NQR.

To bound the idea is that if $p^{1009}\nmid k$ for all $p$ then for all primes $q\le k$ a nonzero density of $n$ in the AP have $\nu_q(n)\not\equiv -1\pmod 1009$ , either $<1008$ when $\nu_q(k)<1008$ or sometimes $=1009$ when $\nu_q(k)=1008$ . For each $q$ we can make these those in some residue class for some power of $q$ , so if we only look at these we get another AP whose difference is still $k$ smooth. Now mirror the proof of squarefree density to get an element of this AP which does not have any factor of a prime $>k$ more than once.

If $k=2^{1009}$ then either do the same thing as above which fails only if the AP consists of odd multiples of $2^{1008}$ . In this case eventually one of them is a square and it has an odd number of factors, failing.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tchange7575

2156 posts

tchange7575

#36 h Yesterday at 9:20 PM

Y by

To determine the values of $k$ such that there is an infinite arithmetic progression with common difference $k$ whose terms are all interesting, we need to ensure that for any starting value $a$ , $a + nk$ (for all integers $n \geq 0$ ) has a number of divisors divisible by 2018. This implies:

$d(a + nk) \equiv 0 \pmod{2018}$
The prime factorization of 2018 is:

$2018 = 2 \times 1009$
Thus, $d(a + nk)$ must be a multiple of both 2 and 1009. If we can ensure that $d(a + nk) \equiv 0 \pmod{1009}$ , then $d(a + nk)$ will naturally be even because $d(n)$ is always even when $n$ is a perfect square.

To analyze this, consider the following structure of numbers in arithmetic progressions. The number of divisors $d(n)$ of a number $n$ with prime factorization $n = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$ is given by:

$d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_m + 1)$
We need this product to be divisible by 1009. One way this can happen is if one of the factors, say $(e_i + 1)$ , is a multiple of 1009, which implies $e_i = 1009k_i - 1$ for some integer $k_i$ . This can be achieved if $n$ is a perfect power with a sufficiently large exponent.

Since $d(a + nk) \equiv 0 \pmod{1009}$ must hold for all terms, we should ensure that the number of divisors is large enough for any $a$ and $a \equiv 0 \pmod{k}$ . Therefore, $k$ itself must be a multiple of 1009 to ensure the structure of the factorization to yield a divisor count of 2018.

Thus, $k$ must be a multiple of the least significant factor, which is 1009. Therefore, any arithmetic progression with common difference $k = 1009$ will ensure that all terms $a + nk$ have $d(a + nk) \equiv 0 \pmod{2018}$ .

Therefore, the positive integers $k$ such that there exists an infinite arithmetic progression with common difference $k$ whose terms are all interesting are:

$\boxed{1009}$

Z K Y

N Quick Reply