Can there be two hash functions without common collisions? Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision?   I mean, like provable in way that someone who took one cryptography class in university can prove.  

For example, I want hash functions $A$ and $B$ such that if hash function $A$ collides on $X$ and $Y$, then $B$ will not collide on these $X$ and $Y$:

$$A(X) = A(Y) \quad \Rightarrow \quad B(X) \neq B(Y) $$
No, in general, there will always be a pair of inputs that will collide for both hash functions.  Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $X$ and $Y$ with $X \neq Y$, $A(X) = A(Y)$ and $B(X) = B(Y)$

Here is a simple demonstration that such a pair must exist: let us assume that $A$ generates an output which is $n$ bits long, while $B$ generates an output which is $m$ bits long, and further assume that $n, m &gt; 0$.

Now, consider the set of all possible bitstrings of length $n+m$, along with the empty bitstring (or, if you don't like that, pick any bitstring shorter than $n+m$).  This set has size $2^{n+m}+1$.  If we apply the hash function $A$ to each member of the set, there are $2^n$ possible outputs, and hence (by the pigeon-hole principle), there must be some output with at least $2^m+1$ preimages.  Let us pick such an output, and call the subset when generates that output subset $W$.

Now, let us consider applying the hash function $B$ to each member of $W$; $W$ has size at least $2^m+1$, and $B$ has $2^m$ possible outputs; hence there must be two elements $X$ and $Y$ of $W$ with the output.

This pair $X$ and $Y$ is a common colliding pair for $A$ and $B$.