An Easy IMO Problem!

d d is a positive integer not equal to 2 , 5 2, 5 or 13 13 . How many values of d d are there such that for any pair ( a , b ) (a, b) from the set { 2 , 5 , 13 , d } \{2, 5, 13, d\} , a b 1 ab-1 is a perfect square?

This is IMO 1986 -1.
This problem is a part of the set "Olympiads and Contests Around the World - 2". You can see rest of the problems here .


The answer is 0.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Discussions for this problem are now closed

Sean Ty
Jul 13, 2014

We consider the combinations 2 d 2d , 5 d 5d , and 13 d 13d for a a and b b .

Now 2 d 1 2d-1 , 5 d 1 5d-1 , and 13 d 1 13d-1 should be perfect squares.

All perfect squares are 0 , 1 , 4 , 9 ( m o d 16 ) \equiv 0,1,4,9 \pmod{16} .

So d 1 , 5 , 9 , 13 ( m o d 16 ) d \equiv 1, 5, 9, 13\pmod{16}

Case 1: d 1 ( m o d 16 ) d \equiv 1 \pmod{16}

2 d 1 1 ( m o d 16 ) 2d-1 \equiv 1 \pmod{16}

2 d 1 2d-1 is a perfect square.

5 d 1 4 ( m o d 16 ) 5d-1 \equiv 4 \pmod{16}

5 d 1 5d-1 is a perfect square.

13 d 1 12 ( m o d 16 ) 13d-1 \equiv 12 \pmod {16}

13 d 1 13d-1 is not a perfect square.

Case 2: d 5 ( m o d 16 ) d \equiv 5 \pmod{16}

2 d 1 9 ( m o d 16 ) 2d-1 \equiv 9 \pmod{16}

2 d 1 2d-1 is a perfect square.

5 d 1 8 ( m o d 16 ) 5d-1 \equiv 8 \pmod{16}

5 d 1 5d-1 is not a perfect square.

Case 3: d 9 ( m o d 16 ) d \equiv 9 \pmod{16}

2 d 1 1 ( m o d 16 ) 2d-1 \equiv 1 \pmod{16}

2 d 1 2d-1 is a perfect square.

5 d 1 12 ( m o d 16 ) 5d-1 \equiv 12 \pmod{16}

5 d 1 5d-1 is not a perfect square.

Case 4: d 13 ( m o d 16 ) d \equiv 13 \pmod{16}

2 d 1 9 ( m o d 16 ) 2d-1 \equiv 9 \pmod{16}

2 d 1 2d-1 is a perfect square.

5 d 1 0 ( m o d 16 ) 5d-1 \equiv 0 \pmod{16}

5 d 1 5d-1 is a perfect square.

13 d 1 8 ( m o d 16 ) 13d-1 \equiv 8 \pmod{16}

13 d 1 13d-1 is not a perfect square.

Therefore, there are 0 \boxed{0} possible values for d d .

Edit: In some parts I may have said "Is a perfect square." Not necessarily true but what this means is "Every perfect square can be either 0 , 1 , 4 , 9 ( m o d 16 ) 0, 1, 4, 9 \pmod{16} . But its converse is not necessarily true."

for d=61.......ab-1 is perfect square...............for d=181.....ab-1 is a perfect square......................can you explain me why.......

Yash Sharma - 6 years, 9 months ago

The mistake you made was fixing one of the pair elements as 2 2 . Note that the question says "for any pair ( a , b ) , . . . (a,b),... " This suggests that you have to find for such values of d d for which all of the numbers ( 2 d 1 ) , ( 5 d 1 ) (2d-1),(5d-1) and ( 13 d 1 ) (13d-1) are perfect squares. When d = 61 d=61 or d = 181 d=181 , ( 5 d 1 ) (5d-1) isn't a perfect square, so they aren't solutions to the problem. In fact, if you do casework by calculating the possible combinations mod 4 or mod 16, no case will give any solution since the case elements will contradict each other and thus, we conclude that there aren't any possible solutions.

Prasun Biswas - 6 years, 5 months ago
Rohan Jain
Jul 15, 2014

let 2d - 1 = a, 5d - 1 = b, 13d - 1 = c where a,b,c are perfect squares solve for d and we'll get the following equations,

5a -2b = -3

13b-5c=-8

13a - 2c = -11

three simultaneous linear equations, convert the matrix in row-echelon form and it becomes quite clear that there are no solutions..

I would recommend using variables besides a,b, and c since a and b are already used in the problem. x,y,z would work better (less confusion among variables).

Alex Wang - 6 years, 10 months ago

see (mod.16) the numbers. the quadratic residues (mod.16) are 0,1,4,9. suppose that 2 d 1 , 5 d 1 , 13 d 1 2d-1,5d-1,13d-1 are perfect squares. for 2 d 1 0 , 1 , 4 , 9 ( m o d . 16 ) 2d-1\equiv 0,1,4,9 (mod.16) , we have d 1 , 5 , 8 o r 13 ( m o d . 16 ) d \equiv 1,5,8 or 13 (mod.16) . if d is 1 or 13, then 13d - 1 is not one of these values. If d is 5 or 9, then 5d - 1 is not one of these values.

(I may sound dumb asking this question) How did you choose what number to use for the mod? (why 16, not some other number)

A Former Brilliant Member - 6 years, 11 months ago

Why 16 16 ?

Because nothing smaller works.

How do you know that?

There is no single specific rule that works for all problems. Sometimes you just have to do trial and error. Reducing things modulo prime powers is helpful in a lot of instances.

Mursalin Habib - 6 years, 11 months ago

Thanks for the advice

A Former Brilliant Member - 6 years, 11 months ago

mod 4 works since integers can be split into odd and even and squaring it gives the two cases for mod 4.

Alex Wang - 6 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...