Why $\,p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) = pq + 1$? This is going to sound like a stupid question, but I cannot understand how I get this result (I understand why, but it looks like there is no relation).
$p, q$ primes
why do we have this?
$p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) = pq + 1$
I don't see the relation between the left and right side, but still it works.
 A: Of course it is tacitly assumed that $p\ne q$. 
I'm interpreting $\ p^{-1}\>{\rm mod}\>  q$ as the unique $x\in[1\>..\>q-1]$ with $xp=1\>{\rm mod}\>  q$, and similarly $\ q^{-1}\>{\rm mod}\> p$ as the unique $y\in[1\>..\>p-1]$ with $yq=1\>{\rm mod}\>  p$. If $x$ and $y$ are determined in this way the number $n:=xp+yq$ satisfies $$ n\leq 2pq-p-q$$
and
$$n=1\ {\rm mod}\>  p,\qquad n=1\ {\rm mod}\>  q\ .\tag{2}$$
The number $n':=pq+1$ satisfies $(2)$. On the other hand, by the Chinese remainder theorem there can be no other such number in the interval $[\,pq,\> 2pq-p-q\,]$. It follows that $n=n'$.
If you want to avoid the CRT you can argue as follows: As ${\rm gcd}(p,q)=1$ there are $x$, $y\in{\mathbb Z}$ with $$xp-yq=1\ .$$
After adding a suitable $kq$ to $x$, and at the same time $kp$ to $y$ we may assume $x\in[1\>..\>q-1]$. It follows that
$$yq=xp-1\in[p-1\>..\>pq-p-1]\ ,$$
which then implies $y\in[1\>..\>p-1]$. It follows that $y':=p-y\in[1\>..\>p-1]$ as well, and we now have
$$xp+y'q=xp+(p-y)q=pq+1\ ,$$
which is the claimed formula.
A: First, let's clarify the question, since one of the commenters was confused:
By
$$p \cdot (p^{-1} \mod q)$$ the question means to find $ p^{-1}\mod q$, transform that into the unique integer $\bar{p} \in \Bbb{N} : \bar{p} \equiv p^{-1}\mod q \wedge 0\leq \bar{p} < q$, and then multiply, in the ordinary field of integers,
$p\cdot \bar{p}$. 
With that understanding in place, here is your proof that $s = p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) = pq+1$ assuming $p,q$ prime:
Lemma 1: $p \cdot (p^{-1} \mod q) \equiv 1 \mod q$.  Proof: This is just the definition of the inverse, mod $q$.
Corollary 2: $s \equiv 1 \mod q$.  Proof: $s =  p \cdot (p^{-1} \mod q) + qk$ where $k$ is some integer (which happens to be $(q^{-1} \mod p)$) so $s  \equiv 1 + 0 \mod q$.
Corollary 3: $s \equiv 1 \mod p$. This is the same statement as corollary 2, exchanging $p$ and $q$.
Lemma 4:  $s \equiv 1 \mod (pq)$.  This is so by corollaries 2 and 3, along with the statement that $p$ and $p$ are coprime.
Lemma 5: $s > 1$.  Proof: each of the terms in $s$ is a positive integer, so $s \geq 1+1$.
Lemma 6: $p \cdot (p^{-1} \mod q) < pq$ and $q \cdot (q^{-1} \mod p) < qp$. Proof: $p^{-1} \mod q < q$; multiply both sides of that relation by $p$. Similarly for the assertion about $q \cdot (q^{-1} \mod p)$.
Corollary 7: $s = p \cdot (p^{-1} \mod q) + q \cdot (q^{-1} \mod p) < 2pq$.
Theorem: $s=pq+1$. Proof: by lemma 5 and corollary 7, $1 < s < pq$.  By lemma 4, $s = kpq + 1$ for some integer $k$.  The unique value of the form $kpq + 1$ between $1$ and $2pq$ is $pq+1$.
Q.E.D.
