# Counting equivalence classes

Given any $$n$$ integers $$m_1,m_2,\ldots m_n\in \mathbb{N}$$ if we define an equivalence relation $$\sim$$ on $$\mathbb{N}^n$$ as follows:

$$(a_1,a_2,\ldots a_n)\sim (b_1,b_2,\ldots b_n)\iff \text{For every integer }1\leq k\leq n\text{ we have }a_k\equiv b_k\bmod m_k$$

Then what is the cardinality of the quotient set $$\mathbb{N}^n/\sim$$?

For the special case when $$m_1,m_2,\ldots m_n$$ are pairwise coprime, I know $$|\mathbb{N}^n/\sim|=m_1m_2\cdots m_n$$. However what about in general when $$m_1,m_2,\ldots m_n$$ might have common factors?

The answer is unconditionally $$m_1...m_n$$. You did not place any restrictions between the entries of the $$n$$-tuple.
• You say you have an argument when $m_i$ are pairwise coprime. Is there anything that goes wrong with the proof when for instance $n=2$ and $m_1=2,m_2=4$? – zoidberg Dec 6 '18 at 20:28