period of product markov chain Consider $Z_n := (X_n,Y_n)$ where $(X_n)_{n\in \mathbb{N}}$ and $(Y_n)_{n\in \mathbb{N}}$ are irreducible markov chains with periods $\lambda$ and $\mu$.
We know that $(Z_n)_{n\in \mathbb{N}}$ is a Markov Chain then. Work on the following problem:
$\mu$ and $\lambda$ have no common divisor $\iff$ $(Z_n)_{n\in \mathbb{N}}$ is irreducible; further $(Z_n)_{n\in \mathbb{N}}$ has period $\lambda \mu$ then.
I do not manage. See below:

We need to show that $\forall i,j,i',j' \exists n \in \mathbb{N}: P(Z_n = (i',j') | Z_0 = (i,j)) > 0$ $\iff$ $\operatorname{gcd}(\mu,\lambda) = 1$.
$\Rightarrow$ direction:
Consider irreducibilty, then the probabilities are always greater than zero. For an $n \in \mathbb{N}$ especially we have $P(Z_n = (i,j) | Z_0 = (i,j)) > 0$. So we have $n|\mu$ and $n|\lambda$.
But how does this impy that $\lambda$ and $\mu$ have no common divisor?
$\Leftarrow$ direction:
I do not know. It seems that if you have no common divisor you will manage to reach every tuple $(i',j')$ starting from any $(i,j)$ since you can reach every $i'$ from $i$ since X is irreducible and the same goes for the $j$'s. But I do not manage to get this formally written down..
Hints? Is this the right way to go?
 A: [Drawing out a simple case, e.g. two circles of length 2 might help visualising the problem (their product becomes a "cross").]
So as OP suggests, for irreducible $Z$ we need $\forall i, i', j, j'$ $\exists n : P_{(i,j)(i',j')}^{(n)}>0$, i.e. there is some $n$ for which the $n$-step transition probability from $(i,j)$ to $(i',j')$ is nonzero (for all pair of vertex tuples). Since $X$ and $Y$ are both irreducible, the real question here is whether it is possible to go $i \rightarrow i'$ (in $X$) and $j \rightarrow j'$ (in $Y$) in the same number of steps. 
Let the directed distances  $i \rightarrow i'$ be a mod $\bf\lambda$
and  $j \rightarrow j'$ be b mod $\bf\mu$. This is unique (well-defined) for any pair as both chains are irreducible with periods $\lambda$ and $\mu$.* Then we want $\forall a, b$ $\exists$ $l,m,n$ so that $n=l\lambda +a$ and $n=m\mu+b$, which means that we can get $i\rightarrow i'$ (in $X$) in $a$ steps then we wait there for $l$ full periods while a similar thing happens in $Y$; all these during $n$ steps (for some $n$). This allows to get $(i,j)\rightarrow(i',j')$ in exactly $n$ steps.
WE then turn to number theory. Eliminating $n$ and rearranging, we get $l\lambda-m\mu=b-a$. Having a solution $l,m$ for any $a,b$ corresponds to an irreducible $Z$. This is a linear Diophantine equation in variables $l$ and $m$, and has a solution iff gcd$(\lambda,\mu)=1$ (otherwise there is some $a-b$ which is not divisible by gcd$(\lambda,\mu)$, whereas the left hand side is). In fact, if there is one solution then there are infinitely many.
To sum up: ($Z$ is irreducible) $\Leftrightarrow$ (equation has a solution) $\Leftrightarrow$ gcd$(\lambda,\mu)=1$. The above also shows that in case of a larger gcd there will be multiple irreducible classes which are not communicating with each other.

*If there were two paths $i\rightarrow i'$ with different lengths (mod $\lambda$), then the difference would be smaller than $\lambda$, so (if we go back $i'\rightarrow i$ on the same path) there are also two circles $i\rightarrow i$ the lengths of which (mod $\lambda$) differ by less than $\lambda$. But this contradicts the definition of period, which requires $\lambda$ to be a divisor of all circle lengths.
