0

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?

Henno Brandsma
  • 242,131
Angjelin Malaj
  • 1
  • 1
    That seems like what they are asking but it is unclear. What exactly is the whole question. If that is the whole question, then what according to your text book is the precise definition of "the reduction". – fleablood Sep 06 '17 at 18:19

3 Answers3

0

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

hmakholm left over Monica
  • 286,031
  • Hmm, out of curiosity, how common is the phrase "the reduction mod k"? I somehow never run across it. What is the terminology of $x \equiv a \mod k$ and $x \in [\lceil -\frac k2 \rceil, \lceil \frac k2 \rceil]$? – fleablood Sep 06 '17 at 19:05
  • @fleablood: I'm not sure I have seen the phrase "reduction modulo $k$" about the result -- but I have certainly seen it describing the process of finding that result. – hmakholm left over Monica Sep 06 '17 at 20:22
  • Glad it's not just me then. It seems me there are asking for 44, but I couldn't really tell be the question. – fleablood Sep 06 '17 at 22:51
0

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

Henno Brandsma
  • 242,131
0

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

fleablood
  • 124,253