Wrong!!!

I think the answer is negative. First, let us narrow down all possible values of $a_n$. Claim 1 : $n\mid 2a_n^2$ for any $n$. Proof : Just notice that \begin{align*} n&\mid a_n^2 + a_{2n}^2 \\ n&\mid a_{2n}^2 + a_{3n}^2 \\ n&\mid a_n^2 + a_{3n}^2 \end{align*}which is enough to imply $n\mid 2a_n^2$. Claim 2 : $\frac{\nu_p(n)}{2} \leqslant \nu_p(a_n) \leqslant 2\nu_p(n)$ for any prime $p$ and $n\in\mathbb{Z}^+$. Proof : We first prove the lower bound by splitting into two cases. If $p$ is odd then by Claim 1, $\nu_p(2a_n^2) = 2\nu_p(a_n)\geqslant \nu_p(n)$ so we are done. If $p=2$ then by Claim 1, we get $\nu_2(a_n) \geqslant \tfrac{\nu_2(n)-1}{2}$. Now we have to improve a little bit. Let $t=\nu_2(n)$ and $M=2^{2019t}$. Thus $2^{1000t}\mid a_M$ (Claim 1) thus $$2^t\mid a_M^2 + a_n^2 \implies 2^t\mid a_n^2\implies \nu_2(a_n)\geqslant\frac{t}{2}.$$ Now for the right side, let $t=\nu_p(a_n)$. Take $M=p^{2019t}$. Clearly, $\nu_p(a_M)>1000t$ thus $$\min\{\nu_p(a_n), \nu_p(a_M)\} \leqslant \nu_p(n^2+M^2) \leqslant 2t$$thus $\nu_p(a_n)\leqslant 2t$ as desired. Now, we need to focus on the existence of good sequences. Claim 3 : A sequence is good as long as $\frac{\nu_p(n)}{2} \leqslant \nu_p(a_n) \leqslant 2\nu_p(n)$ for any prime $p$ and $n\in\mathbb{Z}^+$. Proof : To get the first condition, just note that $$\nu_p(\gcd(m,n)) = \min\{\nu_p(m), \nu_p(n)\} \leqslant \min\{2\nu_p(a_m), 2\nu_p(a_n)\} \leqslant \nu_p(a_m^2+a_n^2)$$Now we proceed to verify the second condition. $$\nu_p(\gcd(a_m, a_n))\leqslant \min\{\nu_p(a_m), \nu_p(a_n)\} \leqslant \min\{2\nu_p(m), 2\nu_p(n)\}\leqslant\nu_p(m^2+n^2)$$ Claim 2,3 implies that a sequence is good if and only if $\frac{\nu_p(n)}{2}\leqslant\nu_p(a_n)\leqslant 2\nu_p(n).$ for any prime $p$ and $n\in\mathbb{Z}^+$. Thus if $k=\prod\limits_{i=1}^r p_i^{e_i}$ where $p_1,p_2,...,p_r$ are primes and $e_1,e_2,...,e_r\in\mathbb{Z}+$. Then the total number of $k$-good number is $$\prod_{i=1}^r\left(2e_i - \left\lceil\frac{e_i}{2}\right\rceil + 1\right).$$Each factor is $3x+1$ if $e_i=2x$ and $3x+2$ if $e_i=2x+1$. This means the number of all $k$-good number is never divisible by $3$, contradiction.

Sniped The answer is negative; there does not exist such $k$. We first characterize all good sequences: Claim wrote: A sequence of integers $\{a_k \}$ is good if and only if $m \mid a_m^2$ and $a_m \mid m^2$, for each $m \in \mathbb{N}$. If the claim holds, then one can check that the number of $k$-good positive integers could never be a multiple of $3$; hence there are no such $k$. Now we prove the claim. Consider a good sequence $\{a_k \}$, and consider some $m \in \mathbb{N}$, and a prime $p$ dividing $m$. Take $n=m \times s$, where $s \ge 1$: $\gcd(m,n)=m \mid a_m^2+a_{ms}^2$; or $m \mid a_m^2 +a_{2m}^2$ and $m \mid a_m^2+a_{4m}^2$. Replacing $m \leftarrow 2m$ gives $2m \mid a_{2m}^2+a_{4m}^2$. Then $2a_m^2 \equiv (a_m^2+a_{2m}^2)+(a_m^2+a_{4m}^2)-(a_{2m}^2+a_{4m}^2) \equiv 0 \pmod {m}$, or $m$ divides $2a_m^2$. If the $v_2$ part is equal; i.e. $v_2(m)=v_2(2a_m^2)$, then $m \mid a_m^2+a_{2m}^2$ implies that $v_2(a_{2m}^2)=v_2(a_{m}^2)$, which contradicts $2m \mid 2a_{2m}^2$. Hence $m \mid a_m^2$. For the other part, take $n=2a_m^2$, and note that $2a_m^2 \mid {2a_{2a_m^2}}^2 \implies a_m \mid a_{2a_m^2}=a_n$. Then $\gcd(a_m, a_n)=a_m$ divides $m^2+n^2=m^2+4a_m^4$, or $a_m$ divides $m^2$, as desired. Now consider a integer sequence such that $m \mid a_m^2$ and $a_m \mid m^2$ for each $m \in \mathbb{N}$; and we claim that the two conditions simultaneously holds for all $m,n \in \mathbb{N}$. Let $p^{s} \parallel \gcd(m,n)$, or $p^{s}$ divides both $m$ and $n$. Then $p^s \mid m \mid a_{m}^2$, which gives $p^s \mid a_m^2+a_n^2$. Note that the second one is symmetric with the first; so the second condition holds for all $m,n \in \mathbb{N}$. Hence the claim is proved, and we are done. $\square$

