Graph and Number theory 
We have two groups of nodes, group A consisting of N items, group B
consisting of M items. There is an edge connecting node $a$ of group A and node $b$ of group B,
where 
$$a = i \mod N$$ 
$$b = i \mod M$$
where i is an integer.
We need to find for each node if there is a path connecting to another node in the graph.
As I am a CS guy, I love brute force. To create the adjacency matrix,
I iterated from $i$ from $0$ to $LCM(N, M)$, since after that, we would
get same edge pairs. Now, discarding this approach, how can one find mathematically, if two nodes of the graph are connected by a path or not?

You can readily show:

Node $x$ (from $A$ or $B$) is connected to node $y$ (from $A$ or $B$) iff $x\equiv y\pmod{\gcd(N,M)}$

Here's a sketch:
The group $\mathbb Z$ acts on the graph as follows: If $k\in \mathbb Z$, then the action maps vertex $a\in A$ to $a+k\bmod N\in A$ and vertex $b\in B$ to vertex $b+k\bmod M\in B$. This works because an edge $(a,b)$ that is witnessed by the integer $i$ with $a\equiv i\pmod N$, $b\equiv i\pmod M$ becimes the edge $(a+k\bmod N,b+k\bmod M)$ witnessed by $i+k$.
By this action we conclude: If $a_1,a_2\in A$ then the existence of a path from $a_1$ to $a_2$ depends only on $a_2-a_1\pmod N$.
Let $I$ be the set of integers $k$ such that there exists a path for some pair $(a_1,a_2)$ with $a_2-a_1\equiv k\pmod N$. (As just seen "for some pair" implies "for all pairs").


*

*$I$ is not empty, for example clearly $N\in I$ and $M\in I$.

*If $k\in I$ then also $-k\in I$ (just interchaneg $a_1$ and $a_2$)

*If $k_1,k_2\in I$ then $k_1+k_2\in I$ (just concatenate two paths).


It follows that $I$ is an ideal in $\mathbb Z$ and contains $N$ and $M$, hence is of the form $I=d\mathbb Z$ with $d\mid\gcd(N,M)$.
But $d$ cannot be a properdivisor of $\gcd(N,M)$ because for every single edge $(a,b)$ with $a\equiv i\pmod N$ and $b\equiv i\pmod M$ we have that $a\equiv i\equiv b\pmod{\gcd(N,M)}$.
So far we have

If $x,y\in A$ then they are connected iff $x\equiv y\pmod{\gcd(N,M)}$

By symmetry, we also have

If $x,y\in B$ then they are connected iff $x\equiv y\pmod{\gcd(N,M)}$

To also treat the case when $x\in A$, $y\in B$ (or vice versa) note that the first edge from $x$ to a vertex in $B$ (or vice versa) connects vertices that are congruent modulo $\gcd(N,M)$.
