Find the reduction $ - 23 \pmod {67} $

Question

I do not understand what the question is asking me to do?

Because if I do $-23 \pmod {67} = 44$? I am not sure if it is correct?

Answer 1

Yes, that is correct.

You added a multiple of $67$ such that the result is in $[0,67)$, which is what taking modulus means.

(Note that most programming languages have an integer remainder operation that works like modulus for positive arguments, but differs when there are negative numbers involved. That is not what you want here).

Answer 2

$-23 \equiv 44 \pmod{67}$ iff $67 |\left( 44 - (-23)\right)$ and $44 -(- 23) = 67$ so the numbers are indeed equivalent modulo $67$.

Answer 3

Oh, never mind. After googling I've found https://eprint.iacr.org/2014/755.pdf which seem to claim "the modular reduction" of $X \mod Y$ will by the remainder when $X$ is divided by $Y$. And it is assumed that the remainder will be non-negative and less than $Y$.

So "the reduction" $-23 \mod 67$ will be the integer $k$ so that $-23 \equiv k \mod 67$ and $0 \le k < 67$.

That number, as you figured out, is $44$.

However the phrase "the reduction modulo Y" is not one that is familiar to me. (Although the concept certainly is).

======

That is probably what they want. But it is unclear what the mean be "the reduction".

Technically speaking $-23 \mod 67$ is not actually equal the integer $44$ but instead $-23$ and $44$ are equivalent to each other under the equivalence relation known as "modulo 67". ($a$ is equivalent to $b$ modulo 67 if and only if $a = b + 67*k$ for some or any integer $k$.

So $44 \equiv -23 \mod 67$. But there is no reason that $44$ is any better an answer than $-23$ or $111$ or $-90$ or $5538$ or ....

Oh...!

Maybe. "The Reduction" means the equivalence class of $-23 \mod 67$.

An "equivalence class modulo 67" is the set of the all integers so that all the elements of the set are equivalent to each other modulo $67$. The equivalence class of $-23 \mod 67$ will be all the integers, $k$ so that $k \equiv -23 \mod 67$.

This is written as $[-23] = \{z\in \mathbb Z| z \equiv -23 \mod 67\}$

$ = \{z \in \mathbb Z| z = -23 + 67*k; k \in \mathbb Z\}$

$=\{67*k - 23| k \in \mathbb Z\}$

$= \{..., -90, -23, 44, 111, 178, .....\}$[$*$]

Maybe that was the answer they wanted.

But you should go to the text and look up their definition of "the reduction".

=======

This is technically what is meant by $-23 \equiv 44 \mod 67$. It actually means $-23$ and $44$ are both in the same equivalence class modulo $67$.