Hello,

Your two questions are one and the same. The expression (read: "a is congruent to b mod n") by definition means thata-b is a multiple of nor equivalentlyn divides a-b, written respectively as and . This may be hard to remember; it's probably easier to think of it this way:a and b have the same (non-negative) remainder when divided by n. When we specify non-negative remainder, we want the integer in [0,n), also called thecommon residue. Using the common residue can keep the numbers smaller, making our calculations easier.

You can verify that 71 is the remainder when 16243 is divided by 622.

Formally, we can write

No matter whether we start with 16243, or 71, or 71+622, or 71+2*622, we will get the same result after applying the steps for modular exponentiation, so we might as well choose the smallest.

Also, you can use \cdot in LaTeX for multiplication, it looks like .

Hope this helps.