Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1986 IMO Problems/Problem 1"

(→‎Solution 1)
(Third solution)
Line 27: Line 27:
 
<cmath>2d=m^2-n^2=(m+n)(m-n)</cmath> can be deduced. Since <math>m^2-n^2</math> is even, <math>m</math> and <math>n</math> have the same parity, so <math>(m+n)(m-n)</math> is divisible by <math>4</math>. It follows that the odd integer <math>d</math> must be divisible by <math>2</math>, leading to a contradiction. We are done.
 
<cmath>2d=m^2-n^2=(m+n)(m-n)</cmath> can be deduced. Since <math>m^2-n^2</math> is even, <math>m</math> and <math>n</math> have the same parity, so <math>(m+n)(m-n)</math> is divisible by <math>4</math>. It follows that the odd integer <math>d</math> must be divisible by <math>2</math>, leading to a contradiction. We are done.
  
 +
===Solution 3===
 +
By contradiction suppose
 +
\begin{align}
 +
2d-1 &= a^2 \\
 +
5d-1 &= b^2 \\
 +
13d-1 &= c^2
 +
\end{align}
 +
Note <math>n^2 \equiv 1 \text{ or } 0 \mod 4</math>. By the first equation <math>d = 2d_1 + 1</math> otherwise <math>-1 \equiv a^2 \mod 4</math>. Substituting, the three equations become
 +
\begin{align}
 +
4d_1 + 1 &= a^2 \\
 +
10d_1 + 4 &= b^2 \\
 +
26d_1 + 12 &=c^2
 +
\end{align}
 +
By the second equation <math>2|b</math> hence <math>4|b^2</math> hence <math>2|d_1</math>. Write <math>d_1=2d_2</math>. Substituting, the three equations become
 +
\begin{align}
 +
8d_2 + 1 &= a^2 \\
 +
5d_2+1 &= b_1^2 \\
 +
13d_2 + 3 &= c_1^2
 +
\end{align}
 +
where <math>b = 2b_1, c = 2c_1</math>. Taking mod <math>3</math> of the third equation implies <math>d_2 \equiv c_1^2 \equiv 0 \text{ or } 1 \mod 3</math>. Case <math>d_2 = 3d_3 + 1</math>: substituting, the first equation becomes <math>24d_3 + 9 = a^2</math>. Similar to before this implies <math>3|d_3</math>. The second equation becomes <math>15d_3 + 6 = b_1^2</math>. Since <math>3 | b_1</math> and <math>9|b_1^2</math> we get <math>9|6</math>. A contradiction. Case <math>d_2 = 3d_3</math>: the third equation becomes <math>13d_3+1 = 3c_2^2</math> where <math>c_1 = 3 c_2</math>. Taking mod <math>3</math> yields <math>d_3 +1 \equiv 0 \text{ or } 1 \mod 3</math>. The only way this is possible is if <math>d_3 = 3 d_4</math>. But then <math>13\cdot 3 d_4 + 1 = 3c_2^2</math> which implies <math>3 | 1</math>. So we are done.
 +
 +
~detriti
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
 
{{IMO box|year=1986|before=First Problem|num-a=2}}
 
{{IMO box|year=1986|before=First Problem|num-a=2}}

Revision as of 00:24, 9 July 2025

Problem

Let $d$ be any positive integer not equal to $2, 5$ or $13$. Show that one can find distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.

Solution

Solution 1

We do casework with modular arithmetic.

$d\equiv 0,3 \pmod{4}: 13d-1$ is not a perfect square.

$d\equiv 2\pmod{4}: 2d-1$ is not a perfect square.

Therefore, $d\equiv 1, \pmod{4}.$ Now consider $d\pmod{16}.$

$d\equiv 1,13 \pmod{16}: 13d-1$ is not a perfect square.

$d\equiv 5,9\pmod{16}: 5d-1$ is not a perfect square.

As we have covered all possible cases, we are done. ~Shen kislay kai

Solution 2

Proof by contradiction:

Suppose $p^2=2d-1$, $q^2=5d-1$ and $r^2=13d-1$. From the first equation, $p$ is an odd integer. Let $p=2k-1$. We have $d=2k^2-2k+1$, which is an odd integer. Then $q^2$ and $r^2$ must be even integers, denoted by $4n^2$ and $4m^2$ respectively, and thus $r^2-q^2=4m^2-4n^2=8d$, from which \[2d=m^2-n^2=(m+n)(m-n)\] can be deduced. Since $m^2-n^2$ is even, $m$ and $n$ have the same parity, so $(m+n)(m-n)$ is divisible by $4$. It follows that the odd integer $d$ must be divisible by $2$, leading to a contradiction. We are done.

Solution 3

By contradiction suppose \begin{align} 2d-1 &= a^2 \\ 5d-1 &= b^2 \\ 13d-1 &= c^2 \end{align} Note $n^2 \equiv 1 \text{ or } 0 \mod 4$. By the first equation $d = 2d_1 + 1$ otherwise $-1 \equiv a^2 \mod 4$. Substituting, the three equations become \begin{align} 4d_1 + 1 &= a^2 \\ 10d_1 + 4 &= b^2 \\ 26d_1 + 12 &=c^2 \end{align} By the second equation $2|b$ hence $4|b^2$ hence $2|d_1$. Write $d_1=2d_2$. Substituting, the three equations become \begin{align} 8d_2 + 1 &= a^2 \\ 5d_2+1 &= b_1^2 \\ 13d_2 + 3 &= c_1^2 \end{align} where $b = 2b_1, c = 2c_1$. Taking mod $3$ of the third equation implies $d_2 \equiv c_1^2 \equiv 0 \text{ or } 1 \mod 3$. Case $d_2 = 3d_3 + 1$: substituting, the first equation becomes $24d_3 + 9 = a^2$. Similar to before this implies $3|d_3$. The second equation becomes $15d_3 + 6 = b_1^2$. Since $3 | b_1$ and $9|b_1^2$ we get $9|6$. A contradiction. Case $d_2 = 3d_3$: the third equation becomes $13d_3+1 = 3c_2^2$ where $c_1 = 3 c_2$. Taking mod $3$ yields $d_3 +1 \equiv 0 \text{ or } 1 \mod 3$. The only way this is possible is if $d_3 = 3 d_4$. But then $13\cdot 3 d_4 + 1 = 3c_2^2$ which implies $3 | 1$. So we are done.

~detriti

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1986 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_IMO_Problems/Problem_1&oldid=253745"