Revision as of 23:30, 20 January 2020

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 mods.

$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.

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

Suppose one can't find distinct a,b from the set $A=\{2,5,13,d\}$ such that $ab-1$ is a perfect square.

Let, $2d-1=x^2\cdots (1)$

$13d-1 =z^2 \cdots (3)$ .b

Clearly $Z^2+1 = 13d = 3(5d)-2d= 3y^2-x^2+2$ .

$\implies x^2 +z^2=3y^2+1$ .

Clearly ,if $x^2,z^2$ is 1 or 0 modulo 3 then it has no solution .

Suppose, $Z=3r$ and $x=3$ ± $1$ , $\implies 3|z$ ,

$\implies 9|z^2$ .

So, $5d-1 \equiv 0 \pmod{9}$ and $13d-1 \equiv 0 \pmod{9}$ .

$\implies d \equiv 0 \pmod{d}$ .

It is contradiction ! Since $9|5d-1$ .

@ftheftics

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

@@ Line 26: / Line 26: @@
 <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=
+Suppose one can't find distinct a,b from the set <math>A=\{2,5,13,d\}</math> such that <math>ab-1</math> is a perfect square.
+Let,<math>2d-1=x^2\cdots (1)</math>
+  <math>5d-1=y^2\cdots (2)</math>
+<math>13d-1 =z^2 \cdots (3)</math>.b
+Clearly <math>Z^2+1 = 13d = 3(5d)-2d= 3y^2-x^2+2</math>.
+<math>\implies x^2 +z^2=3y^2+1</math>.
+Clearly ,if <math>x^2,z^2</math> is 1 or 0 modulo 3 then it has no solution .
+Suppose,<math>Z=3r</math> and <math>x=3</math>±<math>1</math>,
+<math>\implies 3|z </math>,
+<math>\implies 9|z^2</math>.
+So,<math> 5d-1 \equiv 0 \pmod{9}</math> and <math>13d-1 \equiv 0 \pmod{9}</math>.
+<math>\implies d \equiv 0 \pmod{d}</math>.
+It is contradiction ! Since <math>9|5d-1</math>.
+ @ftheftics
 {{alternate solutions}}
 {{IMO box|year=1986|before=First Problem|num-a=2}}

Page

Toolbox

Search

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