Maths Olympiad Prep

Library / /495 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Example 18([27.1]) Let dd be a positive integer such that d2,5,13d \neq 2,5,13. Prove: In the set {2,5,13,d}\{2,5,13, d\}, there must exist two distinct elements a,ba, b such that ab1a b-1 is not a perfect square.

Solution

To prove that it is easy to verify, take any two numbers from 2,5,132, 5, 13 as a,ba, b, then ab1ab-1 must be a perfect square. Therefore, the selection of a,ba, b must be one as dd, and the other chosen from 2,5,132, 5, 13. We will use proof by contradiction to show that there must be a selection such that ab1ab-1 is not a perfect square. If ab1ab-1 are all perfect squares, then we have
2d1=x2,5d1=y2,13d1=z22d-1=x^2, \quad 5d-1=y^2, \quad 13d-1=z^2
If equation (1) holds, it indicates that dd has a close relationship with the sequence of perfect squares, thus it has strong restrictions on the remainders of certain moduli. We will point out that these restrictions are contradictory. This is the idea to solve this problem.

From the first equation of (1), we know that xx is an odd number, and x2x^2 is a number of the form 8m+18m+1, so
d=4k+1d=4k+1

From this and the second and third equations of (1), we deduce that y,zy, z are both even, set as
y=2u,z=2v.y=2u, \quad z=2v.

Using the above two equations, by subtracting the second and third equations of (1), we get
v2u2=2d=8k+2v^2-u^2=2d=8k+2

But v2u2v^2-u^2 cannot equal 8k+28k+2, which is a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.