Solving Multiple Equations with Many Variables

Question

Here's a problem I have stumbled upon, which may have a straightforward solution with linear algebra. If so, I cannot see it.

Choose $n > 0 \in \mathbb N$, and consider the sequence of equations:

$$nx_1 + (n-1)y_1 - 1 = 0$$ $$nx_2 + (n-2)y_2 - 1 = 0$$ $$...$$ $$nx_{n-1} + y_{n-1} - 1 = 0$$

Equivalently, consider all equations for $0 < k < n$ such that

$$nx_k + (n-k)y_k - 1 = 0$$

How might I go about determining if these equations have a solution for $x_k, y_k \in \mathbb R$? In particular, I was hoping someone could help me restate the problem using linear algebra.

NOTE

The original formulation required $x_k, y_k \in \mathbb Z$, in which case, the existence of a solution to these equations is true iff $n$ is prime. I've weakened the constraint in the hopes of finding ways to express or understand this problem without the concepts of $gcd$ or the Euclidean Algorithm.

Answer 1

By Bézout's Theorem, the diophantine equation $$ax + by = 1$$ where $a, b \in \mathbb Z$ has integer solutions for $x$ and $y$ if and only if $hcf(a,b)=1$.

Hence, the equation $$nx_k + (n-k)y_k - 1 = 0$$has solutions if and only if $$hcf(n, n-k) = hcf(n,k)=1$$

In particular, if $n$ is prime, then all of the equations will have solutions.

Answer 2

If $n$ is not prime, then let $d$ be a divisor of $n$ such that $1 < d < n$. Then, $nx_{n-d} + dy_{n-d} = d\left(\tfrac{n}{d}x_{n-d}+y_{n-d}\right)$ is a multiple of $d$, so $nx_{n-d} + dy_{n-d} = 1$ has no solutions.

If $n$ is prime, then $\text{gcd}(k,n) = 1$ for all $1 \le k < n$, and so we can use the Euclidan Algorithm to find a solution $(x_k,y_k)$ for each equation $nx_{n-k} + ky_{n-k} = 1$.