1. Divisibility

Definition 1

For integers with : (” divides ”) iff there is an integer with .

Equivalent phrasings: is a divisor / factor of ; is divisible by ; is a multiple of .
Write when does not divide .

⚠️ is a statement (true/false). is a number (may or may not be an integer).

Always true for every : , , , . Also .

Examples

  • (7/3 is not an integer); (12/3 = 4).
  • Number of positive integers divisible by : (count the with ).

Theorem 1 (properties),

StatementProof idea
(i) and
(ii) for all
(iii) and (transitivity)

Corollary 1 (linear combinations)

If and , then for all integers .
Proof: .

A linear combination of is any with integer coefficients. This corollary is used later for Euclid’s algorithm (4.3).

Lemma 1

For : .


2. The Division Algorithm

Theorem 2

Let and . There is a unique pair with

  • = dividend, = divisor, = quotient, = remainder.
  • Notation: , .
  • ⚠️ The remainder is never negative.

Examples

  • .
  • (not ).

3. Congruence

Definition 3

For : iff . is the modulus. Otherwise .

⚠️ is a relation on ; is a function value. Different concepts, closely related:

Theorem 3

(same remainder).
Proof idea: write , , so with . Then forces , and conversely.

Example: since ; since .

Theorem 4

for some integer .

The set of all integers congruent to mod is the congruence class of modulo .

Theorem 5 — congruences survive and

If and , then

Proof: , ⇒ and .

Example: , ⇒ and .

⚠️ You cannot always divide. does not imply in general (e.g. but ). Division by is allowed when (see 4.3, Theorem 7).

Corollary 2 — reduce first, then compute



4. Arithmetic Modulo

with

Example: ; .

Properties of and

PropertyStatement
Closure
Associativity; same for
Commutativity;
Identities for , for
Additive inversefor : (since ); is its own inverse
Distributivity

⚠️ Multiplicative inverses do not always exist mod — e.g. 2 has no inverse mod 6.

Remarks

  • is a commutative group; is a commutative ring (like itself).
  • Later sections just write and when working in .