# “Tricky” wording on Congruence Modulo Question?

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.

• 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

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$$

• 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.

• 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