Maths Olympiad Prep

Library / /87 of 106

Number theory Difficulty 8.5 Shortlist Find the answer

A number nn is interesting 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. Fractions can be typed as 3/2, and spacing doesn't matter.

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: All\boxed{\text{All}} } k \text{} such that } v_p(k) 2018\geq 2018 \text{} for some prime } p \text{} or } v_q(k) 1009\geq 1009 \text{} and } v_r(k) 2\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 reproduced verbatim; metadata (topic, difficulty) added by this project.