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),
| Statement | Proof 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
| Property | Statement |
|---|---|
| Closure | |
| Associativity | ; same for |
| Commutativity | ; |
| Identities | for , for |
| Additive inverse | for : (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 .