$a/p+b/q>1$ with certain conditions Let $a$ and $b$ be positive integers and $p$, $q$ distinct primes such that $aq\equiv 1\pmod p$ and $bp\equiv 1\pmod q$ prove that $a/p+b/q>1$. My approach was to notice that $pn+aq=qm+bp$ for some integers $n$ and $m$ (from the congruences), which is equivalent to $q(a-m)=p(b-n)$, so $a-m = px$ and $b-n = qy$, for some integers $x$ and $y$. Using the last two equalities we have $a/p+b/q = [(a-m)+m]/p+[(b-n)+n]/q>px/p+qy/q>2>1$.
My biggest concern is if I can use $x,y,n,m$ as $natural$ $numbers$ and im also concerned about the fact that I got that the expression is $>2$ which seems a very huge bound. If there is a flaw in my solution pls. point it. If the solution is completly incorrect pls show me yours. Any help appreciated.
 A: Your concerns are not unfounded.
First of all, if $0 < a < p$ and $0 < b < q$, which certainly is possible, then
$$\frac{a}{p} + \frac{b}{q} < \frac{p}{p} + \frac{q}{q} = 2\,.$$
It follows that in your argument, if everything works up to that point, you cannot have both of $x$ and $y$ be positive integers. More precisely it follows that $x + y \leqslant 1$.
We can explicitly parametrise the pairs $(m,n)$ such that $pn + aq = qm + bp$: One immediately verifies that $m_0 = a$, $n_0 = b$ works. Since changing $m$ changes the right hand side by a multiple of $q$ and changing $n$ changes the left hand side by a multiple of $p$, any two possible choices of $m$ differ by some multiple of $p$ and any two possible choices of $n$ differ by some multiple of $q$. Hence we have $m = m_0 + sp$ and $n = n_0 + tq$ for some integers $s,t$. Plugging this in, we see that we have a solution if and only if $s = t$, thus the solutions to $pn + aq = qm + bp$ are the pairs $(m_t,n_t)$, $t \in \mathbb{Z}$, where $m_t = a + tp$ and $n_t = b + tq$.
Now writing
$$\frac{a}{p} + \frac{b}{q} = \frac{(a - m_s) + m_s}{p} + \frac{(b - n_t) + n_t}{q} \tag{1}$$
is certainly possible, we don't even need to have $s = t$ in that. But to have
$$\frac{(a - m_s) + m_s}{p} + \frac{(b - n_t) + n_t}{q} \geqslant \frac{a - m_s}{p} + \frac{b - n_t}{q} \tag{2}$$
we need
$$\frac{m_s}{p} + \frac{n_t}{q} \geqslant 0 \tag{3}$$
which only obviously holds if $s \geqslant 0$ and $t \geqslant 0$. However, in that case the right hand side of $(2)$, namely $(-s) + (-t)$, is nonpositive, thus certainly not $> 1$. A less obvious but still easy to see condition for $(3)$ is $s + t \geqslant 0$, but that again renders the right hand side of $(2)$ nonpositive. We are left with the option $s + t = -1$ (see above, $s = -x$, $t = -y$), but then $(3)$ is equivalent to
$$\frac{a}{p} + \frac{b}{q} \geqslant 1\,.$$
Since $p$ and $q$ are distinct primes, this inequality is necessarily strict (if it holds), thus we are back at square one — to make the argument work, we must first prove what the argument is supposed to prove.
So let's take a different route. Get rid of the denominators, i.e. multiply the inequality with $pq$. Thus we want to show
$$aq + bp > pq\,. \tag{$\ast$}$$
Now we know everything in $(\ast)$ is a positive integer, which can be useful. And we know some congruences:
\begin{align}
aq + bp &\equiv aq \equiv 1 \pmod{p}\,,\\
aq + bp &\equiv bp \equiv 1 \pmod{q}\,.
\end{align}
Since $p$ and $q$ are coprime, it follows that
$$aq + bp \equiv 1 \pmod{pq}\,. \tag{$\ast\ast$}$$
And also $aq + bp \geqslant 1\cdot q + 1\cdot p > 1$. Together with $(\ast\ast)$ it follows that $aq + bp \geqslant pq + 1$, which is $(\ast)$.
(And in case $a < p$, $b < q$ we have $aq + bp \leqslant (p-1)q + (q-1)p < 2pq$, hence $aq + bp = pq+1$.)
A: Suppose $a_0$ and $b_0$ are the smallest positive integers, respectively, such that $a_0q \equiv 1 \pmod p$ and $b_0p \equiv 1 \pmod q$.
Note that $a_0 q \equiv 1 \equiv aq \pmod p \iff p|a-a_0$. This means $a_0<p$ and all other $a$'s are greater than $p$. Similarly $b_0 < q$ and all other $b$'s are greater than $q$.
Assume $a_0 q=pm+1, m\in \mathbb N$. Then $$pm < pm+1=a_0q  < pq \implies m < q$$ Now, $$ (q-m)p\equiv -mp=1-a_0q \equiv 1 \pmod q \\ \text{ and } 0< q -m < q$$
Therefore $b_0=q-m$. And it follows that
$$\frac ap + \frac bq \ge \frac{a_0}{p} + \frac{b_0}{q} = \frac{pm+1}{pq}+\frac{q-m}{q}=\frac{pm+1+pq-pm}{pq} = 1+\frac{1}{pq}>1.\blacksquare
$$
(We note that $p, q$ need not be prime numbers. As long as $\gcd(p,q)=1$, the inequality holds.)
