Why do all integer solutions of $\frac{157}{50}<\frac{p}{q}<\frac{22}{7}$ for $q>0$ have the form $p=157n_1+22n_2+179,q=50n_1+7n_2+57$?

Question

This is from my attempt to show $\frac{22}{7}$ is the best approximation of $\pi$ with denominator not more than $50$.
My attempt as follows:
Suppose there is a better rational approximation, $\frac pq$: $\left|\pi-\frac pq\right|<\frac{22}{7}-\pi$ $$\pi-\frac{22}{7}<\pi-\frac pq<\frac{22}{7}-\pi$$ $$-\frac{22}{7}<-\frac pq<\frac{22}{7}-2\pi$$ $$\frac{22}{7}>\frac pq>-\frac{22}{7}+2\pi$$ $$\frac{22}{7}-3>\frac {p-3q}q>-\frac{22}{7}-3+2\pi$$ $$\frac{1}{7}>\frac {p-3q}q>\frac{14\pi-43}{7}$$ $$7<\frac q{p-3q}<\frac{7}{14\pi-43}$$ $$0<\frac {22q-7p}{p-3q}<\frac{308-98\pi}{14\pi-43}$$ $$\frac {p-3q}{22q-7p}>\frac{14\pi-43}{308-98\pi}>7$$ Then, in order not to re-arrange terms by hand, I fed the latter inequality to wolframalpha, obtaining $$(50 p - 157 q) (7 p - 22 q)<0$$ $$\frac{157}{50}<\frac{p}{q}<\frac{22}{7}\tag{1}$$ and along with this one more thing, with Reduce[(p - 3 q)/(-7 p + 22 q) > 7, {p, q}, Integers]: $$p = 157 n_1 + 22 n_2 + 179,\, q = 50 n_1 + 7 n_2 + 57,\, n_1, n_2 \in \mathbb{Z}_{+}\tag{2}$$ which solves the original problem (as $q\ge 57$).

However, I do not know any explanation on how is it derived, I'm feeling that I'm missing something well-known. The first idea I can think of is like we solve $$0<\frac{p}{q}-\frac{157}{50}<\frac{22}{7}-\frac{157}{50}$$ $$0<\frac{50p-157q}{50q}<\frac{1}{350}$$ $$0<7(50p-157q)<q$$ ... we solve Diophantine equation $7(50p-157q)=k$ for every $0<k<q$, but it doesn't seem to produce such a neat result. So the question is: how does (1)$\Rightarrow$(2)? References where I can read a more general case may be even better (if available for free).

Thanks.

Answer 1

It is true that, for any positive integers $u,v$ $$ \frac{157}{50} < \frac{157u + 22v}{50u + 7v} < \frac{22}{7} $$ However, take $u,v$ fairly large, you can alter the numerator a little bit (say by $\pm 1$) and still have that inequality

Answer 2

I suppose it's nearly an answer.
It's claimed or even somehow proven or obvious that every rational number ($\frac pq$, in lowest terms) between $\frac{157}{50}$ and $\frac{22}{7}$ will be in a Farey sequence, namely in the Farey sequence of order $q$.

Every number in a Farey sequence is the mediant of its neighbours (mediant of $\frac ab,\,\frac cd$ is defined to be $\frac{a+c}{b+d}$). And "climbing up" from every number that is not $\frac{157}{50}$ or $\frac{22}{7}$ to its neighbours we will eventually reach the ends of the interval $\left[\frac{157}{50},\frac{22}{7}\right]$ (although it's not so obvious that we can't get out of the interval, but it's likely believed), then performing "climbing down" through the same numbers by which we did "climb up" we can go nowhere from the form $\frac{157u+22v}{50u+7v}$, QED.
It's like adding vectors, when we have $(157,50)$ and $(22,7)$ and the only permitted operation $a,\,b\to (a+b)$ we can nowhere escape from the form of $(157u+22v,50u+7v)$. Suppose it's rigorous enough.)
Many thanks to @Barry Cipra and @Will Jagy (and the anonymous upvoter of the question's comment) for carrying this out to me.

Answer 3

Proposition. Let $a$, $b$, $c$, and $d$ be integers such that $b>0$, $d>0$, and $\delta:=ad-bc>0$. Then, any rational number $r$ such that $$\frac{a}{b}>r>\frac{c}{d}$$ is of the form $$r=\frac{an+cm}{bn+dm}$$ for some positive integers $m$ and $n$.

Suppose that $p$ and $q$ are integers such that $q>0$ and $r=\dfrac{p}{q}$. Then, we have $$\frac{a}{b}>\dfrac{p}{q}>\frac{c}{d}\,,$$ whence $$aq-bp=m\text{ and }dp-cq=n$$ for some positive integers $m$ and $n$. That is, $$\delta p=(ad-bc)p=a(dp-cq)+c(aq-bp)=an+cm$$ and $$\delta q=(ad-bc)q=b(dp-cq)+d(aq-bp)=bn+dm\,.$$ Hence, $$p=\frac{an+cm}{\delta}\text{ and }q=\frac{bn+dm}{\delta}\,.$$ This shows that $$r=\frac{p}{q}=\frac{\left(\frac{an+cm}{\delta}\right)}{\left(\frac{bn+dm}{\delta}\right)}=\frac{an+cm}{bn+dm}\,.$$

Corollary. Let $a$, $b$, $c$, and $d$ be integers such that $b>0$, $d>0$, and $ad-bc=1$. Then, if $p$ and $q$ are integers such that $q>0$ and $$\frac{a}{b}>\dfrac{p}{q}>\frac{c}{d}\,,$$ then $$p=an+cm\text{ and }q=bn+dm$$ for some positive integers $m$ and $n$.

In particular, when $a=22$, $b=7$, $c=157$, and $d=50$, we have $\delta=1$. Thus, the corollary applies: for all positive integers $p$ and $q$ such that $$\frac{22}{7}>\frac{p}{q}>\frac{157}{50}\,,$$ there exist positive integers $m$ and $n$ for which $$p=22n+157m\text{ and }q=7n+50m\,.$$ By setting $m':=m-1$ and $n':=n-1$ (so $m'$ and $n'$ are nonnegative integers), we get $$p=22n'+157m'+179\text{ and } q=7n'+50m'+57\,.$$

Remark. The corollary is false if $\delta=ad-bc>1$. For example, when $a=1$, $b=1$, $c=1$, and $d=\delta+1$, we can take $p=1$ and $q=\delta$, which do not satisfy the conclusion of the corollary.