4
$\begingroup$

“congruence modulo $7$” is an equivalence relation on $\mathbb Z.$ Find three elements in the equivalence class $[3].$ so $3$ is congruent to $mod\ 7$..

My attempt:

a = bq + r = 7(1) + 3 = 10 , .. 7(0) + 3 = 3, .. 7(2) + 3 = 17

Thus, three elements in $[3]$ are $\{ 10, 3, 17 \}$ Is this correct?

b) Again consider the equivalence class $[3]$ for the equivalence relation “congruence modulo $7$” on $\mathbb Z.$ Suppose that $S = \{1, 2,\dots,N\}$, where $N$ is a positive integer. Find all possible values of $N$ so that $[3] \cap S$ contains exactly $10$ elements.

I know it should go from $1 - (mod \ -1)$ so there are $9$ values? I'm so confused

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes for (a) U are right

Since $$10 \equiv 3 \pmod 7$$ and $$17 \equiv 3 \pmod 7$$ and $$3 \equiv 3 \pmod 7$$

Well for (b)

You first have to list the elements in $$[3] = \{3,10,17,24,31,..... \}$$

Notice that this list keeps going on and they are all have the form $3 + 7k$ where $k$ is an integer. For your question, We are only concerned with the positive values of $k$

Now the first positive value in $[3]$ is $3$ This is when $k=0$

Now the $10^{th}$ value in $[3]$ is when $k = 9$ which is $3 + 7(9) =66$

And so if $N = 66$ then $S \cap [3] = 10$ and this will hold true for all values of $N$ up to $66 + 7 -1 = 72$

And so $ 66\leq N \leq 72$

Notice that if $N = 73$ then $S \cap [3] = 11$ because $73 \in [3]$ and so that's why it is strictly less than 73

Take some time to understand this question ! It's pretty neat and will save you a lot of time in the future because it truly tests your understanding of congruences

$\endgroup$
3
  • $\begingroup$ Amazing. Thank you so much. One more question, why would I add -1 at the end? Because of mod-1? $\endgroup$
    – AVC
    Commented Apr 28, 2015 at 4:37
  • $\begingroup$ I am sorry but I don't understand your question There are only 6 values for N not 9 $\endgroup$
    – alkabary
    Commented Apr 28, 2015 at 4:39
  • $\begingroup$ I edited my answer to involve more details $\endgroup$
    – alkabary
    Commented Apr 28, 2015 at 4:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .