Mathematical Induction, Division and Integer Structure
This topic establishes the proof language and structural vocabulary that later algebra depends on. Treat definitions as precise contracts: each hypothesis controls what operations or conclusions are permitted. This page consolidates the relevant material from the supplied algebra source into a stand-alone handbook chapter.
Learning pathFoundations of Abstract Algebra
LevelAdvanced
FormatHandbook guide
Read time10 min
Executive summary
This chapter develops mathematical induction, division and integer structure as part of a connected advanced-algebra learning sequence. The emphasis is on definitions, hypotheses, structural results and repeatable methods rather than historical narrative.
The source material is theorem-rich. Accordingly, the handbook presentation separates vocabulary from results and then adds a verification workflow so that each statement can be applied safely. Mathematical examples in the source are treated as examples, not as universal rules.
Problem-solving workflow
State the underlying set, number system or relation precisely.
Write the defining conditions before manipulating symbols.
Reduce the problem to a canonical form such as a remainder, factorisation, equivalence class or function equation.
Apply only results whose hypotheses have been checked explicitly.
Separate existence from uniqueness; prove both when a construction claims a unique answer.
Verify the result against the original definition, including boundary and degenerate cases.
Core definitions
Definition
A natural number p is prime if p ≥2 and there is no factorization p = ab, where a < p and b < p are natural numbers. 1This property is usually called the well-ordering principle.
Definition
If a and b are integers with a ̸= 0, then the integers q and r occurring in the division algorithm are called the quotient and the remainder after dividing b by a. Warning! The division algorithm makes sense, in particular, when b is negative. A careless person may assume that b and −b leave the same remainder after dividing by a, and this is usually false. For example, let us divide 60 and −60 by 7. 60 = 7 · 8 + 4 and −60 = 7 · (−9) + 3 Thus, the remainders after dividing 60 and −60 by 7 are different.
Definition
If a and b are integers, then a is a divisor of b if there is an integer d with b = ad. We also say that a divides b or that b is a multiple of a, and we denote this by a | b. There is going to be a shift in viewpoint. When we first learned long division, we emphasized the quotient q; the remainder r was merely the fragment left over. Here, we are interested in whether or not a given number b is a multiple of a number a, but we are less interested in which multiple it may be. Hence, from now on, we will emphasize the remainder. Thus, a | b if and only if b has remainder r = 0 after dividing by a.
Definition
A common divisor of integers a and b is an integer c with c | a and c | b. The greatest common divisoror gcd of a and b, denoted by (a, b), is defined by (a, b) = 0 if a = 0 = b the largest common divisor of a and b otherwise.
Definition
A common multiple of integers a and b is an integer c with a | c and b | c. The least common multiple or lcm of a and b, denoted by [a, b], is defined by [a, b] = 0 if a = 0 = b the smallest positive common multiple of a and b otherwise.
Definition
Let m ≥0 be fixed. Then integers a and b are congruent modulo m, denoted by a ≡b mod m, if m | (a −b).
Principal results and structural facts
Key result
Let S(n) be a family of statements, one for each integer n ≥m, where m is some fixed integer. If (i) S(m) is true, and (ii) S(n) is true implies S(n + 1) is true, then S(n) is true for all integers n ≥m.
Key result
Let S(n) be a family of statements, one for each integer n ≥m, where m is some fixed integer. If (i) S(m) is true, and (ii) if S(k) is true for all k with m ≤k < n, then S(n) is itself true, then S(n) is true for all integers n ≥m.
Key result
Given integers a and b with a ̸= 0, there exist unique integers q and r with b = qa + r and 0 ≤r < |a|.
Key result
If a and b are integers, then (a, b) = d is a linear combination of a and b; that is, there are integers s and t with d = sa + tb.
Key result
Let a and b be integers. A nonnegative common divisor d is their gcd if and only if c | d for every common divisor c.
Key result
Let I be a subset of Z such that (i) 0 ∈I; (ii) if a, b ∈I, then a −b ∈I; (iii) if a ∈I and q ∈Z, then qa ∈I. Then there is a natural number d ∈I with I consisting precisely of all the multiples of d.
Key result
If p is a prime and p | ab, then p | a or p | b. More generally, if a prime p divides a product a1a2 · · · an, then it must divide at least one of the factors ai.
Key result
(i) If a and b are integers, then a and b are relatively prime if and only if there are integers s and t with 1 = sa + tb. (ii) If d = (a, b), where a and b are not both 0, then (a/d, b/d) = 1.
Key result
Let a and b be positive integers. There is an algorithm that finds the gcd, d = (a, b), and there is an algorithm that finds a pair of integers s and t with d = sa + tb. Remark. More details can be found in Theorem 3.40, where this result is proved for polynomials.
Key result
If b ≥2 is an integer, then every positive integer m has an expression in base b: There are integers di with 0 ≤di < b such that m = dkbk + dk−1bk−1 + · · · + d0; moreover, this expression is unique if dk ̸= 0.
Key result
Assume that an integer a ≥2 has factorizations a = p1 · · · pm and a = q1 · · · qn, where the p’s and q’s are primes. Then n = m and the q’s may be reindexed so that qi = pi for all i. Hence, there are unique distinct primes pi and unique integers ei > 0 with a = pe1 1 · · · pen n .
Key result
If m ≥0 is a fixed integer, then for all integers a, b, c, (i) a ≡a mod m; (ii) if a ≡b mod m, then b ≡a mod m; (iii) if a ≡b mod m and b ≡c mod m, then a ≡c mod m. Remark. (i) says that congruence is reflexive, (ii) says it is symmetric, and (iii) says it is transitive. ◀
Key result
Let m ≥0 be a fixed integer. (i) If a = qm + r, then a ≡r mod m. (ii) If 0 ≤r′ < r < m, then r ̸≡r′ mod m; that is, r and r′ are not congruent mod m. (iii) a ≡b mod m if and only if a and b leave the same remainder after dividing by m. (iv) If m ≥2, each integer a is congruent mod m to exactly one of 0, 1, . . . , m −1.
Key result
Let m ≥0 be a fixed integer. (i) If a ≡a′ mod m and b ≡b′ mod m, then a + b ≡a′ + b′ mod m. (ii) If a ≡a′ mod m and b ≡b′ mod m, then ab ≡a′b′ mod m. (iii) If a ≡b mod m, then an ≡bn mod m for all n ≥1.
How to reason with these results
Most advanced-algebra problems become manageable when the representation is separated from the invariant structure. Begin with the definition, then decide whether the problem is asking for an elementwise calculation, a statement about a morphism, or a classification up to isomorphism. That choice determines the correct proof language.
When a theorem gives a structural conclusion, do not jump directly to the conclusion. Write the hypotheses next to the object you are studying and check them one by one. If a hypothesis fails, either strengthen the object, pass to a quotient or localisation where the theorem applies, or use a more elementary argument.
For computational work, record each transformation together with the equivalence relation it preserves. In algebra, row operations, similarity, quotienting, localisation and isomorphism preserve different kinds of information. A calculation is useful only when the preserved structure matches the question.
Common failure modes
Failure mode
Control
Using an operation before checking that it is well-defined.
Return to the definition or theorem hypotheses and verify the missing condition before continuing.
Treating an example as a proof of a universal claim.
Return to the definition or theorem hypotheses and verify the missing condition before continuing.
Ignoring zero, empty-set or boundary cases.
Return to the definition or theorem hypotheses and verify the missing condition before continuing.
Confusing equality of representations with equality of the underlying mathematical object.
Return to the definition or theorem hypotheses and verify the missing condition before continuing.
Using induction without a valid base case or without proving the inductive implication.
Return to the definition or theorem hypotheses and verify the missing condition before continuing.
Verification checklist
The ambient set, ring, field, group, module or category has been stated.
Every operation and map used is well-defined in that setting.
The hypotheses of each structural result have been checked before use.
Representatives, coordinates or generators have not been confused with the underlying object.
Existence and uniqueness have been separated where both matter.
The final result has been checked against the original defining relation or universal property.
Quick questions
What should I identify first in a problem about mathematical induction, division and integer structure?
Start with the ambient algebraic structure, its operation or maps, and the exact hypotheses. Most incorrect solutions begin by using a familiar rule that is not valid in the stated structure.
How should definitions be used in proofs?
Expand the definition at the point where it becomes useful. Definitions are not background prose; they are the conditions that determine what must be proved and which implications are available.
When is a structural theorem safer than direct calculation?
Use a structural theorem when its hypotheses are satisfied and the calculation would otherwise depend on arbitrary coordinates, representatives or generators. The theorem usually identifies an invariant that survives those choices.
How can a final answer be checked?
Substitute the result back into the defining relation, verify any required closure or map property, and check edge cases such as zero, the identity, the empty object or degenerate quotients where relevant.
Connections within the handbook
Source basis: supplied advanced algebra reference. Source-identifying authorship, publisher information, acknowledgements and biographical material are intentionally omitted. Mathematical terminology and results are retained in handbook form.