Felt a bit like IMO 2018/5(Changing divisiblity to v_p) $\textbf {Claim} $:Sequence is good if and only if $n\mid a^2_n $ and $a_n\mid n^2$. Proof:So taking $m,n $ as $(n,2n)$,$(2n,3n)$,$(3n,n) $ we get that $n\mid 2\cdot a_n^2$ so for odd prime $p $ we have $\nu_p (n)\le 2\cdot \nu_p (a_n) $ and for $p=2$ take $m $ such that $\nu_2 (m) $ is sufficiently large then $\nu_2 (a_m) $ is sufficiently large which means $\nu_2 (n)\leq 2\cdot \nu_2 (a_n) $ then $n\mid a_n^2$ .To show $a_n\mid n^2$ we do the exactly same things:take $m $ such that $\nu_p (m) $ is sufficiently large then $\nu_p (a_m) $ is sufficuently large which means that $\nu_p (a_n)\leq 2\cdot \nu_p (n) $ then $a_n\mid n^2$. Let's show that any sequence of $a_n $ 's satisfying the above divisiblities is good. $\nu_p (gcd (m,n))=min (\nu_p (m),\nu_p (n))\leq 2\cdot min (\nu_p (a_m),\nu_p (a_n))=min (\nu_p (a_m^2),\nu_p (a_n^2))\leq \nu_p (a_m^2+a_n^2) $ similarly we can show second condition holds. Then let $k=p_1^{c_1}\cdot p_2^{c_2}...\cdot p_t^{c_t} $ so $a $ must have the same prime divisors according to the divisiblity conditions. Let $a=p_1^{d_1}\cdot p_2^{d_2}...\cdot p_t^{d_t} $ so the number of $a $'s is $(2a_1-\lfloor\frac{a_1+1}{2}\rfloor+1)\cdot ... (2a_t-\lfloor\frac{a_t+1}{2}\rfloor+1) $ since $3,673$ are primes some factor should be equal to $1$ or $3$ which clearly wrong.So the answer is no.

Solution with Aahan Chatterjee, Aditya Khurmi, Anshul Guha, Anushka Aggarwal, Derek Liu, Grant Yu, Marvin Mao, Max Lu, Rishabh Dhiman, Robin Son, Rohan Goyal, William Wang, Eric Shen, Paul Hamrick, and others: The answer is no. In fact, we describe all good sequences: they are the ones satisfying \[ n \mid a_n^2 \text{ and } a_n \mid n^2 \]for every integer $n$. In other words, for any prime $p$ and integer $n$, the only constraint is that \[ \frac{\nu_p(n)}{2} \le \nu_p(a_n) \le 2\nu_p(n). \qquad (\heartsuit) \] It is not hard to check that any such sequence works by taking $\nu_p$'s. For the other direction, we proceed in three steps. Take $(n,2n)$, $(2n,3n)$ and $(n,3n)$ in the given statement to get $n$ divides $a_n^2 + a_{2n}^2$, $a_{2n}^2 + a_{3n}^2$ and $a_n^2 + a_{3n^2}$. This implies \[ n \mid 2a_n^2. \]This is almost the left half of $(\heartsuit)$, except for $p=2$ where it is off by one. Now we prove $(\heartsuit)$ in one go. Let $p$ be any prime and $n$ any index. We will pick $m = p^{2\nu_p(a_n) + \nu_p(n) + 1}$ alongside $n$ in the given (or really any very big power of $p$). This ensures $\nu_p(m) > \nu_p(n)$ and by the previous bullet, $\nu_p(a_m) > \frac{\nu_p(m)-1}{2}> \nu_p(a_n)$. This works even if $p=2$. Then we have \[ \nu_p(n) = \nu_p(\gcd(m,n)) \le \nu_p(a_m^2+a_n^2) = \nu_p(a_n^2) \]as well as \[ \nu_p(a_n) = \nu_p(\gcd(a_m,a_n)) \le \nu_p(m^2+n^2) = \nu_p(n^2) \]which gives $(\heartsuit)$. It remains to check no such $i$ exists as described. Note that for each prime $p$, there are $2\nu_p(i) - \left\lfloor \frac{\nu_p(i)}{2} \right\rfloor$ choices for $\nu_p(a_i)$. It is easy to check this is in fact never divisible by $3$, so the product of such numbers cannot equal $2019$.

v_Enhance wrote:

