Prime Factorisation, Modular Arithmetic and Simultaneous Congruences
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 time9 min
Executive summary
This chapter develops prime factorisation, modular arithmetic and simultaneous congruences 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
Let m ≥0 be fixed. Then integers a and b are congruent modulo m, denoted by a ≡b mod m, if m | (a −b).
Definition
A common divisor of integers a1, a2, . . . , an is an integer c with c | ai for all i; the largest of the common divisors, denoted by (a1, a2, . . . , an), is called the greatest common divisor. 1.21 (i) Show that if d is the greatest common divisor of a1, a2, . . . , an, then d = tiai, where ti is in Z for 1 ≤i ≤n. (ii) Prove that if c is a common divisor of a1, a2, . . . , an, then c | d. 1.22 (i) Show that (a, b, c), the gcd of a, b, c, is equal to (a, (b, c)). (ii) Compute (120, 168, 328). 1.23 A integer right-triangle triples is an ordered triple (a, b, c) of positive integers for which a2 + b2 = c2; it is called primitive if gcd (a, b, c) = 1. (i) If q > p are positive integers, prove that (q2 −p2, 2qp, q2 + p2) is a integer right-triangle triples. [One can prove that every primitive integer right-triangle triples (a, b, c) is of this type.] (ii) Show that the integer right-triangle triples (9, 12, 15) (which is not primitive) is not of the type given in part (i). (iii) Using a calculator that can find square roots but that can display only 8 digits, prove that (19597501, 28397460, 34503301) is a integer right-triangle triples by finding q and p.
Principal results and structural facts
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.
Key result
A positive integer a is divisible by 3 (or by 9) if and only if the sum of its (decimal) digits is divisible by 3 (or by 9).
Key result
If p is a prime, then a p ≡a mod p for every a in Z. More generally, for every integer k ≥1, a pk ≡a mod p.
Key result
Let p be a prime and let n be a positive integer. If m ≥0 and if is the sum of the p-adic digits of m, then nm ≡n mod p.
Key result
If (a, m) = 1, then, for every integer b, the congruence ax ≡b mod m can be solved for x; in fact, x = sb, where sa ≡1 mod m is one solution. Moreover, any two solutions are congruent mod m.
Key result
If p is a prime and a is not divisible by p, then the congruence ax ≡b mod p is always solvable.
Key result
If m and m′ are relatively prime, then the two congruences x ≡b mod m x ≡b′ mod m′ have a common solution, and any two solutions are congruent mod mm′.
Key result
Every complex number z has a factorization z = r(cos θ + i sin θ), where r = |z| ≥0 and 0 ≤θ < 2π.
Source-grounded examples
Worked source example
(i) Prove that if a is in Z, then a2 ≡0, 1, or 4 mod 8. If a is an integer, then a ≡r mod 8, where 0 ≤r ≤7; moreover, by Proposition 1.20(iii), a2 ≡r2 mod 8, and so it suffices to look at the squares of the remainders. r r2 r2 mod 8 Table 1.1. (ii) Prove that n = 1003456789 is not a perfect square. Since 1000 = 8 · 125, we have 1000 ≡0 mod 8, and so n = 1003456789 = 1003456 · 1000 + 789 ≡789 mod 8. Dividing 789 by 8 leaves remainder 5; that is, n ≡5 mod 8. Were n a perfect square, then n ≡0, 1, or 4 mod 8. (iii) If m and n are positive integers, are there any perfect squares of the form 3m +3n +1? Again, let us look at remainders mod 8. Now 32 = 9 ≡1 mod 8, and so we can evaluate 3m mod 8 as follows: If m = 2k, then 3m = 32k = 9k ≡1 mod 8; if m = 2k + 1, then 3m = 32k+1 = 9k · 3 ≡3 mod 8. Thus, 3m ≡ 1 mod 8 if m is even; 3 mod 8 if m is odd. Replacing numbers by their remainders after dividing by 8, we have the following possibilities for the remainder of 3m + 3n + 1, depending on the parities of m and n: 3 + 1 + 1 ≡5 mod 8 3 + 3 + 1 ≡7 mod 8 1 + 1 + 1 ≡3 mod 8 1 + 3 + 1 ≡5 mod 8. Some Number Theory In no case is the remainder 0, 1, or 4, and so no number of the form 3m + 3n + 1 can be a perfect square, by part (i). ◀
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 prime factorisation, modular arithmetic and simultaneous congruences?
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.
