Solution to Linear Diophantine Equation: Check

Question

Problem Statement.

Let $n,p$ be positive integers where $p$ is a prime number and $n<p$. Consider the following linear Diophantine equation:

$$xn-yp=1\tag{1}$$

I am trying to prove that there exists positive integer-pair solutions $(x,y)$ with $x,y<p$.

---

My Attempted Proof. [Flawed, See Below]

Since $p$ is prime, $\gcd (n,p)=1$. Therefore, by Bézout's identity, eq. (1) always has at least one integer-pair solution $(x,y)$. This one integer-pair solution though generates infinitely many other integer pair solutions via:

$$(x,y)\longrightarrow (x+mp,y+mn),\,m\in\mathbb{Z}\tag{2}$$

So there are infinitely many integer-pair solutions $(x,y)$ with $x$ and/or $y$ positive.

$\color{red}{\text{This paragraph is wrong. }}$ Now consider the integer-pair $(x,y)$ where $x$ is smallest, i.e $1\leq x < p$. Since $1\leq n < p$, we have that $1\leq xn < np$. But from eq. (1) this immediately implies $1\leq y < n <p$. $\blacksquare$

---

Corrected "Proof".

Starting from the $\color{red}{\text{"wrong" }}$ paragraph: Now consider the integer-pair $(x,y)$ where $y$ is within the range $1\leq y \leq n$. Multiplying this inequality by $p$, we see that:

$$p\leq yp \leq np \tag{3}$$

Since the integer solution $(x,y)$ solves the Diophantine equation (1), we can replace $yp$ in the above inequality with:

$$p \leq xn-1 \leq np \tag{4}$$

Adding $1$ to both sides, and then dividing by $n$ (which is allowed since $n$ is a positive integer):

$$\frac{p}{n}+\frac{1}{n} \leq x \leq p+\frac{1}{n}\tag{5}$$

At this point we realize the falsehood of the problem statement which @Servaes notified us about in his/her answer below. If $n=1$, we see that no integer $x$ can satisfy the inequality (5). In fact, only when $n>1$ does a solution exist, and even then the value of $x$ must lie within the range:

$$1< \lfloor \frac p n + \frac 1 n \rfloor \leq x \leq p $$

$$\implies \boxed{1 < x \leq p}$$

In contrast to the range proposed in the problem statement.

Answer 1

Your proof is a good start, but is lacking in some details: In the sentence

Now consider the integer-pair $(x,y)$ where $x$ is smallest, i.e $1\leq x<p$.

You implicitly claim that such an $x$ always exists, but this requires an argument. This is not hard:

From your equation (2) it easily follows that there exists a pair $(x,y)$ with $0\leq x<p$, for example by dividing $x$ by $p$ by means of the Euclidean algorithm. And indeed $x\neq 0$ as otherwise $$1=xn-yp=-yp,$$ which is impossible as $p$ is prime.$\ \square$

More seriously, in the sentence

But from eq. (1) this immediately implies $1\leq y<n<p$.

This is false! From the inequalities $1\leq xn<np$ and equation (1) you get $$1\leq1+yp<np\qquad\text{ and so }\qquad 0\leq y<n-\frac{1}{p}<n.$$ But you cannot exclude $y=0$ in general; you can only exclude this if $n>1$. If $n=1$ you have the solution $(x,y)=(1,0)$, and in fact a more careful look shows that the statement you are trying to prove is false when $n=1$.