unexplained modulo, rs ≡ 1 (mod m) where r = 3, s= 59 and m = 176

Question

I'm trying to work through the math behind public key encryption, I'm a computer programmer, but not a mathematician. I came across this wonderful example, but I'm confused about the use of (mod x) my understanding of modulus is that it is the remainder after devision. e.g. 5 % 2 = 1. but this is odd:

rs ≡ 1 (mod m) where r = 3, s = 59 and m = 176

how can s = 59 my understanding is that 1 mod 176 would be 1.

Answer 1

You should know that $a \equiv b (\text{mod $m$)}$ means that $a-b$ is divisible by $m$.

For this modulo, you should note that $0$ is divisible by all positive natural numbers (result would be $0$), so $1$ when divided by any positive natural numbers (except $1$) will have $1$ as a remainder $\Rightarrow 1 \equiv 1 (\text{mod $m$)}$.

For this problem, $177$ when divided by $176$ will have a remainder of $1$, or $177-1$ is divisible by $176$ $\Rightarrow 3 \times 59 \equiv 1 (\text{mod $176$)}$.

Answer 2

Note that $rs = 3(59)= 177 = 176+1 \equiv 1 \pmod{176}$.

To find $s$, we usually use euclidean algorithm.

$$176 = 58(3)+2$$ $$3 = 2(1) + 1$$

Hence

\begin{align} 1 &= 3-2(1) \\ &=3-(176-58(3)) \\ &= 59(3)-176 \end{align}

Hence $$1 \equiv 59(3) \pmod{176}$$