Linear Diophantine Equation

# Congruence and Modular Arithmetic

Invented/Discovered by Carl Friedrich Gauss.

Let be a fixed positive integer. For integers and , we say that is congruent to modulo , and write

when . For integers and such that , we write . We refer to as congruence, and as its modulus.

### Elementary Properties of Congruence

One convenient aspect of congruence is that it behaves a lot like equality. For example, equality is an equivalence relation on the integers. This means that it has the following three properties:

1. Reflexivity: For all integers , .
2. Symmetry: For all integers and , .
3. Transitivity: For all integers , and , .

Equivalence relation Let be any set and let be any binary relation on . Then is said to be an equivalence relation if “same thing as above”

#### Some Theorems

Congruence is an Equivalence Relation (CER) For all integers , and , we have

1. .
2. If , then .
3. If and ,then .

Proposition 2 For all integers , , and , if and , then

1. ,
2. ,

Congruence Add and Multiply (CAM) For all positive integers , for all integers , and , if for all , then

1. .

Congruence Power (CP) For all positive integers and integers and , if , then .

Congruence Divide (CD) For all integers , and , if and , then .

### Congruence and Remainders

Congruent Iff Same Remainder (CISR) For all integers and , if and only if and have the same remainder when divided by .

Congruent To Remainder (CTR) For all integers and with , if and only if has remainder when divided by .

### Linear Congruence

A relation of the form is called a linear congruence in the variable . A solution to such a linear congruence is an integer such that

Linear Congruence Theorem (LCT) For all integers and , with a non-zero, the linear congruence has a solution if and only if , where . Moreover, if is one particular solution to this congruence, then the set of all solutions is given by

or, equivalently,

### Non-Linear Congruence#gap-in-knowledge

For higher powers, we can solve a congruence relation modulo by checking all values, which works quite well when is small. (so essentially brute forcing)

### Congruence Classes and Modular Arithmetic

The congruence class modulo of the integer is the set of integers

We define to be the set of congruence classes
and we define two operations on , addition and multiplication, as follows:

When we apply these operations on the set , we are doing what is known as modular arithmetic.

### Inverses in (INV )

I really struggled with this for MATH135. See MATH135. See Modular Multiplicative Inverse Inverse defintiion

Let be an integer with . The element in has a multiplicative inverse if and only if . Moreover, when , the multiplicative inverse is unique.

### Inverses in (INV )

For all prime numbers and non-zero elements [a] in , the multiplicative inverse exists and is unique.

### Fermat’s Little Theorem (FT)

For all prime numbers and integers not divisible by , we have

### Chinese Remainder Theorem (CRT)

For all integers and , and positive integers and , if , then the simultaneous linear congruences

have a unique solution modulo . Thus, if is one particular solution, then the solutions are given by the set of all integers such that

### Generalized Chinese Remainder Theorem (GCRT)

For all positive integers and , and integers , if for all , then the simultaneous congruences

have a unique solution modulo . Thus, if is one particular solution, then the solutions are given by the set of all integers such that

### Splitting Modulus Theorem (SMT)

For all integers and positive integers and , if , then the simultaneous congruences

have exactly the same solutions as the single congruence .