You have $\nu_p (a_m)>\nu_p (a_n)$. But you have $\nu_p (a_n)\le \nu_p (\gcd (a_m,a_n)) $ Is not $\nu_p (a_n)= \nu_p (\gcd (a_m,a_n))$? @below: I know that's true for $\le $ but isn't the same say you: I'm stupid and I'm smart or stupid (you can conclude the answer, but there are an option don't needed)

Yes, you're correct, I meant to write "=" instead (of course $\le$ is true too ).

Let $P(m,n)$ denote $\gcd(m,n) \mid a_m^2+a_n^2$ and $Q(m,n)$ denote $\gcd(a_m,a_n) \mid m^2+n^2$. Claim: $v_p(a_n) \ge \tfrac12 v_p(n)$ for any prime $p$. Proof: Note \begin{align*} P(n,2n) &: n\mid a_{2n}^2+a_n^2 \\ P(n,3n) &: n\mid a_{3n}^2+a_n^2 \\ P(2n,3n) &: n\mid a_{2n}^2+a_{3n}^2. \end{align*}The first two imply $n\mid a_{2n}^2+a_{3n}^2+2a_n^2$, and combined with the third, we get $n\mid 2a_n^2$. So for an odd prime $p$, we have \[ v_p(2a_n^2) = 2v_p(a_n) \ge v_p(n) \implies v_p(a_n) \ge \frac{v_p(n)}{2}\]and for $p=2$ we have \[ v_2(a_n) \ge \frac{v_2(n)-1}{2}. \]We claim that in fact, we can strengthen the above to $v_2(a_n) \ge \tfrac12 v_2(n)$. Let $x=2^{100v_2(n) + 100v_2(a_n)}$. Then looking at $v_2$ of $P(2^x,n)$ gives \[ v_2\big(a_x^2+a_n^2 \big) \ge \min\big\{v_2(x), v_2(n)\big\} = v_2(n). \]We claim $v_2(a_x) \not = v_2(a_n)$. Indeed, $v_2(a_x) \ge \frac{v_2(x)-1}{2} > v_2(a_n)$. Therefore, \[ v_2(a_{x}^2+a_n^2) = \min \big\{ v_2(a_{x}^2), v_2(a_n^2)\big\}=2\min \{ v_2(a_x), v_2(a_n)\} = 2v_2(a_n), \]giving us $2v_2(a_n) \ge v_2(n)$, as desired. $\square$ Claim: $v_p(a_n) \le 2v_p(n)$. Proof: Taking the $v_p$ of $Q(m,n)$ gives $v_p(m^2+n^2) \ge \min\{v_p(a_m), v_p(a_n)\}$. Take $m=p^{x}$ where $x=100v_p(a_n)+100v_p(n)$. Then \[ v_p(p^{2x}+n^2) \ge \min \{x, v_p(a_n)\} = v_p(a_n). \]Clearly, $v_p(p^{2x}+n^2) = v_p(n^2) = 2v_p(n)$, so $2v_p(n)\ge v_p(a_n)$, as desired. $\square$ Hence, for any prime $p$, \[ \frac{v_p(n)}{2} \le v_p(a_n) \le 2v_p(n). \]This means \begin{align*} v_p(n) &\le 2v_p(a_n) =v_p(a_n^2) \forall p \implies \boxed{n\mid a_n^2} \\ v_p(a_n) &\le 2v_p(n) = v_p(n^2) \forall p \implies \boxed{a_n\mid n^2}. \end{align*}Therefore, any good sequence $\{a_n\}$ satisfies $n\mid a_n^2$ and $a_n\mid n^2$. We claim that any sequence satisfying these two properties is good. This is easy to check with $v_p$'s, now that we have all the necessary conditions. Now, we basically just choose the $v_p$ for each prime $p$; the primes act independently now that we have classified $v_p(a_n)$ completely. There are \[ 2v_p(k) - \left\lceil \frac{v_p(k)}{2} \right\rceil + 1\]choices for $v_p(a_k)$, for each prime $p$. Hence the total number is the product of the above, over all primes $p$. However, it is easy to check that the above is never a multiple of 3. So it is not possible for 2019.

Amazing Problem. The answer is $\boxed{no.}$ Claim 01. $m \mid 2a_m^2$ for all $m \in \mathbb{N}$. Proof. We have $\gcd(m,2m) = \gcd(m,3m) = \gcd(2m,3m) = m$ and therefore \[ m \mid (a_m^2 + a_{2m}^2) + (a_m^2 + a_{3m}^2) - (a_{2m}^2 + a_{3m}^2) = 2a_m^2 \] Claim 02. For any prime numbers $p$ and natural numbers $n$, we have \[ \frac{\nu_p(n)}{2} \le \nu_p(a_n) \le 2 \nu_p(n) \]Proof. We'll first do this for odd primes $p$. By Claim 01, we have \[ \nu_p(m) \le \nu_p(2a_m^2) = \nu_p(a_m^2) = 2 \nu_p(a_m) \Longrightarrow \frac{\nu_p(m)}{2} \le \nu_p(a_m) .\]Now, notice that $\gcd(a_m, a_n) \mid m^2 + n^2$. Take $n = p^{2 \nu_p(a_m) + 2}$. Therefore, by our previous result, \[ \nu_p(a_n) = \nu_p(a_{p^{2 \nu_p(a_m) + 2}}) \ge \frac{\nu_p(p^{2 \nu_p(a_m) + 2})}{2} = \frac{2 \nu_p(a_m) + 2}{2} = \nu_p(a_m) + 1 > \nu_p(a_m) \]and \[ \nu_p(n) = 2 \nu_p(a_m) + 2 \ge \nu_p(m) + 2 > \nu_p(m) \]Therefore, we have established that \[ \nu_p(a_m) = \min \{ \nu_p(a_m), \nu_p(a_n) \} \le \nu_p(m^2 + n^2) = \nu_p(m^2) = 2 \nu_p(m)\]for all $m \in \mathbb{N}$. Now, we have $\nu_2(m) \le \nu_2(2a_m^2) = 2 \nu_2(a_m) + 1$, a slightly weaker bound. But this bound is enough to prove the upper bound, that is, with a similar approach. Take $n = 2^{2 \nu_2(a_m) + 2}$. Therefore, by our previous result, \[ \nu_2(a_n) = \nu_2( a_{2^{2 \nu_2(a_m) + 2}}) \ge \frac{\nu_2(2^{2 \nu_2(a_m) + 2}) - 1}{2} = \frac{2 \nu_2(a_m) + 1}{2} > \nu_2(a_m) \]and \[ \nu_2(n) = 2 \nu_2(a_m) + 2 \ge \nu_2(m) + 1 > \nu_2(m) \]Therefore, we have established that \[ \nu_2(a_m) = \min \{ \nu_2(a_m), \nu_2(a_n) \} \le \nu_2(m^2 + n^2) = \nu_2(m^2) = 2 \nu_2(m) \]Similarly, from above, we have \[ \nu_2(m) = \min \{ \nu_2(m), \nu_2(n) \} \le \nu_2(a_m^2 + a_n^2) = \nu_2(a_m^2) = 2 \nu_2(a_m) \]We are done. Claim 03. Any sequence of natural numbers $\{ a_n \}$ satisfying Claim 02 must be good. Proof. Suprisingly, we just need to prove that Claim 02. is a sufficient condition for any good sequence. To prove $\gcd(m,n) \mid a_m^2 + a_n^2$ for any $m,n \in \mathbb{N}$, notice that for any prime number $p$, we have \[ \min \{ \nu_p(m), \nu_p(n) \} = 2 \min \left \{ \frac{\nu_p(m)}{2}, \frac{\nu_p(n)}{2} \right \} \le 2 \min \{ \nu_p(a_m), \nu_p(a_n) \} = \min \{ \nu_p(a_m^2), \nu_p(a_n^2) \} \le \nu_p(a_m^2 + a_n^2) \]To prove $\gcd(a_m, a_n) \mid m^2 + n^2$ for any $m,n \in \mathbb{N}$, notice that for any prime number $p$, we have \[ \min \{ \nu_p(a_m), \nu_p(a_n) \} \le \min \{ 2 \nu_p(m), 2 \nu_p(n) \} = \min \{ \nu_p(m^2), \nu_p(n^2) \} \le \nu_p(m^2 + n^2) \] Finally, we just need the fact that $2019$ is a multiple of $3$. We'll prove that for any natural number $m$, there won't be any integer $k$ such that there exists exactly $3m$ $k$-good positive integers. From Claim 03, we know that we can generate all good sequences one by one by picking the $\nu_p$ such that it satisfies the sufficient condition. It suffices to prove that there does not exist a prime number $p$ in which the number of ways we can assign $nu_p(a_n)$ is a multiple of $3$. Now, we consider $2$ cases: If $\nu_p(n)$ is even, then the number of ways to choose $\nu_p(a_n)$ is \[ 2 \nu_p(n) - \frac{\nu_p(n)}{2} + 1 = 3 \left( \frac{\nu_p(n)}{2} \right) + 1 \not \equiv 0 \ (\text{mod} \ 3). \]If $\nu_p(n)$ is odd, then the number of ways to choose $\nu_p(a_n)$ is \[ 2 \nu_p(n) - \left \lceil \frac{\nu_p(n)}{2} \right \rceil + 1 = 2 \nu_p(n) - \frac{\nu_p(n) + 1}{2} + 1 = \frac{3\nu_p(n) + 1}{2} \not \equiv 0 \ (\text{mod} \ 3) \]Therefore, we are done. Remark. Claim 01 was pretty natural, you need to find something to loosen up the condition, something solely dependent on $a_m$ to get information on $a_n$ for every $n \in \mathbb{N}$ and since we can't substitute $n = m$ here, it's pretty natural to try $2m, 3m$ and ended up with $m \mid 2a_m^2$. For me, the leap of faith was actually Claim 02. After getting Claim 01, I spent some times playing with $p \mid a_{kp}$ for all $p$, but it can be strengthened further rather than just $\text{rad}(m) \mid a_m$, and therefore the $\nu_p$ idea was raised. I quickly get the lowerbound of $\nu_p(a_n)$. However, since we can do this to the first equation. It is questionable whether we could do this to the second equation and get a similar result - and yes, we have found a lower bound and upper bound for $\nu_p(a_n)$. The proof for odd prime $p$ would be less involved, but I got stuck for $\nu_2$ bound proof for a while - wondering whether the bound is even correct for prime $p = 2$. Now, after we are done with Claim 02, we looked at the problem statement again. We are asked the number of $k$-good numbers. To determine, we have to determine the sufficient condition for a good sequence, given the necessary condition that we have proved in Claim 02. However, apparently the sufficient condition is exactly the same as necessary condition, finishing the problem immediately just by noticing that $2019$ is a multiple of $3$. Last but not least, throughout this solution, there was a lot of $p$-adic properties usage: \[ \nu_p(a + b) \ge \min \{ \nu_p(a), \nu_p(b) \} \ \text{or even} \nu_p(a^b) = b \nu_p(a) \]

Oranges are yummy The answer is no. I claim for each $a_{n}$, we have $n | a_{n}^{2}, a_{n} | n^{2}$. Observe that for each $a_{n}$ that satisfies that property, there exists a sequence with it. This is because we can take the sequence $a_{n} = a_{n}, a_{i} = i$ for $i\neq n$. Now, we will show that these are the only possible values. First, I claim that for a prime $p$, $p | m \Longleftrightarrow p | a_{m}$. This is because \[p | \gcd(m, 2m) | a_{m}^{2} + a_{2m}^{2}, p | \gcd(m, 3m) | a_{m}^{2} + a_{3m}^{2}, p | \gcd(2m, 3m) | a_{2m}^{2} + a_{3m}^{2}\]\[\Rightarrow p | 2(a_{m}^{2} + a_{2m}^{2} + a_{3m}^{2}), a_{2m}^{2} + a_{3m}^{2}\]If $p\neq 2$, then this implies $p | a_{m}^{2}, a_{m}$. For $p = 2$, it is obvious that if $2 | m, n$, then $a_{m}\equiv a_{n}\mod 2$. Furthermore, since $4 | \gcd(4,8) | a_{4}^{2} + a_{8}^{2}$, if $a_{4}, a_{8}$ were both odd, by $\mod 4$ this would be a contradiction. Thus, $a_{4}$ is even, so for all $2 | m$ we have $a_{m}$ even. To show the converse of this, if $p\not | m$, but $p | a_{m}$, then \[p | \gcd(a_{m}, a_{p}) | p^{2} + m^{2}\Rightarrow p | m^{2}\]Contradiction. The converse is proven. Now, I claim that for any prime $p^{i}$, we have $\frac{i}{2}\leq v_{p}(a_{p^{i}}) \leq 2i$. We will prove this by induction on $i$. For our base case, if $i = 1$, then let $k = v_{p}(a_{p})$. Clearly $k\geq \frac{i}{2}$ (since $p | a_{p}$ by our above claim), so we prove $k\leq 2$. If $k > 2$, then $v_{p}(a_{p^{i}})\leq 2$, or else \[p^{3} | \gcd(a_{p}, a_{p^{i}}) | p^{2} + p^{2i}\]a contradiction. However, if $v_{p}(a_{p^{i}})\leq 2$, then this means for all $i$, we have $a_{p^{i}} = p, p^{2}$. Thus for $4 < m < n$, \[p^{m} = \gcd(p^{m}, p^{n}) | a_{p^{m}}^{2} + a_{p^{n}}^{2}\leq p^{4}\]Contradiction. We conclude that $k\leq 2$, which proves our base case. Next, for our inductive step, assume that for all $j < i$, we have $\frac{j}{2} \leq v_{p}(a_{p^{j}}) \leq 2j$. Then, again let $v_{p}(a_{p^{i}}) = k$. If $k < \frac{i}{2}$, then for any $m > i$, we have $v_{p}(a_{p^{m}}) \leq k$, or else if $a_{p^{m}} = l > k$ \[p^{i} | \gcd(p^{i}, p^{m}) | p^{2k} + p^{2l}, v_{p}(p^{2k} + p^{2l}) = 2k\]But this is a contradiction since $2k < i$. Therefore, for all $m$, we must have $a_{p^{m}} \leq k$, but this also means for $4k < m < n$, we get \[p^{m} | \gcd(p^{m}, p^{n}) | a_{p^{m}}^{2} + a_{p_{n}}^{2} \leq 2p^{2k}\]which is again a contradiction. We conclude that $k \geq \frac{i}{2}$. Now, to prove that $k\leq 2i$, assume $k > 2i$. For any $m > i$, we must have $v_{p}(a_{p^{m}}) \leq k$, or else if $a_{p^{m}} = p^{l} > p^{k}$, this means \[p^{k} |\gcd(p^{l}, p^{k}) | p^{2i} + p^{2m}, v_{p}(p^{2i} + p^{2m}) = 2i\]This is a contradiction, so all $m > i$ must have $a_{p^{m}} \leq p^{k}$. But then for $4k < m < n$, we get \[p^{m} | \gcd(p^{m}, p^{n}) | a_{p^{m}}^{2} + a_{p^{n}}^{2} \leq 2p^{2k}\]Contradiction. We conclude that $k\leq 2i$, which proves our induction. Now, we prove that if $v_{p}(m) = i$, then $\frac{i}{2}\leq v_{p}(a_{m}) \leq 2i$. Let $k = v_{p}(a_{m})$. If $k < \frac{i}{2}$, then \[p^{i} | \gcd(m, p^{i}) | a_{m}^{2} + a_{p^{i}}^{2}\]But $v_{p}(a_{p_{i}}^{2})\geq i$, and $v_{p}(a_{m}^{2}) < i$, so $v_{p}$ of the RHS is less than $i$, a contradiction. This means $k \geq \frac{i}{2}$. Now, if $k > 2i$, then \[p^{k} | \gcd(p^{k}, p^{k}) | \gcd(a_{m}, a_{p^{2k}}) | m^{2} + p^{4k} \]But $v_{p}(m^{2}) = 2i < k$, so $v_{p}$ of the RHS is less than $k$, a contradiction, so $k \leq 2i$. Doing this for all primes results in $n | a_{n}^{2}, a_{n}|n^{2}$, and there's always a sequence for each value of $a_{n}$. Finally, for each $p^{e} | n$, if $e = 2k$, then there are $4k - k + 1 = 3k + 1$ ways to choose the power for $p$ in $a_{n}$. Otherwise, if $e = 2k + 1$, then there are $4k + 2 - (k+1) + 1 = 3k + 2$ ways to choose the power of $p$. Multiplying over all primes $p$, since there is never a multiple of $3$, the number of ways to choose $a_{n}$ can not be a multiple of $3$, so there is no $n$ such that there are $2019$ choices of $a_{n}$.

fattypiggy123 wrote: Call a sequence of positive integers $\{a_n\}$ good if for any distinct positive integers $m,n$, one has $$\gcd(m,n) \mid a_m^2 + a_n^2 \text{ and } \gcd(a_m,a_n) \mid m^2 + n^2.$$Call a positive integer $a$ to be $k$-good if there exists a good sequence such that $a_k = a$. Does there exists a $k$ such that there are exactly $2019$ $k$-good positive integers? Claim: Any good sequence must have $n|a_n$ and $a_n|n^2$ Proof: Take $(n,2n)$, $(2n,3n)$ and $(n,3n)$ in the given statement to get $n$ divides $a_n^2 + a_{2n}^2$, $a_{2n}^2 + a_{3n}^2$ and $a_n^2 + a_{3n^2}$. This implies\[ n \mid 2a_n^2. \]so for odd prime $p $ we have $\nu_p (n)\le 2\cdot \nu_p (a_n) $ and for $p=2$ choose $m $ such that $\nu_2 (m) $ is sufficiently large then $\nu_2 (a_m) $ is sufficiently large which means $\nu_2 (n)\leq 2\cdot \nu_2 (a_n) $ then $n\mid a_n^2$ To show $a_n\mid n^2$,choose $\nu_p(a_m)$ to be sufficiently large and by the previous argument,$\nu_p(a_n) \le 2 \nu_p(n).$ Thus we must have \[ \frac{\nu_p(n)}{2} \le \nu_p(a_n) \le 2\nu_p(n). \]Thus if $k=\prod\limits_{i=1}^r p_i^{e_i}$ where $p_1,p_2,...,p_r$ are primes and $e_1,e_2,...,e_r\in\mathbb{Z}+$. Then the total number of $k$-good number is $$\prod_{i=1}^r\left(2e_i - \left\lceil\frac{e_i}{2}\right\rceil + 1\right).$$Each factor is $3x+1$ if $e_i=2x$ and $3x+2$ if $e_i=2x+1$. This means the number of all $k$-good number is never divisible by $3$, contradiction hence the answer is $\boxed{\text{No.}}$

The answer is no. Let $P(m,n)$ denote the given assertion. Claim: For each positive integer $m$, we have $m\mid 2a_m^2$. Proof: $P(m,2m)$, $P(2m,3m)$, and $P(m,3m)$ give that $m$ divides all of $a_m^2 + a_{2m}^2$, $a_{2m}^2 + a_{3m}^2$, and $a_m^2 + a_{3m}^2$. Therefore \[ m\mid (a_m^2 + a_{2m}^2) + (a_m^2 + a_{3m}^2) - (a_{2m}^2 + a_{3m}^2) = 2a_m^2,\]as desired. $\square$ Claim: $a_m \mid m^2$ for any positive integer $m$ Proof: We show that for any prime $p$, $\nu_p(a_m) \le 2\nu_p(m)$. Suppose there existed a prime $p$ with $\nu_p(a_m) > 2\nu_p(m)$. Then set $n = p^N$ for some sufficiently large $N$ (as in $N > 1434m^{69} + 420$). It is clear that $p^N \mid 2 a_n ^2$, so $\nu_p(a_n) \ge \frac{N-1}{2} $. Now, note that $\nu_p(\gcd(a_m,a_n) ) = \nu_p(a_m) > 2\nu_p(m)$, but $\nu_p(m^2 + n^2) = \nu_p(m^2) = 2\nu_p(m)$, so $\gcd(a_m,a_n)> m^2 + n^2$, contradiction. $\square$ Thus, for any prime $p > 2$, we have \[\frac{\nu_p(m)}{2} \le \nu_p(a_m) \le 2\nu_p(m) \ \ \ \ \ \ \ \ \ \ \ \ (1)\] Claim: $\frac{\nu_2(m)}{2} \le \nu_2(a_m) $ for any positive integer $m$. Proof: Set $n = 2^N$ for some sufficiently large positive integer $N$. Clearly, $\nu_2(a_n) \ge \frac{ N - 1}{2}$. We have $\gcd(m,n) = \nu_2(m)$ and $\nu_2(a_m^2 + a_n^2) = \nu_2(a_m^2) = 2\nu_2(a_m)$. This implies $\nu_2(m) \le 2\nu_2(a_m)$, so $\frac{ \nu_2(m)}{2} \le \nu_2(a_m)$. $\square$ Hence $(1) $ holds for all primes $p$. This implies that for any positive integer $m$, we have $m\mid a_m^2$ and $a_m\mid m^2$. All such sequences $(a_i)$ work, so these are the only solutions. It suffices to find the number of $k$-good positive integers for each $k$. Notice that if $(1)$ is satisfied for some $a_k$, $m = k$, and all primes $p$, then $a_k$ is $k$-good. The number of ways to select $\nu_p(a_k)$ for each prime $p$ is equal to \[ 2 \nu_p(k) - \left \lceil \frac{\nu_p(k)}{2} \right \rceil + 1 = f(k_p)\]So essentially the number of $k$-good positive integers is equal to the product of $f(k_p)$ over all primes $p$. We can rewrite $(2)$ as $f(k_p) = \frac{ 3\nu_p(k)}{2} + 1 $ if $\nu_p(k) $ is even, and $f(k_p) = \frac{ 3\nu_p(k) + 1}{2}$ if $\nu_p(k)$ is odd. If there existed $k$ with $2019$ numbers that are $k$-good, we must have $\prod_{p \text{ prime} } f(k_p) = 2019$. However, we see that if $\nu_p(k)$ is even, then $f(k_p) \equiv 1\pmod 3$ and if $\nu_p(k)$ is odd, then $f(k_p) \equiv \frac{1}{2} \equiv 2\pmod 3$. This means that $f(k_p)$ is never a multiple of $3$, so the product of all $f(k_p)$ can never equal $3\cdot 673 = 2019$.

We'll prove that for all positive integer $n$, $n \mid a_n^2$ and $a_n \mid n^2$, which is enough to conclude the problem. Consider the following claim: Claim: For all prime $p$ and all positive integer $n$, $p \mid n \iff p \mid a_n$. Proof. Firstly, we'll prove that for all $n$, if $p \mid n$, so $p \mid a_n$. Assume for some $m$, $p \mid m$ and $p \nmid a_m$. Then for all $p \mid n$, we have $p \mid \gcd(m, n) \mid a_m^2 + a_n^2$, so $p \nmid a_n$. If $p = 2$, then $4 \mid (4, 8) \mid a_4^2 + a_8^2$ and since $a_4, a_8$ are odd, so $a_4^2 + a_8^2 \equiv 2 (4)$, a contradiction. Therefore, we can assume $p$ is odd. If $p \equiv 3 (4)$, so for all $p \mid n$, we have $p \mid \gcd(m, n) \mid a_m^2 + a_n^2$, so we get $p \mid a_m$. Thus we can assume $p \equiv 1 (4)$. Now since for all $p \mid n$, we have $p \mid \gcd(m, n) \mid a_m^2 + a_n^2$, so $a_n^2 \equiv -a_m^2 (p)$ for all $n \equiv 0 (p)$, other than $m$. Take positive integers $n, k$ such a way $p \mid \gcd(n, k)$. Then $p \mid a_n^2 + a_k^2$, so $0 \equiv a_n^2 + a_k^2 \equiv -2a_m^2 (p)$, so $p \mid a_m^2$. Now we'll prove the other direction. Assume for some $m$, we have $p \mid a_m$ and $p \nmid m$. Then since $p \mid a_p$, so $p \mid \gcd(a_m, a_p) \mid m^2 + p^2$, which forces $p \mid m$. Hence the claim is proved. $\blacksquare$ Now we'll prove that $n \mid a_m^2$ and $a_m \mid m^2$ for all $m$, which suffices to consider the following claim: Claim: For all prime $p$ and all positive integer $n$, $\nu_p(n) \le 2\nu_p(a_n)$ and $\nu_p(a_n) \le 2\nu_p(n)$. Proof. Firstly, we'll prove that $\nu_p(n) \le 2\nu_p(a_n)$ for all positive integer $n$ and all primes $p$. Assume $p = 2$. FTSOC, assume there exists $m$ such that $\nu_2(m) > 2\nu_2(a_m)$. Then for all $n$ such that $\nu_2(n) \ge \nu_2(m)$, we have $2^\nu_2(m) \mid \gcd(m, n) \mid a_n^2 + a_m^2$, so $\nu_2(a_m) = \nu_2(a_n)$. Take $n, k$ such that $\nu_2(n), \nu_2(k)$ are large enough. Then $2^{\nu_2(m) + 1} \mid \gcd(n, k) \mid a_n^2 + a_k^2$, but $\nu_2(a_n^2 + a_k^2) \le 2\nu_2(a_n) + 1 = 2\nu_2(a_m) + 1$, a contradiction. Hence we can assume $p$ is odd. Assume $p \equiv 3 (4)$. Take $n$ such that $\nu_p(n) \ge \nu_p(m)$. Then $\nu_p(m) = \nu_p(\gcd(m, n)) \le \nu_p(a_m^2 + a_n^2) = \min(2\nu_p(a_m), 2\nu_p(a_n)) \le 2\nu_p(a_m)$. Now assume $p \equiv 1 (4)$. FTSOC, assume there exists $m$ such that $\nu_p(m) > 2\nu_p(a_m)$. Then take a positive integer $n$ such that $\nu_p(n) \ge \nu_p(m)$. Then $\nu_p(m) = \nu_p(\gcd(m, n)) \le \nu_p(a_m^2 + a_n^2)$, hence $\nu_p(a_m) = \nu_p(a_n)$ for all positive integer $n$ satisfying $\nu_p(n) \ge \nu_p(m)$. Take positive integers $n, k$ such that $\nu_p(n), \nu_p(k) \ge \nu_p(m)$. Then $\nu_p(m) \le \nu_p(\gcd(n, k)) \le \nu_p(a_n^2 + a_k^2) = 2\nu_p(a_m)$, which is an evident contradiction. Now we'll prove that $\nu_p(a_m) \le 2\nu_p(m)$ for all positive integer $m$. Take positive integer such that $\nu_p(n)$ is large enough. Then $\nu_p(a_n)$ is large enough too, since $2\nu_p(a_n) \ge \nu_p(n)$. Then we have $\nu_p(a_m) = \nu_p(\gcd(a_m, a_n)) \le \nu_p(m^2 + n^2) = 2\nu_p(m)$. Thus the claim is proved. $\blacksquare$ By above claim, it is clear that there is no such $m$ that $a_m$ can take exactly $2019$ values. Hence we're done. $\blacksquare$ Remark: It's very natural to consider the above claims. I misread the problem, allowing the condition $m = n$, then problem becomes way too easy, so I read it again and realised the claim. Once you realised the claim, it's just repeating the same idea over and over (in $p = 4k+1$ and $p = 2$).

can we do the same by p adic numbers?

Answer: No. In fact, I claim that all good sequences are described as the following: \[n \mid a_n^2 \textrm{ and } a_n \mid n^2 \textrm{ for all positive integers } n\]1. Any sequence satisfying the condition above is clearly a good sequence. 2. Observe that \begin{align*} &n \mid a_{n}^2+a_{in}^2 \\ &n \mid a_{n}^2+a_{jn}^2 \\ &n \mid a_{in}^2+a_{jn}^2 \end{align*}is true for all positive integers $i$ and $j$. This implies $n \mid 2a_n^2$. 3. Let $m=2n^2$. We have $2n^2 \mid 2a_m^2 \implies n \mid a_m$. Hence, $n \mid \gcd(m, n) \mid a_m^2+a_n^2$ which implies $n \mid a_n^2$. 4. Let $i=2a_n^2$ and $j=4a_n^2$. Note that $2a_n^2 \mid 2a_i^2 \implies a_n \mid a_i$ and likewise $a_n \mid a_j$. Therefore, we have \begin{align*} a_n \mid \gcd(a_n, a_i) &\mid n^2 + i^2 \\ a_n \mid \gcd(a_n, a_j) &\mid n^2+j^2 \\ a_n \mid \gcd(a_i, a_j) &\mid i^2+j^2\end{align*}which implies $a_n \mid 2n^2$. 5. Let $m=2a_n^2$. Notice that $2a_n^2 \mid 2a_m^2 \implies a_n \mid a_m$. Hence, $a_n \mid \gcd(a_n, a_m) \mid m^2+n^2$ which implies $a_n \mid n^2$. $\square$ Define by $f(n)$ the number of $n$ good positive integers. We prove that $f$ is multiplicative. Let $n$ be a positive integer and let $p$ be a prime number that doesn't divide $n$. Consider an arbitrary $np^\alpha$ good positive integer $a_n$. Let $a_n=p^\beta k$ where $p \nmid k$. Obviously, $a_n = p^\beta k \mid (np^\alpha)^2$ and $np^\alpha \mid a_n^2 = (p^\beta k)^2$ implies $k$ being $n$ good and likewise $p^{\beta}$ being $p^{\alpha}$ good and vice-versa. Since there are $f(p^\alpha)$ ways to choose $p^\beta$ and there are $f(n)$ ways to choose $k$, we ultimately get $f(np^\alpha)=f(n)f(p^\alpha)$. $\square$ Finally, we will prove that $3 \nmid f(n)$ for all positive integers $n$. It suffices to show that $3 \nmid f(p^\alpha)$ for all primes $p$. Let $p^{\beta}$ be a $p^\alpha$ good number. (It is clear that any such number must be a power of $p$.) Obviously $p^\beta \mid p^{2\alpha}$ and $p^\beta \mid p^{2\alpha}$ is equivelant to $\frac{\alpha}{2} \leq \beta \leq 2\alpha$. If $\alpha$ is even choosing $\alpha=2k$, there are $3k+1$ ways to choose $\beta$. If $\alpha$ is odd choosing $\alpha=2k+1$ there are $3k+2$ ways to choose $\beta$, and we are done since $3 \mid 2019$. $\blacksquare$

Let's mess around with the propeties of this sequence, as one should. $n \mid a_n^2+a_{2n}^2, a_n^2+a_{3n}^2, a_{2n}^2+a_{3n}^2$ so we get that $n \mid 2a_{kn}^2$ for any positive integer $k$, now if $v_2(n)=v_2(2a_n^2)$ then we must have that $v_2(a_n^2)=v_2(a_{kn}^2)$ for any positive integer $k$ (otherwise the divisibility cannot be true in powers of $2$), but we have that $2n \mid 2a_{2n}^2$ so $v_2(2a_{2n}^2) \ge v_2(2n)=v_2(n)+1=v_2(2a_n^2)+1=v_2(2a_{2n}^2)+1$, contradiction!. Therefore $n \mid a_n^2$ for all positive integers $n$. Now consider $m=a_n^2$ and note that $a_n^2 \mid a_m^2$ so $a_n \mid a_m$ and therefore we have $a_n \mid m^2+n^2$ so $a_n \mid n^2$ for all positive integers $n$. Now if a sequence were to satisfy $a_n \mid n^2$ and $n \mid a_n^2$ for all positive integers $n$, notice that we have $n \mid a_n^2+a_{mn}^2$ and $m \mid a_m^2-a_{mn}^2$ so by adding we get $\gcd(m,n) \mid a_m^2+a_n^2$ for all positive integers $m,n$, now $a_n \mid n^2-(mn)^2$ and $a_m \mid m^2+(mn)^2$ so by adding we must have $\gcd(a_m,a_n) \mid m^2+n^2$ for all positive integers $m,n$. Therefore those conditions are equivalent (i.e. one holds if and only if the other does) in any good sequence. To Finish note that this means that the number of $k$-good numbers where $k=\prod_{i=1}^{\ell} p_i^{\alpha_i}$ is $\prod_{i=1}^{\ell} \left(2\alpha_i-\left\lceil \frac{\alpha_i}{2} \right\rceil+1 \right)$, and whether $\alpha_i$ is odd of even none of the terms ends up being a multiple of $3$ therefore there is no such $k$, thus we are done .