Problem Statement.

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


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.

  • $\begingroup$ Your proof seems perfectly fine to me. $\endgroup$ Aug 25, 2018 at 20:20
  • $\begingroup$ @Servaes If you make your comment into an answer I can accept it. $\endgroup$ Dec 18, 2018 at 18:39
  • $\begingroup$ I've taken a second look at your attempted proof, and found a problem. See my answer. $\endgroup$ Dec 18, 2018 at 18:54

1 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$.

  • $\begingroup$ I've edited my answer to make more precise where the statement and proof fail. $\endgroup$ Dec 18, 2018 at 19:22
  • $\begingroup$ Ah, thanks. I've updated my proof, which I think is actually correct now (maybe not though). It's interesting how I as soon as I re-read my answer all I could think was "What the heck was I thinking? How'd I think that was true?". $\endgroup$ Dec 18, 2018 at 19:41
  • $\begingroup$ Your 'proof' seems correct to me now, though it is not entirely clear what you prove, as the original problem is false. Note that the original problem does not even make any sense for $p=2$, as then necessarily $n=1$. Where did you find this problem? $\endgroup$ Dec 18, 2018 at 20:12
  • $\begingroup$ And it is quite easy to believe that a statement $P$ is true when a textbook asks you to prove $P$, don't hit yourself over the head too hard over it. $\endgroup$ Dec 18, 2018 at 20:14
  • 1
    $\begingroup$ Actually I arrived at this statement by trying to prove Fermat's little theorem, and thought that the proof ultimately lied in proving the statement in my original post, but shortly posting this I learned of a much faster group-theoretic proof. :ь $\endgroup$ Dec 18, 2018 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.