-2

Let $\overline{a}\in{}\mathbb{Z}/157\mathbb{Z}$ , and we consider \begin{equation} \overline{17},\qquad \overline{-768},\qquad \overline{51},\qquad \overline{1744},\qquad\overline{100},\qquad\overline{-57} \end{equation} How many different elements of $\mathbb{Z}/157\mathbb{Z}$ are listed above?

I originally thought we'll need to figure out the congruent pairs from the given list and figure out which ones are distinct and hence count towards the "different" elements, although I doubt my reasoning is right, and even if it is, it'll be quite tedious to check for every pair out there so I think am missing something. What's the reasonable way to go about this?

Arturo Magidin
  • 398,050
kareem bokai
  • 157
  • 2
    I think an easy method is to mod each of these numbers by 157 and just directly compare them. Note that you'll only need to do this for $-768, 1744,$ and $-57$ as the others are already between $0$ and $156$ – Theo C. Feb 27 '19 at 15:39
  • @TheoC. That doesn't apply here: He's asking for the correct representatives. – Jossie Calderon Feb 27 '19 at 15:42
  • Yes I figured that much, but I was wondering if there's a way to go about this without checking every single pair together. Maybe am being lazy actually I don't know – kareem bokai Feb 27 '19 at 15:45
  • 5
    @JossieCalderon I don't understand what you mean by "the correct representatives". – Calum Gilhooley Feb 27 '19 at 15:48
  • @CalumGilhooley By definition, $\bar{-768}$ can NOT be in the set. – Jossie Calderon Feb 27 '19 at 15:52
  • Has somebody just systematically downvoted all the answers? – Calum Gilhooley Feb 27 '19 at 15:54
  • I have no idea, I can't even downvote because I don't have 125 reputation yet.. – kareem bokai Feb 27 '19 at 15:54
  • 6
    @JossieCalderon I have no idea what you are saying. I assume that $\overline{x}$ is short for a coset $x+157\mathbb{Z}$. So $\overline{-768}$ makes total sense and Theo's method works correctly. For any $\overline{x}$ you take $x\text{ mod }p$ to obtain normalized (i.e. between $0$ and $p$) representatives. Then you remove duplicates. – freakish Feb 27 '19 at 16:05
  • @freakish That's indeed what I meant with the notation, sorry didn't make that clear in the question. And $\overline{-768}$ does make sense, I don't know why JossieCalderon insist it doesn't. – kareem bokai Feb 27 '19 at 16:11
  • 1
    @kareembokai Don't worry, your question and Theo C.'s comment on it were both perfectly clear - it's just some of the other comments that have baffled me! – Calum Gilhooley Feb 27 '19 at 16:28

3 Answers3

1

To expand on my approach mentioned in the comments:

First, recall that $\mathbb{Z}/n\mathbb{Z} = \{\overline{0},\overline{1},...,\overline{n-1} \}$, where $\overline{j} = \{j + k*n, k\in \mathbb{Z}\} = \{j,j\pm n, j\pm 2n,...\}$. Often, people call these elements "residue classes". Note that there is no restriction on $j$, other than $j$ being an integer. As a quick example, take the group $\mathbb{Z}/3\mathbb{Z} = \{\overline{0},\overline{1},\overline{2}\}$, and note:

$$\overline{3} = \{3+k*3, k\in \mathbb{Z}\} = \{...,-9,-6,-3,0,3,6,9,...\} = \{0+k*3,\ k\in \mathbb{Z}\} = \overline{0} $$

So to recap: there are only $n$ distinct residue classes in $\mathbb{Z}/n\mathbb{Z}$, but there are many different ways of rewriting this same set of $n$ elements.

Now consider (for example), the element $\overline{100}$ of your group $\mathbb{Z}/157\mathbb{Z}$: $$\overline{100} = \{100 + 157k, k\in\mathbb{Z}\} = \{...,-57,100,257,...\} $$ Now, we could immediately glean from this that $\overline{100}=\overline{-57}$ in $\mathbb{Z}/\mathbb{157Z}$, but for larger numbers, listing out this set becomes increasingly painful. So ideally we could take a shortcut.

What I suggested above was to take each element, and perform division by $157$ to find the modulo of each element. The machinery behind this suggestion is the claim that any two residue classes $\overline{a}$ and $\overline{b}$ are equal if and only if $a\equiv b \mod n$ (try proving this to yourself if you haven't yet seen this).

So anyway, performing this with the given numbers in question, we have $$(\overline{17}, \overline{-768}, \overline{51},\overline{1744},\overline{100},\overline{-57}) \mapsto (\overline{17}, \overline{17}, \overline{51}, \overline{17}, \overline{100},\overline{100}\} $$ So there are three distinct elements in your list: $\overline{100},\overline{17},$ and $\overline{51}$.

I'm not entirely sure by what is meant with the statement "it'll be quite tedious to check for every pair", as we don't really need to consider a pair-by-pair comparison. Feel free to expand on this and I'll try to address it.

Bill Dubuque
  • 272,048
Theo C.
  • 1,282
  • 1
    You want $,a\bmod 157 = $ the remainder left after division by $157$, which is not "modular division" (that means something different). Also $,a\equiv b\mod n$ should be $,a\equiv b\pmod{n}\ $ By "checking every pair" OP probably means $,\bar a = \bar b\iff 157\mid a-b\ \ $ – Bill Dubuque Feb 27 '19 at 16:50
0

$-768 \equiv -611 \equiv 17 \pmod {157}$

For each of the above, we can find members of the equivalency class in $\{0,\cdots, 156\}$

And then decide if they are different or not.

Doug M
  • 57,877
0

Just apply the definitions. Is it true that $\overline{17}=\overline{-768}$, i.e., is it true that $157\mid (17+768)$?

Yes, it is!

For most pairs we immediately see that it isn't without really computing, e.g., for $17$ and $51$. The definition in general is as follows: $\overline{n}\equiv \overline{m} \bmod 157$ if and only if $157\mid (n-m)$ in $\Bbb Z$.

Dietrich Burde
  • 130,978