Maths Olympiad Prep

Library / /82 of 97

Number theory Difficulty 8.5 Shortlist Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

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

To solve this, we need to identify the conditions on k k that allow for such an arithmetic progression. We will show that k k must satisfy one of the following two conditions:
1. There exists a prime number p p such that vp(k)2018 v_p(k) \geq 2018 .
2. There exist two distinct prime numbers q q and r r such that vq(k)1009 v_q(k) \geq 1009 and vr(k)2 v_r(k) \geq 2 .

### Proof:
1. Condition 1:
If k k has a prime factor p p with vp(k)2018 v_p(k) \geq 2018 , then consider the arithmetic progression {p2017(p1+nkp2017)}nZ+ \{ p^{2017}(p-1 + n \frac{k}{p^{2017}}) \}_{n \in \mathbb{Z}^+} . Here, pkp2017 p \mid \frac{k}{p^{2017}} and p(p1) p \nmid (p-1) . Each term in this progression will have a number of divisors divisible by 2018, making all terms interesting.

2. Condition 2:
If k k has two distinct prime factors q q and r r with vq(k)1009 v_q(k) \geq 1009 and vr(k)2 v_r(k) \geq 2 , then consider the arithmetic progression {q1008r(k1+nkq1008r)}nZ+ \{ q^{1008}r(k-1 + n \frac{k}{q^{1008}r}) \}_{n \in \mathbb{Z}^+} . Here, q,rkq1008r q, r \mid \frac{k}{q^{1008}r} and q,r(k1) q, r \nmid (k-1) . Each term in this progression will also have a number of divisors divisible by 2018, making all terms interesting.

### Inductive Step:
We use induction to show that if an infinite arithmetic progression with common difference m m exists, then m m must satisfy one of the two conditions above.

- Base Case:
For m=1 m = 1 , there is no such arithmetic progression.

- Inductive Hypothesis:
Assume the statement is true for all mk m \leq k .

- Inductive Step:
Suppose there exists an arithmetic progression {a+nd}nZ+ \{ a + nd \}_{n \in \mathbb{Z}^+} with common difference d=m d = m satisfying the condition. If m m does not satisfy either condition, we derive a contradiction by considering the prime factorization of m m and using properties of divisors and prime numbers.

Thus, the positive integers k k that allow for an infinite arithmetic progression of interesting numbers must satisfy one of the two conditions stated above.

The answer is: \boxed{\text{All } k \text{ such that } v_p(k) \geq 2018 \text{ for some prime } p \text{ or } v_q(k) \geq 1009 \text{ and } v_r(k) \geq 2 \text{ for some distinct primes } q \text{ and } r.}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.