# Linear combination of relative primes

I apologise if this question is a duplicate, I couldn't find it anywhere.

I came across the following problem:

An ordered pair $(x,y)$ of integers is called a primitive point if the greatest common divisor of $x$ and $y$ is $1$.Given a finite set $S$ of primitive points, prove that there exists a positive integer $n$ and integers $a_0, a_1,\ldots, a_n$ such that for all $(x,y) \in S$ we have that $$a_0x^n\ + \ a_1x^{n-1}y\ +\ a_2x^{n-2}y^2\ + \ldots+\ a_{n-1}xy^{n-1} \ + \ a_ny^n=1.$$

How does one go about proving this?

What first came to mind was to use induction on this problem. I believe this should work for any points $(x,y)$ where $x$ and $y$ are relatively prime. For the base case $n=1$ we would have that $$ax +by=1$$ for some integers $a$ and $b$ which we know exist because of Bézout's identity. However I don't know how to follow up or even if induction is the proper way to tackle this problem. It also seems to me this has a strange similarity to the binomial theorem, could they be connected somehow?

Any hints and/or ideas are welcome!

• Can we assume that the $x_j$ are pairwise distinct ? Apr 24, 2018 at 11:24
• @Peter I'm afraid the problem doesn't specify. I would think it need not be so, but I could be wrong. Does it make more sense to you that they should be pairwise distinct? Apr 24, 2018 at 11:57
• In the case of pairwise distinct $x_j$, I think we can work somehow with the Lagrange-interpolation polynomial, but for arbitary $(x/y)$, I am not sure whether the claim is true. Apr 24, 2018 at 12:50
• perhaps the first thing to investigate is the possibility that there exist solutions for all $n$. if there are $w$ primitive points $(x_w,y_w)$ and $(a_w x_w - b_w y_w)=1$. It would follow immediately that $(a_w+m y_w)x_w-(b_w+m x_w)y_w=1$ where $m$ is any non-negative integer. Do there exist paired choices of $(a_w+m y_w)$ and $(b_w+m x_w)$ for some particular choice of $w$ where all the values $x_w$ are a divisor of $(a_w+m y_w)$ and all the values $y_w$ are a divisor of $(b_w+m x_w)$ Apr 26, 2018 at 15:49
• This problem is even harder than it seems on the first look. I have tried a very simple example with just two primitive points: (3,5) and (2,7). I also assumed that the solution for two points is of the form: $a x^2+b x y+c y^2$. This leads to $b=\frac{24-341a}{385}, c=\frac{1+66a}{385}$. There are no integer numbers $a,b,c$ satisfying these conditions because, for example, 11 divides 385 but does not divide $1+66a$. So even in the simplest case with just two primitive points, $n$ must be greater than 2.
– Saša
May 1, 2018 at 18:13