# Math Olympiad Perfect Square Question

Let $N$ = $(\overline{abcd})$ be a 4-digit perfect square that satisfies $(\overline{ab}) =3× (\overline{cd}) +1$ Find the sum of all possible values of $N$.

(The notation $n= (\overline{ab})$ means that $n$ is a 2-digit number and its value is given by $n= 10a + b$)

I came across this question in a Math Olympiad Competition and did not have the slightest clue on how to solve it. Can anyone help? Thanks.

• you say N has four digits, but the notation implies only two digits. did you mean $N=(abcd^-)$ – cirpis Jun 5 '14 at 9:21
• I mean it can stand for any number of digits so for example, (abcd) with the notation means 1000a + 100b + 10c + d. – snivysteel Jun 5 '14 at 9:23
• This is the original sign: prntscr.com/3pu87o but i do not know how to type it on Stack Exchange – snivysteel Jun 5 '14 at 9:25
• "Let $N = (ab)̅$ be a 4digit n" "$n= (ab)̅$ means that n is a 2digit number and its value is given by $n=10a+b$" – cirpis Jun 5 '14 at 9:26
• There are $99-32+1=68$ possible numbers, so multiplying them by hand (let's assume 30 seconds) would take only about 35 minutes (and could be done faster just by adding odd numbers) $\ddot\frown$ – dtldarek Jun 5 '14 at 9:41

Write $N=x^2$. Then $x^2=N=\overline{abcd}=100\overline{ab}+\overline{cd}=301\overline{cd}+100 \equiv 10^2 \pmod{7*43}$

Thus $x \equiv \pm 10 \pmod{7}$ and $x \equiv \pm 10 \pmod{43}$.

Thus $x \equiv 10, 53, 248, 291 \pmod{301}$. Note $32 \leq x \leq 99$. Thus $x=53$ and $N=2809$.

• Can you elaborate on the last sentence, I do not really understand it. – snivysteel Jun 5 '14 at 10:34
• @snivysteel by $=>$ do you mean $\geq$? – Ivan Loh Jun 5 '14 at 10:35
• Where do you get $100\overline{ab}+\overline{cd}=301\overline{cd}+100\pmod{301}$? – Servaes Jun 5 '14 at 10:35
• no I mean "=". Your answer is correct but I do not understand the last sentence. – snivysteel Jun 5 '14 at 10:36
• @Servaes I interpreted it as an equality. Perhaps that wasn't what was meant. – Ivan Loh Jun 5 '14 at 10:36

EDIT: As the question has been edited to say $(ab)=3\times(cd)+1$ in stead of $(ab)\geq3\times(cd)+1$, this answer no longer answers the question.

The best I have is a very ugly brute force approach, I hope this is not the intended solution:

Let $N=(abcd)$ be a $4$-digit perfect square satisfying $(ab)\geq3\times(cd)+1$. Let $x\in\Bbb{N}$ be such that $x^2=N$, and note that we must have $x<100$.

It is clear that $(cd)$ is a quadratic residue modulo $100$ and it is at most $32$, so $$(cd)\in\{0,1,4,6,16,21,24,25,29\}.$$ There are precisely $10$ solutions to $x^2\equiv0\pmod{100}$ with $0\leq x<100$, and it is obvious that for exactly $9$ of these the number $N=x^2$ satisfies the given inequality; these are $$10,\ 20,\ 30,\ 40,\ 50,\ 60,\ 70,\ 80,\ 90,$$ and their squares sum up to $28500$.

For each quadratic residue $y\neq0$ there are precisely four solutions to $x^2=y$ yielding $32$ candidates for $x$. For each $y$ they are of the form $$x_1=k\qquad x_2=50-k,\qquad x_3=50+k,\qquad x_4=100-k,$$ where $k\in\{1,2,3,4,5,11,18,23\}$. For solutions of the form $x_1$ we have $a=0$ in $x_1^2=N=(abcd)$, from which it easily follows that they cannot satisfy the inequality.

Solutions of the form $x_2$ work up to $k=2$, those of the form $x_3$ work up to $k=3$, and those of the form $x_4$ work up to $k=5$. These correspond to the perfect squares $$2304,\ 2401,\ 2601,\ 2704,\ 2809,\ 9025,\ 9216,\ 9409,\ 9604,\ 9801,$$ which sum up to $59874$. This yields a sum of $28500+59874=88374$.

• Was the => meant to be a $\geq$? Hmm – Ivan Loh Jun 5 '14 at 10:34
• What else could it mean? – Servaes Jun 5 '14 at 10:36
• Ah, I see the edit. That makes the question rather trivial. – Servaes Jun 5 '14 at 10:37
• though this is a nice way to finish your interpretation of the problem. (+1) – Ivan Loh Jun 5 '14 at 10:45

$\text{Given}:$

$N=x^2$

$N=\overline{abcd}$

$\overline{ab}=3\times\overline{cd}+1$

$\overline{ab}\lt100$

$3\times\overline{cd}+1\lt100$

$\overline{cd}\lt33$

$9\lt\overline {ab}$

$3\lt\overline{cd}\lt33$

$N=x^2$

$N\equiv0,1,4,5,6,9\pmod{10}$

$d=0,1,4,5,6,9$

$c=0,1,2,3$

$\overline{cd}=04,05,06,09,10,11,14,15,16,19,20,21,24,25,26,29,30,31$

Now, reducing possibilities.

$\overline{cd}\neq10,20,30\quad[(10x)^2=100x^2]$

$\overline{cd}\neq5,15\;\;\;\;\quad\quad[(5x)^2=25x^2]$

So possible values of $\overline{cd}$ and corresponding values of $\overline{abcd}$:

$04,\quad1304$

$06,\quad1906$

$09,\quad2809$

$11,\quad3411$

$14,\quad4314$

$16,\quad4916$

$19,\quad5819$

$21,\quad6421$

$24,\quad7324$

$25,\quad7625$

$26,\quad7926$

$29,\quad8829$

$31,\quad9431$

Out of these, only $2809=53^2$ is a perfect square.

Therefore, answer is $2809$.

[Extremely Inelegant and Clumsy, but covers all possible solutions]