Skip to main content
OlympiadHQ

Browse · MathNet

Print

Autumn tournament

Bulgaria number theory

Problem

Let be coprime integers, such that . For which , there exist even integers , such that
Solution
Set , all of them are even. At the first step we get the pairs At each subsequent step we expand the set by adding additional pairs defined as By (2) we obtain So, if is obtained in the process of expanding, we also add defined as in (3). We want to characterize all pairs that can be obtained in this way. Note that if , then from (3) follows . Let us prove that the set of pairs in question is Note that we ruled out because cannot be represented as wanted. The transformation described in (3) shows that we cannot step outside . To prove that all pairs in can be generated, we follow a standard procedure - take and search for that generates via (3), but we want be "less" than . That's how induction works. Solving (3) with respect to yields Clearly, we can choose such that (since ). Indeed, consider the points where runs through all integers. These points are at a distance apart, and none of them hits because . Hence, the point closest to 0 has magnitude less than . So, we started from , and found that generates and moreover, . Apparently is "less" than , that is, . Now, induction does the job. Obviously, can be represented as continued fractions satisfying the statement. Assume that all with can be represented like that. Take . As just shown, there exists such that The induction step is complete and the result follows. Note that it also follows that the representation of numbers in as continued fractions like that is unique. Indeed, take a pair . The pair that satisfies (4) and is determined uniquely. Uniqueness follows easily.
Final answer
Exactly those coprime integers p, q with |p| < |q| and with one of p, q even and the other odd (excluding |p| = |q|, i.e., ±1).

Techniques

OtherIntegers