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"

(Created page with "== Problem == Let <math>d</math> be any positive integer not equal to <math>2, 5</math> or <math>13</math>. Show that one can find distinct <math>a,b</math> in the set <math>...")
 
(→‎Solution 1)
 
(12 intermediate revisions by 7 users not shown)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
We do casework with mods.
+
===Solution 1===
 +
We do casework with modular arithmetic.
  
−
<math>d\equiv 0 \pmod{4}: 13d-1</math> is not a perfect square.
+
<math>d\equiv 0,3 \pmod{4}: 13d-1</math> is not a perfect square.
  
 
<math>d\equiv 2\pmod{4}: 2d-1</math> is not a perfect square.
 
<math>d\equiv 2\pmod{4}: 2d-1</math> is not a perfect square.
  
−
<math>d\equiv 3 \pmod{4}: 13d-1</math> is not a perfect square.
+
Therefore, <math>d\equiv 1, \pmod{4}.</math> Now consider <math>d\pmod{16}.</math>  
−
 
 
−
Therefore, <math>d\equiv 1 \pmod{4}.</math> Now consider <math>d\pmod{16}.</math>  
 
  
 
<math>d\equiv 1,13 \pmod{16}: 13d-1</math> is not a perfect square.
 
<math>d\equiv 1,13 \pmod{16}: 13d-1</math> is not a perfect square.
Line 20: Line 19:
  
 
As we have covered all possible cases, we are done.
 
As we have covered all possible cases, we are done.
 +
~Shen kislay kai
 +
 +
===Solution 2===
 +
Proof by contradiction:
 +
 +
Suppose <math>p^2=2d-1</math>, <math>q^2=5d-1</math> and <math>r^2=13d-1</math>. From the first equation, <math>p</math> is an odd integer. Let <math>p=2k-1</math>. We have <math>d=2k^2-2k+1</math>, which is an odd integer. Then <math>q^2</math> and <math>r^2</math> must be even integers, denoted by <math>4n^2</math> and <math>4m^2</math> respectively, and thus <math>r^2-q^2=4m^2-4n^2=8d</math>, from which
 +
<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.
 +
 +
 +
{{alternate solutions}}
  
 
{{IMO box|year=1986|before=First Problem|num-a=2}}
 
{{IMO box|year=1986|before=First Problem|num-a=2}}

Latest revision as of 12:10, 3 September 2024

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.


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=226302"