Modular Arithmetic

Definition 5

?Let n ∈ N and let a,b ∈ Z. We say that a is congruent to b modulo n?

if n|(a?b).?

We write this as a ≡ b (mod n).

Theorem 2

Let n∈N and let a,b∈Z. TFAE：（"The Following Are Equivalent"）

1. a≡b(modn).
2. a and b leave the same remainder when divided by n.?

3. a=b+kn?for some?k∈Z.

Theorem 3

Let a1,a2,b1,b2 ∈ Z, and let n ∈ N.?

Suppose, further, that a1 ≡ a2 (mod?n) and b1 ≡b2 (mod?n). Then

1. a1 + b1 ≡ a2 + b2 (mod n).

2. a1b1 ≡ a2b2 (mod n).

3. a1 ? b1 ≡ a2 ? b2 (mod n).

Ok, this is pretty great, but it’s missing one operation! How do we perform division modulo n? Or even, can we?

As a reminder of how we defined division way back when, we had the following definition for the number 1/n?:

Definition 8

Let n ∈ N and let a ∈ Z. We say that u is?

if?au ≡ 1 (mod n).

So, in Example 8, we showed that 5 is a multiplicative inverse for 3 modulo 7.?

Let’s take a look at another example:

So sometimes inverses exist, and sometimes they don’t.?

There are common?factors between??6? and (2, 3, 4,6).

There are common?factors between? 7?and 7.

There are common?factors between? 8?and (2,4,6,8).

Examining the above 3 examples, you might notice a pattern: multiplicative inverses do not exist anytime the number we are interested in shares a factor with the modulus. This, in general, is the feature we are looking for.

Theorem 4.?

Let n ∈ N and a ∈ Z. Then a has a multiplicative inverse modulo n?

if and only if a ⊥ n.

example:

1?⊥ 6

5?⊥ 6

1?⊥ 7

2?⊥ 7

3?⊥ 7

4?⊥ 7

5?⊥ 7

6?⊥ 7

1?⊥ 8

3?⊥ 8

5?⊥ 8

7 ⊥ 8