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?
Best Answer
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.