$\newcommand{\lcm}{\operatorname{lcm}}$
Suppose $\Bbb{Z}_{n\cdot m} \cong \Bbb{Z}_m\times \Bbb{Z}_n$, then the highest order of an element of $\Bbb{Z}_{n\cdot m}$ is $nm$, and the highest order of an element of $\Bbb{Z}_m\times \Bbb{Z}_n$ is $\lcm(n,m)$. Thus for the two groups to be isomorphic, we must have $\lcm(n,m)=nm$, but since $g\ell = nm$ where $g=\gcd(n,m)$, and $\ell = \lcm(n,m)$, this means that $g=1$, and so we must have had that $n$ and $m$ are relatively prime.
The larger case should be true by induction in one direction and a direct generalization of this argument in the other.
In modulo arithmetic, "division" means multiplying by the multiplicative inverse, e.g., $b = \frac{1}{a}$ means the value which when multiplied by $a$ gives $1$ modulo the value, e.g., $ba \equiv 1 \pmod n$. Note you may sometimes see $b = a^{-1}$ instead to avoid using explicit "division". This works, and gives a unique value, in any cases where the value you're dividing and the modulus are relatively prime.
More generally, it'll work in all cases of $\frac{c}{a} \equiv e \pmod n$ where $d = \gcd(a,n)$ and $d \mid c$ since this gcd value "cancels" in the division. Thus, the resulting equivalent modulo equation of $\frac{c'}{a'} \equiv e \pmod n$, where $c' = \frac{c}{d}$ and $a' = \frac{a}{d}$ has $\gcd(a',n) = 1$, has a solution. However, as Bill Dubuque's comment indicates, this assumes you're doing integer division to the extent of removing the common factor of $d$. Note that $a^{-1}$ doesn't exist modulo $n$ in this case. However, $(a')^{-1}$ does exist modulo $\frac{n}{d}$, so a possible interpretation would be $\frac{c'}{a'} \equiv c'(a')^{-1} \equiv e \pmod{\frac{n}{d}}$.
As for why the multiplicative inverse $b = a^{-1}$ exists modulo $n$ if $\gcd(a,n) = 1$, Bézout's identity states that in such cases there exist integers $x$ and $y$ such that
$$ax + ny = 1 \tag{1}\label{eq1}$$
As such $ax \equiv 1 \pmod n$ so $x \equiv a^{-1} = b \pmod n$. This value must be unique, modulo $n$, because if there was another value $x'$ such that $xa \equiv x'a \equiv 1 \pmod n$, then $(x - x')a \equiv 0 \pmod n$. Since $\gcd(a,n) = 1$, this means that $x - x' \equiv 0 \pmod n \; \iff \; x \equiv x' \pmod n$.
Bézout's identity also shows that if $a$ and $n$ are not relatively prime, e.g., $\gcd(a,n) = d \gt 1$, then \eqref{eq1} becomes
$$ax + ny = d \tag{2}\label{eq2}$$
with the integers of the form $ax + ny$ are always multiples of $d$, so it can't be congruent to $1$ and, thus, $a$ would not have a multiplicative inverse.
Best Answer
This is not a robust answer, but provides a heuristic reasoning for why the approach proposed in the question may not work.
For a suitably arbitrary prime $p$, a pair of residues $x,y \pmod{p}$ are likely to be coprime i.e., their GCD is likely to be $1$ with more than $0.5$ probability.
For example, there are $13$ coprime pairs modulo $5$ (therefore, coprimality probability = $0.52$) and $93$ pairs modulo $13$ (coprimality probability = $0.55$) and the limit for the probability is $6 \over \pi^2$ as $p \rightarrow \infty$. This is approximately $0.61$. (See this question and answer for more info).
If the prime doesn't divide the integers $x,y$ then we have to ignore the residue pairs $(0, y)$ and $(x, 0)$ and then the effective coprimality probability would go up even higher.
So, using even a probabilistic argument, we are likely to see $1$ as the GCD of the residues quite often even when the numbers themselves are not coprime.
Using this and the pigeon-hole principle, we should be finding the actual GCD only by chance (and very low at that).