If $p,q$ are two primes with $p \neq q$, why does $p \not\equiv 1$ (mod $q-1$) or $q \not\equiv 1$ (mod $p-1$) hold? I assume that $p \equiv 1$ (mod $q-1$), so I must show that this implies $q \not\equiv 1$ (mod $p-1$) then. The assumption implies that there is a $c$ such that $p-1 = c(q-1)$. In particular, since $c$ must be positive, this implies $q<p$. However, this is where I don't know how to continue with my computatio in order to show $q \not\equiv 1$ (mod $p-1$).
Could you please guide or explain me how to continue from here?
 A: Q9y5 gives a quicker explanation, but the answer can still be seen starting from something similar to your approach. If $q\equiv1\mod(p-1)$, then $q=1+n(p-1)$ for some $n\in\mathbb{N}$, which leads to $\frac{q-1}{p-1}=n$. Alternatively, if $p\equiv1\mod(q-1)$ we get $\frac{p-1}{q-1}=m$ for some $m\in\mathbb{N}$. Neither $n$ nor $m$ is $1$ as this would imply $p=q$, but it clearly holds that $n=1/m$. However, both $n$ and $m$ are positive integers and not equal to one, so this is a contradiction and thus both of our assumptions cannot hold simultaneously. Note that we don't need to worry about division by 0 anywhere as 1 is not prime.
A: Continue with what you have tried. For integers, $q<p$ implies $q\leq p-1$, therefore $q\equiv 1\left(\text{mod }p-1\right)$ means either $q=1$ or $q=p$, both are invalid.
A: Assume BOTH are true: $p \equiv 1 \pmod {q-1}$ AND $q \equiv 1 \pmod{p-1}$. Then your argument shows that $q<p$ AND $p<q$. This contradiction proves that one of the congruences is false.
