Let's analyze the problem step by step: --- ## **Given** Find the number of integer solutions \((x, y)\) with \(1 \leq x, y \leq 10^6\) such that \[ x^2 + y^2 \text{ is divisible by } x + y. \] --- ## **Step 1: Express the divisibility condition** Let \(d = x + y\). We want \(d \mid x^2 + y^2\). But, \[ x^2 + y^2 = (x + y)^2 - 2xy = d^2 - 2xy \] So, \[ d \mid d^2 - 2xy \implies d \mid d^2 - 2xy \implies d \mid d^2 - 2xy \] But \(d \mid d^2\), so \(d \mid -2xy\), i.e., \[ d \mid 2xy \] --- ## **Step 2: Rewriting the condition** So, for \(1 \leq x, y \leq 10^6\), we want \(x + y \mid 2xy\). Let \(d = x + y\). Then \(1 < d \leq 2 \times 10^6\) (since both \(x, y \geq 1\)). For each \(d\), \(x\) and \(y\) are positive integers such that \(x + y = d\) and \(x, y \geq 1\). Then, \[ d \mid 2xy \] But \(y = d - x\), so \[ 2xy = 2x(d - x) = 2dx - 2x^2 \] So, \(d \mid 2xy \implies d \mid 2dx - 2x^2\) But \(d \mid 2dx\) is always true, so \(d \mid -2x^2\) i.e., \[ d \mid 2x^2 \] But also \(x\) and \(y = d - x\) are both between \(1\) and \(10^6\). --- ## **Step 3: Re-expressing the solutions** So, for each \(d\) from \(2\) to \(2 \times 10^6\), we want to count the number of \(x\) such that \(1 \leq x \leq d - 1\), \(x \leq 10^6\), \(d - x \leq 10^6\), and \(d \mid 2x^2\). Or, equivalently, for each \(d\), count the number of \(x\) in the range \(\max(1, d - 10^6) \leq x \leq \min(10^6, d - 1)\) such that \(d \mid 2x^2\). --- ## **Step 4: Counting the solutions** For each possible \(d\), \(d \mid 2x^2\) means \(2x^2 = k d\) for some \(k\). So \(x^2 \equiv 0 \pmod{d/\gcd(2, d)}\), but let's keep it as \(d \mid 2x^2\). For each divisor \(d\), \(x\) must be such that \(d \mid 2x^2\). But \(d \mid 2x^2 \iff \frac{2x^2}{d}\) is integer, i.e., \(x^2\) is a multiple of \(d/\gcd(2, d)\). But let's do a simple substitution: Let \(g = \gcd(2, d)\), so \(d = g \cdot m\), where \(m\) is coprime to \(2\). Then \(d \mid 2x^2 \implies m \mid x^2\), since \(g \mid 2\). So for each \(d\), the number of \(x\) in the range such that \(m \mid x^2\). But \(m\) is square-free (since it is coprime to 2). The number of \(x \leq N\) such that \(m \mid x^2\) is equal to the number of \(x\) such that every prime dividing \(m\) divides \(x\). That is, \(x\) must be divisible by all primes dividing \(m\). So, if \(m = p_1 p_2 \cdots p_k\), then \(x\) must be divisible by \(p_1 p_2 \cdots p_k = m\). So \(x = m t\), for integer \(t\). So \(x = m t\), and \(x \leq 10^6\). But also \(x \leq d - 1\), and \(x \geq \max(1, d - 10^6)\). --- ## **Step 5: Final formula** For each \(d\) from \(2\) to \(2 \times 10^6\): - Let \(g = \gcd(2, d)\), \(m = d / g\) - \(x = m t\), for integer \(t\) - \(x\) must be in \(\max(1, d - 10^6) \leq x \leq \min(10^6, d - 1)\) So for each \(d\), the number of \(x\) is equal to the number of integers \(t\) such that \[ \max(1, d - 10^6) \leq m t \leq \min(10^6, d - 1) \] i.e. \[ \left\lceil \frac{\max(1, d - 10^6)}{m} \right\rceil \leq t \leq \left\lfloor \frac{\min(10^6, d - 1)}{m} \right\rfloor \] The total number of solutions is the sum over all \(d\) from \(2\) to \(2 \times 10^6\) of the number of integers \(t\) in this range. --- ## **Summary** **The number of integer solutions \((x, y)\) is:** \[ \boxed{ \sum_{d=2}^{2 \times 10^6} \left( \max\left( 0, \left\lfloor \dfrac{\min(10^6, d-1)}{m} \right\rfloor - \left\lceil \dfrac{\max(1, d-10^6)}{m} \right\rceil + 1 \right) \right) } \] where \(m = \dfrac{d}{\gcd(2, d)}\). --- ### **Key Ideas:** - Reduce the divisibility to \(x + y \mid 2xy\). - Substitute \(d = x + y\), \(y = d - x\). - Reduce to finding \(x\) such that \(d \mid 2x^2\). - \(d = g \cdot m\), \(g = \gcd(2, d)\), \(m\) coprime to 2, \(x = m t\). - Bounds on \(x\) from \(1 \leq x \leq 10^6\), \(1 \leq y \leq 10^6\), \(x + y = d\). - Sum over all \(d\). --- If you want the **exact value**, it's best computed with a program, since the sum runs over \(2 \times 10^6\) values. But the reasoning above gives you the formula!