Determine all pairs $(n,m)$ of positive integers for which there exists an infinite sequence $\{x_k\}$ of $0$'s and $1$'s with the properties that if $x_i=0$ then $x_{i+m}=1$ and if $x_i = 1$ then $x_{i+n} = 0.$
1. **Initial Conditions and Sequence Properties**:
   - Given an infinite sequence $\{x_k\}$ of $0$'s and $1$'s.
   - If $x_i = 0$, then $x_{i+m} = 1$.
   - If $x_i = 1$, then $x_{i+n} = 0$.

2. **Sequence Repetition**:
   - If $x_i = 0$, then $x_{i+m} = 1$ and $x_{i+n+m} = 0$.
   - If $x_i = 1$, then $x_{i+n} = 0$ and $x_{i+n+m} = 1$.
   - In both cases, $x_i = x_{i+n+m}$, indicating the sequence repeats every $n+m$ terms.

3. **Implications of Sequence Values**:
   - Suppose $x_i = 0$. If $x_{i+n} = 0$, then $x_{i+n+m} = 1$, which contradicts $x_{i+n+m} = x_i = 0$. Thus, $x_i = 0$ implies $x_{i+n} = 1$.
   - Similarly, if $x_i = 1$, then $x_{i+m} = 0$.
   - Therefore, $x_i \neq x_{i+n}$ and $x_i \neq x_{i+m}$.

4. **Periodic Nature of the Sequence**:
   - Since $x_i \neq x_{i+n}$ and $x_i \neq x_{i+m}$, we can extend this to $x_i = x_{i+2n}$ and $x_i = x_{i+2m}$.
   - This implies $x_i = x_{i+2rn} = x_{i+2rm}$ for all natural numbers $r$.
   - Adding another $n$ or $m$ to $i$, we get $x_i \neq x_{i+sn} = x_{i+sm}$ for odd positive integers $s$.

5. **Greatest Common Factor Analysis**:
   - Let the greatest common factor of $n$ and $m$ be $c$, so $n = ac$ and $m = bc$.
   - Note that $a$ and $b$ cannot both be even, as this would contradict the definition of $c$.
   - If $a$ is even and $b$ is odd, then $x_{i+abc} = x_{i+bac}$, or $x_{i+am} = x_{i+bn}$.
   - Since on the left, we added an even number of $m$'s, we should have $x_i = x_{i+abc}$. But on the right, we added an odd number of $n$'s, so we should have $x_i \neq x_{i+bac} = x_{i+abc}$, a contradiction.
   - Similarly, we cannot have an odd $a$ and an even $b$.
   - Thus, $a$ and $b$ must both be odd.

6. **Constructing a Valid Sequence**:
   - We claim that as long as $a$ and $b$ are both odd, we can construct a valid sequence $\{x_k\}$.
   - We do this by alternating groups of $c$ 1's and $c$ 0's.
   - To show that this works, we need to show that $x_i = 0$ implies $x_{i+m} = 1$ and $x_i = 1$ implies $x_{i+n} = 0$.

7. **Verification**:
   - Let $x_i = 0$, so $x_i$ is in a $0$ group. Then, $x_{i+m} = x_{i+bc}$.
   - This is the term exactly $b$ groups after $x_i$. Since $b$ is odd, $x_{i+m}$ must be in a $1$ group, so $x_{i+m} = 1$.
   - On the other hand, if $x_i = 1$, we have $x_{i+n} = x_{i+ac}$.
   - This term is exactly $a$ groups after $x_i$. Since $a$ is odd, $x_{i+n}$ must be in a $0$ group, so $x_{i+n} = 0$.

8. **Conclusion**:
   - Another way of expressing the fact that $a$ and $b$ must both be odd is to say that $n$ and $m$ have an equal power of $2$ in their prime factorization.
   - In other words, $\boxed{(n,m) = \left( 2^d p, 2^d q \right)}$ for all nonnegative integers $d$, $p$, and $q$ such that $p$ and $q$ are odd.