Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm asked for all possible values, but I can only see one. The question on my practice exam reads:

Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. Suppose that $S = {1, 2, ..., N}$, where $N$ is a positive integer. Find all possible values of $N$ so that $[3] \cap S$ contains exactly $10$ elements.

As I see it, $S$ must be $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$, so all possible values of $N$ are $12$?

$3$ and $10$ and members of $[3]$, but $13$ is not, so any higher values would have more than $10$ elements.

share|cite|improve this question
What about $\,S=\{1,2\ldots,73\}\,$ ? How many integers here equal $\,3\pmod 7\,$ ? – DonAntonio Apr 23 '13 at 3:12
Oh boy... hours of studying have left me unable to discern between union and intersection. Thank you :) – GotterdammerunG Apr 23 '13 at 3:21
up vote 4 down vote accepted

Recall that $[3]$ is an equivalence class, representing a set:

$$x \in [3] \iff x \equiv 3 \pmod 7 \implies x = 7k + 3 \;\text{ where}\;\;k\in \mathbb Z$$

What integers $x$ in $\mathbb N = \{1, 2, 3, ....\}$, are such that $x = 7k + 3, k\geq 0\,$? We need the first ten such elements in the natural numbers, and let's call the set of the first ten elements $X$:

$$X =\{3, 10, 17, 24, 31, 38, 45, 52, 59, \bf 66\} $$ is the set of the first ten elements in $[3]$, if we are considering only values of $x \in [3]$ as a subset of the natural numbers.

$$S \subset \mathbb N = \{1, 2, 3, \cdots, 65, {\bf 66}\}$$

$$|X \cap S| = 10 \implies \bf N = 66$$

share|cite|improve this answer
Union / Intersection confusion: time for a sandwich break :) Thanks again – GotterdammerunG Apr 23 '13 at 3:24
100% What a great website/community here! – GotterdammerunG Apr 23 '13 at 3:26
Glad to help! ;-) – amWhy Apr 23 '13 at 3:27
Hahaha... still cheaper than a tutor ;) I do appreciate it! – GotterdammerunG Apr 23 '13 at 3:31
Yes, and likely quicker than a waiting until you're next meeting with a tutor! ;-) – amWhy Apr 23 '13 at 3:32

The first $10$ positive integers that belong to the equivalence class are $3, 10, 17, 24, 31, 38, 45, 52, 59, 66$.

So we need to go up to $66$ at least, and we don't want the next one, $73$, for that would put us over.

Remark: The number $7$ definitely does not belong to the equivalence class of $3$ modulo $7$, since the difference between $7$ and $3$ is not divisible by $7$.

The equivalence class of $3$, in symbols $[3]$, consists of all integers $n$, positive, negative, or $0$, such that $n\equiv 3\pmod{7}$. In more old-fashioned language, it consists of all integers $n$ of the form $7k+3$.

Very soon, we start thinking of $[3]$ as a single abstract object, and we kind of forget that, in principle, it is an infinite set. In that sense, the question was a bit of a trick question.

share|cite|improve this answer
Framing an equivalence class as you did has given me a more intuitive understanding of the subject. Those problems should be a piece of cake now, at least in the context of my current math class. Thank you. – GotterdammerunG Apr 23 '13 at 3:38
@GotterdammerunG: You are welcome. But soon, as I mentioned, you will need to think of the equivalence classes mainly as new kinds of objects which are as concrete as the integers themselves. – André Nicolas Apr 23 '13 at 3:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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