Find all positive integer solutions $(a, b, c)$ to the function $a^{2} + b^{2} + c^{2} = 2005$, where $a \leq b \leq c$.
Problem
Source: CSEMO 2005-4
Tags: function, modular arithmetic, number theory unsolved, number theory
18.07.2005 02:28
make a bruteforce it takes 40 minutes with calculator... solutions: $(23,24,30)$ $(15,22,36)$ $(9,18,40)$ $(4,15,42)$ $(12,30,31)$ $(9,30,32)$ $(4,30,33)$
23.07.2005 15:52
Out of curiosity, let me ask another related qn. What is the smallest positive integer $k$ such that the eqn ${a_1}^2 + {a_2}^2 + \ldots + {a_k}^2$ = 2005 has infinitely many positive integer solutions in $a_1, a_2, \ldots, a_k$?
23.07.2005 16:07
dblues wrote: Out of curiosity, let me ask another related qn. What is the smallest positive integer $k$ such that the eqn ${a_1}^2 + {a_2}^2 + \ldots + {a_k}^2$ = 2005 has infinitely many positive integer solutions in $a_1, a_2, \ldots, a_k$? I think that $\forall k\in \mathbb {N}$ there exists only finitely many solutions (if they exist at all), because $a_i<[\sqrt{2005}]$ and there are $< ([\sqrt{2005}]+1)^k$ k-tuples $(a_1,a_2,...,a_k)\in {\mathbb {R}}^k$ that has a chance to be a solution and hence the number of solutions is finite.
23.07.2005 16:41
so sorry... tt was a dumb qn... of course there are finitely many solutions $\forall k$. Recently, I was actually working on a problem about the smallest positive integer $k$ such that the eqn ${a_1}^3 + {a_2}^3 + \ldots + {a_k}^3 = n $ has infinitely many positive integer solutions in $a_1, a_2, \ldots , a_k$. Either I cannot remember what the value of $n$ was in that qn, or I generalised some olympiad qn, but I was asking myself what if $n = 2005$ out of curiosity... Perhaps that was why i mixed it up... sorry...
24.07.2005 12:33
What's the solution without brute force?
24.07.2005 12:45
If you want number of solutions, apply Jacobi's formula (in terms of Dirichlet's class-number theirem) and you're done. Bomb
24.07.2005 13:38
bomb wrote: If you want number of solutions, apply Jacobi's formula (in terms of Dirichlet's class-number theirem) and you're done. Bomb But that's not what we want...
08.08.2005 15:17
wait! im so sorry... what is Jacobi's formula?
09.08.2005 15:38
Micchi wrote: wait! im so sorry... what is Jacobi's formula? But we want solutions, not number of solutions. I still don't know how this one is solved.
17.09.2005 23:35
a^2 + b^2 = k is solvable iff, given $k = \prod p_i^{a_i}$, 4 does not divide $p_i^{a_i} + 1$ for all i. http://mathworld.wolfram.com/SquareNumber.html
21.09.2005 22:39
yeah, but that's trivial because of Fermat's 4n + 1 theorem (any prime of the form 4n+1 can be written as a sum of two squares), and the identity (a^2 + b^2)(c^2 + d^2) = (ad + bc)^2 + (ac - bd)^2
18.12.2005 07:03
Can zhaoli or anyone post the official solution?
18.12.2005 10:56
I do not know the official solution, but here's my solution anyway. We consider $\mod 8$. Since all squares are $\equiv 0, 1$ or $4 \pmod{8}$ and $2005 \equiv 5 \pmod{8}$ it follows that $a^2, b^2, c^2$ are $\equiv 0, 1, 4 \pmod{8}$ in some order. WLOG, we ignore the order of $a,b,c$ (we drop the assumption of $a \leq b \leq c$) and assume $a^2 \equiv 0 \pmod{8}, b^2 \equiv 1 \pmod{8}, c^2 \equiv 4 \pmod{8}$. Let $a=4a_1, b=2b_1+1, c=4c_1+2$. We then have $a^2+b^2+c^2=16{a_1}^2+4{b_1}^2+4b_1+16{c_1}^2+16c_1+5 = 2005$ $\Leftrightarrow 4{a_1}^2+{b_1}^2+b_1 + 4{c_1}^2+4c_1 = 500$. Taking $\mod 4$, we have ${b_1}^2 + b_1 \equiv 0 \pmod{4} \Rightarrow b_1 \equiv 0$ or $-1 \pmod{4}$. Case 1: $b_1 \equiv 0 \pmod{4}$. Let $b_1 = 4b_2$ We have $4{a_1}^2+16{b_2}^2+4b_2 + 4{c_1}^2+4c_1 = 500 \Leftrightarrow {a_1}^2+4{b_2}^2+b_2 + {c_1}^2+c_1 = 125$. Since $b_2 \in \mathbb{Z}^+$ and $4{b_2}^2 > 125 \ \forall \ b_2 > 5$, we have $1 \leq b_2 \leq 5$. When $b_2 = 5$, we have ${a_1}^2 +{c_1}^2+c_1=20$. Note that ${c_1}^2+c_1 \equiv 0 \pmod{2}$, thus ${a_1}^2 = 4$ or $16$. We then have ${c_1}^2+c_1 = 16$ or $4$ respectively, which yield no solutions. When $b_2=4$, we have ${a_1}^2 +{c_1}^2+c_1=57$. Note that ${c_1}^2+c_1 \equiv 0 \pmod{2}$, thus ${a_1}^2 = 1, 9, 25$ or $49$. We then have ${c_1}^2+c_1 = 56, 48, 32$ or $8$ respectively, which yield the only possible solution $c_1 = 7 \Rightarrow (a,b,c) = (4,33,30)$. When $b_2=3$, we have ${a_1}^2 +{c_1}^2+c_1=86$. Similarly, ${a_1}^2$ can only be $4, 16, 36$, or $64$, which means ${c_1}^2+c_1 = 82, 70, 50$ or $22$ respectively, which yield no solutions. When $b_2=2$, we have ${a_1}^2 +{c_1}^2+c_1=107$. Similarly, ${a_1}^2$ can only be $1, 9, 25, 49$ or $81$, which means ${c_1}^2+c_1 = 106, 98, 82, 58$ or $26$ respectively, which yield no solutions. When $b_2=1$, we have ${a_1}^2 +{c_1}^2+c_1=120$. Similarly, ${a_1}^2$ can only be $4, 16, 36, 64$ or $100$, which means ${c_1}^2+c_1 = 116, 104, 84, 56$ or $20$ respectively, which yield the possible solutions $c_1 = 7, 4 \Rightarrow (a,b,c) = (32, 9, 30), (40, 9, 18)$. Case 2: $b_1 \equiv -1 \pmod{4}$. Let $b_1 = 4b_2 -1$ We have $4{a_1}^2+16{b_2}^2-4b_2 + 4{c_1}^2+4c_1 = 500 \Leftrightarrow {a_1}^2+4{b_2}^2-b_2 + {c_1}^2+c_1 = 125$. Since $b_2 \in \mathbb{Z}^+$ and $4{b_2}^2 -b_2 > 125 \forall b_2 > 5$, we have $1 \leq b_2 \leq 5$ When $b_2 = 5$, we have ${a_1}^2 +{c_1}^2+c_1=30$. Similarly, by considering parity, we must have ${a_1}^2 = 4$ or $16$, which means ${c_1}^2+c_1 = 26$ or $14$ respectively, which yield no solutions. When $b_2=4$, we have ${a_1}^2 +{c_1}^2+c_1=65$. Similarly, we have ${a_1}^2 = 1, 9, 25$ or $49$, meaning ${c_1}^2+c_1 = 64, 56, 40$ or $16$ respectively, which yield the only possible solution $c_1 = 7 \Rightarrow (a,b,c) = (12, 31, 30)$. When $b_2=3$, we have ${a_1}^2 +{c_1}^2+c_1=92$. Similarly, we have ${a_1}^2 = 4, 16, 36$ or $64$, meaning ${c_1}^2+c_1 = 88, 76, 56$ or $28$ respectively, which yield the only possible solution $c_1 = 7 \Rightarrow (a,b,c) = (24, 23, 30)$. When $b_2=2$, we have ${a_1}^2 +{c_1}^2+c_1=111$. Similarly, we have ${a_1}^2 = 1, 9, 25, 49$ or $81$, meaning ${c_1}^2+c_1 = 110, 102, 86, 62$ or $30$ respectively, which yield the possible solutions $c_1 = 5, 10 \Rightarrow (a,b,c) = (4, 15, 22), (36, 15, 42)$. When $b_2=1$, we have ${a_1}^2 +{c_1}^2+c_1=122$. Similarly, ${a_1}^2$ can only be $1, 9, 25, 49, 81$ or $121$, which means ${c_1}^2+c_1 = 121, 113, 97, 73, 41$ or $1$ respectively, which yield no solutions. Therefore, by considering the above $10$ cases, the only seven possible solutions are $(4,33,30), (32,9,30), (40,9,18), (12,31,30), (24,23,30), (4,15,22), (36,15,42)$. As a side note, we can actually make use of what Singular has mentioned regarding the solvability of $a^2+b^2 =k$ to reduce the number of cases, but this does not necessarily make the solution shorter. Using the "Dirichlet Class-Number Theorem", or rather, finding the appropriate class numbers, to compute $\frac{r_3(2005)}{2^3 \cdot 3!} - \frac{r_2(2005)}{2^2 \cdot 2!} = 7$ is but an unnecessary complication. And besides, I haven't seen any olympiad problems that ask "Find the number of solutions..." instead of the usual "Find all solutions to...", so I doubt this theorem will be used that often.