From Durrett's book I've come along with this problem:
Let $K\geq 3$ be a prime and let $X,Y$ be independent random variables that are uniformly distributed on $\{0,1,\ldots , K-1\}$. For $0\leq n < K$, let $Z_n = X+ nY \mbox{ mod } K$. Show that $Z_0, Z_1, \ldots , Z_{K-1}$ are pairwise independent.
Here's my proof attempt:
If $K$ is prime, then for any $\lambda > 0$, we have the next equality:
$$ \{\lambda \kappa \mbox{ mod } K: 0\leq \kappa < K \} = \{0,1,\ldots ,K-1\}.$$
Then, for any $m\geq 0$, $\mathbb{P}[X+mY = \kappa ] = 1/\vert \{0,1,\ldots , K-1\}\vert = 1/K$, for any $0\leq \kappa <K$. Now, if $m<n$ we define $\lambda = n-m >0$, and, if $0\leq m < n < K$, then for each $0\leq \kappa, \eta < K$, there is exactly one pair of numbers $0\leq x,y < K$ so that $x+my = \kappa$ and $x+ny = \eta$.
To prove pairwise independence I need to verify
$$\mathbb{P}[X+mY = \kappa,\ X+nY = \eta] = \mathbb{P}[X+mY = \kappa] \ \mathbb{P}[X+nY = \eta],$$
and we know
$$\mathbb{P}[X+mY = \kappa] \ \mathbb{P}[X+nY = \eta] = \dfrac{1}{K^{2}}.$$
My problem is that I do not know how to verify $\mathbb{P}[X+mY = \kappa,\ X+nY = \eta] = 1/K^{2}$. I have read about pairwise independence and hash functions but I'm really lost.
Is there a way to prove $\mathbb{P}[X+mY = \kappa,\ X+nY = \eta] = 1/K^{2}$ in a more intuitive way without using hash functions theory?
Best Answer
The system of congruences $$\begin{cases}X+mY \equiv \kappa \\ X + nY \equiv \eta\end{cases}$$ may be solved by substitution or elimination to find $$X \equiv \kappa - m(m-n)^{-1}(\kappa - \eta) \pmod{K} \\ Y \equiv (m-n)^{-1}(\kappa-\eta) \pmod{K}$$ In other words, $$\mathbb{P}[X+mY\equiv \kappa, X+nY \equiv \eta] = \mathbb{P}[X=x, Y=y] = \mathbb{P}[X=x]\mathbb{P}[Y=y] = \frac{1}{K^2}$$ where $x,y$ are the remainders found above.