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.

  • $\begingroup$ I don't understand what you mean by restrictions. $\endgroup$ – user3865391 Dec 6 '18 at 20:11
  • $\begingroup$ 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$? $\endgroup$ – zoidberg Dec 6 '18 at 20:28
  • $\begingroup$ Please don't downvote posts simply because you don't understand. $\endgroup$ – zoidberg Dec 6 '18 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.