Proof by Contradiction - two distinct primes not divisible by each other
Solution 1:
This is so trivial it immediately follows by definition of prime numbers, but I will provide a proof by contradiction anyways:
Assume $p$ and $q$ are distinct prime numbers and $p|q$. Then, because $q$ is prime, $q$ has only trivial divisors, i.e. $p = 1$ or $q = p$. The case $q = p$ is not possible, since $p$ and $q$ are distinct. So therefore, we conclude that $p = 1$, but $p$ is a prime number and $1$ is not. A contradiction.