Nice! Consider a graph $G$ with vertices $V=\{1,2,\dots,n\}$. Draw a red edge between $u,v\in V$ if $p|uv-1$ and a blue edge if $q|uv-1$. It suffices to show that $G$ is bipartite or that $G$ does not contain an odd cycle. But as no two red edges share a vertex and no to blue edges share a vertex, all cycles must have even length.

@sami1618: Nice solution. I think some parts would benefit from giving more details. Consider $G=(V,E)$ with $V=\{1,\dots,n\}$ and $E$ is such that $\{i,j\}\in E$ iff $p\mid ij-1$ or $q\mid ij-1$. The goal is to show $G$ is 2-colorable. That is, there is a way to assign one of two colors to each $i\in\{1,\dots,n\}$ such that $i$ and $j$ are of different color if $(i,j)\in E$. It's a well-known fact, see e.g. here, that a graph is 2-colorable iff it doesn't contain an odd cycle. Next, we prove $G$ has no odd cycles. Assume the converse that $x_1,x_2,\dots,x_{2k+1},x_1$ is an odd cycle. Without loss of generality, let $p\mid x_1x_2-1$. If $p\mid x_2x_3-1$, as well, then $p\mid x_2(x_1-x_3)$. Since $x_2\le n<p$, this forces $p\mid x_1-x_3$, i.e., $x_1=x_3$. As $x_1\ne x_3$, this is impossible. So, $q\mid x_2x_3-1$, $p\mid x_3x_4-1$ and so on. Continuing, we find $p\mid x_{2k+1}x_1-1$. This combined with $p\mid x_1x_2-1$ yields $x_2=x_{2k+1}$, a contradiction. So, $G$ indeed has no odd cycles.

Uh... Can't you just color it any way you want? Suppose that $p \neq q$ and there are $x \neq y$ such that $p|xy-1$ and $q|xy-1 \implies pq|xy-1 \implies n^2 < pq \le xy-1 < n^2-1$, contradiction! So $p=q$. And for that we just want a coloring such that $x$ and $x^{-1}$ modulo $p$ doesn't have the same color. But for this just start coloring from $1$ to $n$ with color 1 and if at some point the number $x$ you will color has its multiplicative inverse (modulo $p$) already colored, just color it the second one. And since multiplicative inverses are unique, this algorithm will never fail.