How Do I Pick These Pairs?

Let us generalize it a little.

We have to find all real $(x,y)$ such that both $ax + by$ and $px + qy$ are integers, for $a,b \in \mathbb{Z}$

Let $\displaystyle (ax+by, px+qy)$ be a point on the Argand plane. (You can also assume it on the Cartesian plane if you like as well).

Now $\displaystyle z = (ax+by) + \iota (px + qy)$

$\displaystyle z = (a + p\iota)x + (b + q\iota) y$

We know $0< x,y < 1$ which implies that when we draw a graph of it, by using parallelogram law(till the upper limit), then all values inside the parallelogram will be valid.

Let us say that it has vertices $\displaystyle O(0,0), A(a,p), B(b, q), C(a+b, p+q)$

Now we have our parallelogram i.e. the set of all the possible $z$ and we have to find those with integer real and imaginary parts.

In other words, we have to find out the internal lattice points. And how do we do that? We use Pick's Theorem.

$\displaystyle A = \frac{B}{2} + i -1$

$\displaystyle \text{Area} = A = |aq - bp|$ (can be found easily)

$\displaystyle \text{Boundary lattice points} = B = ?$

On OA, $\displaystyle ay -px = 0, x = \frac{a}{p} y$ and corresponding $y \in (0,p)$ so there is no boundary points except vertices.

On OB, $\displaystyle y = \frac{q}{b} x$ and corresponding $x \in (0,b)$ so there is no boundary points except vertices here too.

On other 2 lines, case is exactly the same because it is a parallelogram.

Therefore, $B = 4$

$\displaystyle i = |aq -bp| - \frac{4}{2} + 1$

$\displaystyle \boxed{i = |aq-bp| - 1}$

I was intrigued by the conversation in the solution discussions and decided to pursue it further. The goal is to overturn the claim "This is just too random" by explaining the theory behind it.

Once again, let's work with the general case, where we want to find all pairs of $0 < x, y < 1$ such that $ax + by$ and $px + qy$ are integers.

Naitik's observation is that $p ( ax+by) - a (px+qy ) = y ( bp - aq)$ must be an integer.

Assumption 1: $bp - aq \neq 0$ .

WLOG, let's assume that $bp-aq > 0$ to keep our math simple.
In this case, it is obvious that $y$ must be of the form $\frac{ k } { bp - aq }$ for some integer $0 \leq k < bp-aq$ .

The question raised by Ivan is "Why must there be an $x$ that makes both of the original terms an integer?"

If we repeat the analysis by swapping the terms, then $x ( bp-aq)$ must be an integer, so we also have $x = \frac{ l } { bp-aq}$ for some integer. If so, we have $\frac { al + bk } { bp-aq }$ is an integer, or that $al \equiv -bk \pmod{ bp-aq }$ .

Assumption 2: $\gcd (a,bp) = 1$ , which is equivalent to $\gcd (a,bp-aq) = 1$ .

Since $a$ is not a divisor of $bp-aq$ , then $a^{-1} \pmod{bp-aq}$ exists and so we have $l \equiv - bk \times ( a ^{-1} ) \pmod{bp-aq}$ . Taking the corresponding residue class, we can define $x = \frac{-bk \times a^{-1} } { bp-aq}$ . Now, it is clear that with this definition, $ax + by$ is an integer.

The question raised by Ivan now becomes "Why is the next one also an integer?"

As it turns out, we are really lucky! (Well, it isn't luck, just math.) For the expression to be an integer, we need to show that $p l + q k \equiv 0 \pmod{ bp-aq}$ , with $l \equiv -bk \times (a^{-1})$ . Since $\gcd(a, bp-aq) = 1$ , the statement is equivalent to multiplying throughout by $a$ to get

$p l + q k \equiv 0 \pmod{ bp-aq} \Leftrightarrow -pbk + aqk \equiv 0 \pmod{pb - aq } ,$

which is obviously true.

---

Now, how do we deal with the assumptions? And how do these assumptions relate to / show up in Kartik's solution?

Assumption 1: If this was not true, what can we say about the 2 expressions?
Assumption 2: What we really needed as that there exists a $l$ such that $al \equiv -bk \pmod{bp-aq }$ . How many solutions are there in general?

We are given two equations that have to be satisfied at once by two unknown real numbers. They aren't real equations per se, but their sums must both equal an integer at once.

43x + 47y = int (integer)

53x + 11y = int

There isn't much we can do in terms of letting the two sides of the equation interact with each other, but we can multiply these equations like we do in regular algebra in order to cancel out certain variables. If we multiply the first equation by 53 and the second by 43 and subtract them from one another, we will get:

2279x + 2491y = int

-2279x - 473y = int

0x + 2018y = int

Here we have our confirmation that y must be a rational fraction whose denominator is 2018 and whose numerator can be any number from 1 to 2017. If you do the same in order to isolate x, you'll see that x must also be a rational fraction of this type.

With that confirmed, we run into a roadblock: although we know for a fact now what x and y are confined to value-wise, we do not know how many possible combinations work. This may not be the best solution, but here's how I handled it. I reworked the two equations we've been given so that the coefficient of one of the variables would be 1; this way I could analyze the equations efficiently. 43 mod 53 is -10. 43 16 mod 53 is -160, which, seeing as 53 -3 is -159, turns out to actually be -1. I multiplied both equations and subtracted accordingly. I also "multiplied" the variables and the int by 2018, so that I could work with whole numbers, more intuitively than fractions. Under this, x and y are integers ranging from 1 to 2017, while "int" is now a whole multiple of 2018.

688x + 752y = whole multiple of 2018

689x + 143y = whole multiple of 2018

609y - x = whole multiple of 2018

It becomes apparent here that for any y value you choose, there is a value of x that works as a solution. No matter what multiple of 609 you pick, you can subtract 2017 or less (including 0) to get an integer multiple of 2018. But, at the same time, there is only ONE positive x in this range that will work for any multiple of 609. Thus, for each of the 2017 rational fractions in the range 0<y<1 whose denominator is 2018, there is one single x-value in the range 0<y<1 that results in a solution. The answer is 2017. What's more, as a consequence of the fact that 609 and 2018 are coprime, 609*y mod 2018 from 1 to 2017 always results in a different value, so we can say that each different possible value of x must be used once. Thus, the domain of both x and y includes all possible values of 1/2018 to 2017/2018.