Congruences

Introduction

Two numbers are congruent modulo a given number if they give the same remainder when divided by that number. x mod n = remainder of x when divide by n

Let a,a’ be integers and b be a positive integer. a is congruent to a’ modulo b

a = a’ (mod b) ) iff b | (a – a’)

Equivalently

a mod b = a’ mod b

a = a’ (mod b) means that a and a’ have the same remainder when dividing by b.

Use

Example

3 = 3 (mod 17)

Example

172 = 177 (mod 5)

Example

-13 = 13 (mod n)