- #1

AndersHermansson

- 61

- 0

a = b(mod n)

Can anyone explain the modulus operator and congruence to me?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter AndersHermansson
- Start date

- #1

AndersHermansson

- 61

- 0

a = b(mod n)

Can anyone explain the modulus operator and congruence to me?

- #2

KLscilevothma

- 322

- 0

1= 0 χ 5 + 1

2= 0 χ 5 + 2

3= 0 χ 5 + 3

4= 0 χ 5 + 4

5= 1 χ 5 + 0

6= 1 χ 5 + 1

.

.

.

We observe that the remainder left when any integer is divided by 5 is one of the five integers 0, 1, 2, 3, 4. We say that two integers a and b are "congruent modulo 5" if they leave the same remainder on division by 5. Thus 2, 7, 22, -3, -8, etc are all congurent modulo 5 since they leave the remainder 2. In general, we say that two integers a and b are congrent modulo d, where d is a fixed integer, if a and b leave the same remainder on division by d. For example, 15 and 1 are congruent modulo 7. We can write 15 ≡ 1 (mod 7)

Let a and b be integers and let n be a positive integer. We say a is congruent to b modulo n , written

a ≡ b (mod n)

In fact "a ≡ b (mod n)" and "a=b+nd (where d is an integer)" are equilvalent.

Here are more examples

2003 ≡ 3 (mod 1000)

1985 ≡ 85 (mod 100)

1985 ≡ 985 (mod 1000)

121 ≡ 0 (mod 11)

953 ≡ 4 (mod 13)

Here are some properties of congruences. For all integers a, b and c, we have

1) a ≡ a (mod n)

2) a ≡ b (mod n) if and only if b≡ a (mod n)

3) if a ≡ b (mod n) and b ≡ c (mod n), then a≡ c (mod n)

4) n | a if and only of a ≡ 0 (mod n)

5) If a ≡ b (mod n) and x is a natural number, then a

- #3

AndersHermansson

- 61

- 0

Thanks alot, that really helped!

Share:

- Last Post

- Replies
- 7

- Views
- 313

- Replies
- 5

- Views
- 386

- Replies
- 2

- Views
- 466

- Replies
- 9

- Views
- 392

- Last Post

- Replies
- 3

- Views
- 463

- Last Post

- Replies
- 1

- Views
- 550

- Last Post

- Replies
- 3

- Views
- 486

- Last Post

- Replies
- 5

- Views
- 1K

- Replies
- 4

- Views
- 2K

- Replies
- 15

- Views
- 770