Cannot understand congruence relation from RSA

663 Views Asked by At

Currently I'm reading about RSA and have a trouble understanding the following formula: $$e \cdot d \equiv 1 (\mod (p-1)(q-1)) $$ From Wikipedia I know that for a given positive integer $n$, two integer $a$ and $b$ are called congruent modulo $n$ if $a$ and $b$ have the same remainder when divided by $n$. But! If you take a reminder of $1$ divided but any $n>1$, the remainder will be $1$. That is, we can simplify he first formula to be: $$(e \cdot d) \mod ((p-1)(q-1)) = 1 $$ Are these formulas equivalent?

1

There are 1 best solutions below

2
On BEST ANSWER

$a \equiv b\pmod n\,$ means $\,n\mid a-b,\ $ i.e. $\,a-b = nk,\,$ for some integer $k$.

$(a\bmod n) = b\ $ means the above plus $\,0\le b < n,\,$ i.e. $\,b\,$ is the least natural $\equiv a\pmod n$ or, equivalently, $\,b\,$ is the remainder left when dividing $\,a\,$ by $\,n.\,$

In your case $\,b = 1 < n\,$ is always true so they are always equivalent. But for larger $\,b\,$ this is not true, e.g. $\, 0 \equiv 2\pmod 2\,$ but $\,(0\bmod 2)\ne 2.$

Congruence relations are often more convenient for theory, whereas normal forms (such as produced by the mod operator) are often more convenient for computation. But it is best to be proficient with the use of both, and to be able to quickly convert back-and-forth between the two as need be.