The different elements of $\mathbb{Z}/157\mathbb{Z}$

Question

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?

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

Answer 2

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

Answer 3

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