10. A lattice point is a point whose coordinates are both integers. Suppose Johann walks in a line from the point $(0,2004)$ to a random lattice point in the interior (not on the boundary) of the square with vertices $(0,0),(0,99),(99,99),(99,0)$. What is the probability that his path, including the endpoints, contains an even number of lattice points?
Solution:
$$
3 / 4
$$

If Johann picks the point $(a, b)$, the path will contain $\operatorname{gcd}(a, 2004-b)+1$ points. There will be an odd number of points in the path if $\operatorname{gcd}(a, 2004-b)$ is even, which is true if and only if $a$ and $b$ are both even. Since there are $49^{2}$ points with $a, b$ both even and $98^{2}$ total points, the probability that the path contains an even number of points is
$$
\frac{98^{2}-49^{2}}{98^{2}}=\frac{49^{2}\left(2^{2}-1^{2}\right)}{49^{2}\left(2^{2}\right)}=\frac{3}{4} .
$$