Competition problem — Number theory

Library / /174 of 299

Number theory Difficulty 6.7 National Olympiad Prove it Iran

a.
Prove that there doesn't exist a sequence of positive integers like $a_1, a_2, a_3, \dots$ such that for all $i, j \in \mathbb{Z}^+$ with $i < j$
$\text{gcd}(a_i + j, a_j + i) = 1.$

b.
Assume that $p$ is an odd prime number. Prove that there exists a sequence of positive integers like $a_1, a_2, a_3, \dots$ such that for all $i, j \in \mathbb{Z}^+$ with $i < j$ , $\text{gcd}(a_i + j, a_j + i)$ is divisible by $p$ .

Solution

a.
If $i, a_i, j$ and $a_j$ are all odd or are all even then $\text{gcd}(a_i + j, a_j + i)$ will be an even number. So except for at most two values of $i$ , the parity of $i, a_i$ is different. So there exists some even numbers $i, j$ such that $a_i, a_j$ are both odd which, again, we conclude that $\text{gcd}(a_i + j, a_j + i)$ is an even number. Hence, is greater than 1. Thus no such sequence exists. $\square$

b.
Consider the following sequence
$a_n = pn - n + 1.$
If $p \mid a_n + m = pn - n + 1 + m$ and $p \mid a_m + n = pm - m + 1 + n$ , for some $m, n \in \mathbb{Z}^+$ with subtracting these two relations we obtain
$p \mid n - m$
And if we add it two the first relation we'll have $p \mid pn + 1$ which is a contradiction. Therefore the given sequence satisfies the desired conditions. $\square$

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.