Number theory studies the structure of integers: divisibility, primes, factors, remainders and the equations they satisfy. Its gold standard is an answer supported by a valid method and a reason that survives a change of example. Knowing that a calculation worked once is useful; understanding why it works is what makes the knowledge transferable.
A question such as “When will these two cycles coincide?” can lead to common multiples. “Can these quantities be split into identical groups?” can lead to common divisors. “Why can I cancel this number here but not there?” can lead into modular inverses. Elementary questions open a route into substantial mathematics.
This root connects Mathematics with the existing guides on primes, factors, HCF and LCM, then develops the bridge to Discrete Mathematics, Logic and Cryptography. The specialist library groups those routes by the question a reader needs to resolve.
The explanations begin with ordinary integers and make the conditions explicit. You do not need to know advanced algebra to follow the first chapters. When a later result requires a new idea, the worked example introduces it before asking you to use it.
EDUKATE · THE GOLD STANDARD
Find your next learning step
Choose the starting point closest to your question: integers and factors, reliable algorithms, remainders, proof, or further learning. The worked examples are teaching examples. Each method keeps its assumptions visible so you can see why it works and when it applies.
Full chapter index · Diagnose the uncertainty · Specialist reading library · Mathematics guide
Full chapter index
Understand integers and factors · Chapters 1–4
Find structure with algorithms · Chapters 5–8
Reason with congruences · Chapters 9–13
Prove and test claims · Chapters 14–17
Explore and transfer · Chapters 18–22
CHAPTER 1 OF 22 · Understand integers and factors
1. State which numbers the question allows
An integer is a whole-valued number such as −3, 0 or 12. A positive integer is greater than zero. A nonnegative integer may be zero. These distinctions are small in wording and large in consequences, because a solution allowed in one domain may be excluded in another.
If a question asks for a number of boxes, negative values are normally inappropriate to that model. If it asks whether an integer equation has a solution, negative integers may be essential. Write the permitted domain before solving rather than rejecting an inconvenient answer at the end.
Conventions also matter. Some texts include zero among the natural numbers, while others begin at one. An article can avoid confusion by stating positive or nonnegative when that is what it means. A familiar symbol does not remove the need to define the intended set.
The guide Is Zero an Even Number? provides a useful starting point. Evenness is a structural property: an integer is even when it equals twice an integer. Since 0 = 2 × 0, zero meets that definition. A definition can resolve a question more reliably than a feeling about what a number looks like.
CHAPTER 2 OF 22 · Understand integers and factors
2. Divisibility turns a calculation into a relationship
For integers a and b with a nonzero, saying that a divides b means that b = ak for some integer k. The number k is a whole-valued multiplier. This is stronger than saying that a calculator can produce a decimal quotient.
For example, 6 divides 42 because 42 = 6 × 7. But 6 does not divide 43, because no integer multiplier gives 43. The notation 6 | 42 records the divisibility relationship. It does not mean an ordinary fraction or a division sign waiting for an answer.
A factor and a multiple describe opposite directions of the same relationship. If 6 is a factor of 42, then 42 is a multiple of 6. The guide Can a Number Be Both a Factor and a Multiple? explores why the relationship must name the other number.
Zero needs careful language. Every nonzero integer divides zero because zero is its product with zero. Dividing by zero remains undefined in ordinary arithmetic. These statements concern different operations, so they do not contradict one another. Read Zero as a Multiple alongside the precise definitions.
CHAPTER 3 OF 22 · Understand integers and factors
3. Primes require exactly the right definition
A prime is a positive integer greater than one with exactly two positive divisors: one and itself. A composite positive integer greater than one has a nontrivial factorisation. The restrictions in that definition do work; they should not disappear when a shortcut is memorised.
The number 1 has only one positive divisor, so it is not prime. It is also not composite under these definitions. The guides Why Is 1 Not a Prime Number? and Can a Number Be Both Prime and Composite? develop those boundaries.
The only even prime is 2. Any even integer greater than 2 can be written as 2k with k greater than one, giving a factorisation into smaller positive integers. The conclusion follows from evenness and the prime definition, rather than from inspecting a long list.
To test a positive integer n greater than one by trial division, it is enough to check possible prime divisors up to its square root. If n = ab is composite with a and b positive and greater than one, they cannot both exceed √n. Otherwise their product would exceed n. That short argument explains the stopping rule.
CHAPTER 4 OF 22 · Understand integers and factors
4. Prime factorisation exposes the multiplicative structure
Every integer greater than one has a factorisation into primes, unique apart from their order. This is the fundamental theorem of arithmetic. The statement is not that every way of writing a product looks identical; it is that continuing to prime factors leads to the same prime ingredients with the same multiplicities.
For example, 84 = 2 × 42 = 2 × 2 × 21 = 2² × 3 × 7. Beginning with 84 = 6 × 14 eventually produces the same prime factorisation. A factor tree is a way to organise the work, while uniqueness is the reason different valid routes agree.
Check that the final factors are prime and that multiplying them reconstructs the original number. Stopping at 84 = 4 × 21 is a valid factorisation, but it is not yet a prime factorisation. The task determines which form counts as complete.
Prime exponents also encode useful information. A positive integer is a perfect square precisely when every exponent in its prime factorisation is even. Squaring doubles each exponent; conversely, even exponents can be halved to construct an integer square root. This connects a classification with an explanation rather than a visual guess.
CHAPTER 5 OF 22 · Find structure with algorithms
5. HCF and LCM solve different structural questions
The highest common factor, also called the greatest common divisor or gcd, is the greatest positive integer dividing both numbers. The lowest common multiple is the least positive integer that is a multiple of both. For this chapter, take both original numbers to be positive.
With 12 = 2² × 3 and 18 = 2 × 3², the gcd uses each common prime to the smaller exponent: 2 × 3 = 6. The lcm uses the larger exponent needed to include both numbers: 2² × 3² = 36. One describes a shared divisor; the other describes a shared multiple.
Why the exponent rules? A common divisor cannot contain more copies of a prime than either original number. A common multiple must contain at least as many copies as each original number requires. The rules follow from those requirements and prime factorisation.
For positive a and b, gcd(a,b) × lcm(a,b) = ab. Here 6 × 36 = 12 × 18 = 216. This is a useful check, but the meanings still determine which quantity a problem needs. Continue with HCF and LCM in Grouping and Repetition for the application route.
CHAPTER 6 OF 22 · Find structure with algorithms
6. The Euclidean algorithm preserves the common divisors
The Euclidean algorithm finds a gcd through division with remainder. Its key step is gcd(a,b) = gcd(b,r) when a = qb + r. A common divisor of a and b divides r = a − qb; a common divisor of b and r divides a = qb + r. The two pairs therefore have the same common divisors.
To find gcd(252,198), reduce the problem through the following exact divisions. The last nonzero remainder is 18, so the gcd is 18. The method avoids having to list every divisor or completely factor both original numbers.
| Division step | Equivalent next gcd question |
|---|---|
| 252 = 1 × 198 + 54 | gcd(198,54) |
| 198 = 3 × 54 + 36 | gcd(54,36) |
| 54 = 1 × 36 + 18 | gcd(36,18) |
| 36 = 2 × 18 + 0 | gcd = 18 |
Check the result in the original pair: 252 = 18 × 14 and 198 = 18 × 11. Since 14 and 11 are coprime, no larger common divisor has been missed. The algorithm is more than a recipe; the preserved relationship explains why the final result answers the original question.
CHAPTER 7 OF 22 · Find structure with algorithms
7. Integer combinations reveal why some equations have solutions
The extended Euclidean algorithm can express gcd(a,b) as ax + by for integers x and y. This is often called Bézout’s identity. For the preceding example, back-substitution gives 18 = 4 × 252 − 5 × 198. The coefficients can be negative because the statement concerns integers.
This provides a route into equations ax + by = c. For a and b not both zero, such an equation has integer solutions exactly when gcd(a,b) divides c. Any common divisor must divide the left side; Bézout’s identity supplies a solution when the right side is a multiple of the gcd.
The permitted domain remains essential. The equation 6x + 9y = 3 has an integer solution, x = −1 and y = 1. It has no solution with both x and y nonnegative integers: zero on both gives zero, while any positive contribution is at least 6.
A gcd test therefore settles integer solvability, not every practical interpretation involving counts or lengths. After finding an algebraic solution, return to the original conditions. A correct theorem can be misapplied when the domain quietly changes.
CHAPTER 8 OF 22 · Find structure with algorithms
8. Division with remainder needs a consistent convention
For an integer a and a positive integer m, division with remainder writes a = qm + r with integers q and r satisfying 0 ≤ r < m. The quotient and remainder are uniquely determined under those conditions. The remainder is not simply whatever is left after an arbitrary subtraction.
For example, 17 = 3 × 5 + 2, so its remainder on division by 5 is 2. For a negative example, −3 = (−1) × 5 + 2. Under this convention the remainder is again 2, rather than −3.
The convention makes comparison possible. All integers can be sorted by the same finite collection of remainders: 0, 1, 2, …, m − 1. Numbers in one class differ by multiples of m. This prepares the language of congruence.
Computer languages can differ in how remainder-like operators handle negative inputs. A programming result should be checked against the language’s definition before it is treated as this mathematical convention. The mathematical idea and a particular software operator need an explicit connection.
CHAPTER 9 OF 22 · Reason with congruences
9. Congruence preserves the remainder relationship
Write a ≡ b (mod m) when m divides a − b, with m positive. It means that a and b belong to the same remainder class modulo m. It does not mean that a and b are equal as ordinary integers.
Thus 17 ≡ 2 (mod 5), because their difference is 15. Also −3 ≡ 2 (mod 5), because their difference is −5. The modulus is part of the statement. Removing it changes the claim.
Addition, subtraction and multiplication respect congruence. For example, 17² ≡ 2² ≡ 4 (mod 5). Checking directly, 289 = 57 × 5 + 4. Replacing a number with a congruent representative can simplify a computation while preserving the remainder information.
The clock analogy helps with repetition, but the definition is the dependable foundation. When a problem moves beyond a familiar clock, ask whether the difference is a multiple of the modulus. That question works for negative integers, large powers and unfamiliar examples.
CHAPTER 10 OF 22 · Reason with congruences
10. Cancellation requires an invertible factor
Ordinary division cannot be transferred unchanged into modular arithmetic. From 2 × 1 ≡ 2 × 4 (mod 6), it would be wrong to cancel 2 and conclude 1 ≡ 4 (mod 6). The products differ by 6, but the proposed reduced pair differs by only 3.
A number a has a multiplicative inverse modulo m when there is an integer u with au ≡ 1 (mod m). For m greater than one, this happens exactly when gcd(a,m) = 1. Multiplying by that inverse justifies cancellation without changing the modulus.
Modulo 7, the inverse of 3 is 5 because 3 × 5 = 15 ≡ 1. To solve 3x ≡ 4 (mod 7), multiply by 5: x ≡ 20 ≡ 6. Checking, 3 × 6 = 18 ≡ 4 (mod 7).
Modulo 6, however, 2 has no inverse. Its products cannot be congruent to 1 because they are even. The right habit is to check the condition before cancelling. A familiar-looking symbolic move is valid only when the mathematical setting supports it.
Consider the simultaneous requirements x ≡ 2 (mod 3) and x ≡ 3 (mod 5). In one block of fifteen consecutive integers beginning at zero, candidates for the first requirement are 2, 5, 8, 11 and 14. Only 8 satisfies the second.
All solutions are x ≡ 8 (mod 15). Adding 15 preserves both remainders. Conversely, the difference between any two solutions is divisible by both 3 and 5, so it is divisible by 15 because these moduli are coprime.
This illustrates the Chinese remainder theorem: for pairwise coprime positive moduli, specified remainder classes combine into a unique class modulo their product. The word unique refers to that class, not to a single ordinary integer with no other solutions.
Without coprime moduli, compatibility must be examined. An integer cannot be even and also leave remainder 1 on division by 4. Other systems with non-coprime moduli can be compatible. The missing hypothesis does not mean every such system fails; it means the stated coprime version cannot be applied automatically.
CHAPTER 12 OF 22 · Reason with congruences
12. Use repeated squaring to control large powers
A large power does not always need to be expanded into an enormous integer. In modular arithmetic, reduce intermediate products while preserving the desired remainder. Repeated squaring organises this efficiently by building powers with exponents 1, 2, 4, 8 and so on.
Find the remainder of 7¹³ on division by 10. First, 7² ≡ 9 (mod 10). Squaring gives 7⁴ ≡ 9² ≡ 1, and then 7⁸ ≡ 1. Since 13 = 8 + 4 + 1, we have 7¹³ ≡ 1 × 1 × 7 ≡ 7.
The exponent decomposition explains which intermediate powers to multiply. It is not legitimate to add the remainders of the powers, because multiplying powers with the same base adds their exponents. Keep that operation visible in the working.
This is a useful connection between number theory and algorithms. The goal is to preserve the required information while avoiding unnecessary work. A short computation becomes trustworthy when its reductions and exponent rules can be checked.
CHAPTER 13 OF 22 · Reason with congruences
13. Cycles require both a period and a starting position
Two repeating events with periods 12 and 18 units coincide every 36 units if they begin together at time zero. The lcm gives the repeat interval for that shared starting arrangement. It does not automatically settle a problem in which the two events begin at different times.
If one cycle has an offset, write the timing conditions explicitly. A statement that an event occurs at times congruent to 2 modulo 3 is different from a statement that it occurs at multiples of 3. This is where remainder equations can express the actual model more faithfully.
The same distinction appears in grouping. A gcd may identify the largest equal group size that divides two quantities, but only when the problem really permits the proposed arrangement. If different item types must be mixed in fixed proportions, state that requirement too.
Useful applications keep the modelling assumptions visible: exact integer periods, agreed units, starting positions and the meaning of coincidence. An elegant calculation should answer the situation described. It should not quietly replace the situation with a simpler one.
CHAPTER 14 OF 22 · Prove and test claims
14. A general proof must reach every permitted case
Examples can reveal a pattern and suggest a conjecture. A proof establishes the claim through an argument covering its stated domain. The difference concerns the scope of the reasoning, not how many lines the explanation contains.
Consider the claim that the sum of two even integers is even. Write them as 2a and 2b for integers a and b. Their sum is 2(a + b). Since a + b is an integer, the sum is even. This covers every permitted pair, including negative integers and zero.
The proof identifies a representation, performs valid operations and returns to the definition. It does not depend on choosing large numbers or on testing many cases. A concise proof can be stronger than a page of unexplained examples.
Continue into Logic and How Mathematics Establishes Truth. A learner should be able to point to the step that makes the argument general. “It keeps happening” is an observation to investigate, rather than that step.
Suppose, for a contradiction, that all primes could be listed as p₁, p₂, …, pₖ. Form N = p₁p₂…pₖ + 1. This number is greater than one, so it has a prime divisor. Yet division by any prime in the proposed list leaves remainder one.
The prime divisor of N is therefore missing from the supposed complete list. That contradicts the assumption that the list contained every prime. Hence there cannot be only finitely many primes.
The argument does not require N itself to be prime. It only requires a prime divisor not on the list. That is an important boundary: product plus one is a way to defeat a proposed complete list, not a guarantee that the constructed number is always prime.
For a concrete check, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509. The constructed number is composite, but neither displayed factor belongs to the original list. The numerical example illustrates the distinction; the preceding general argument supplies the proof.
CHAPTER 16 OF 22 · Prove and test claims
16. Factor pairs explain why squares have an odd divisor count
Positive divisors of a positive integer n can be paired as d and n/d. For a non-square, the two members of each pair differ, so the divisor count is even. For a square, the divisor √n pairs with itself, producing one unpaired middle member in a list of distinct divisors.
Take 36. Its positive divisors are 1, 2, 3, 4, 6, 9, 12, 18 and 36. The pairs are 1 with 36, 2 with 18, 3 with 12 and 4 with 9, while 6 pairs with itself. There are nine distinct positive divisors.
The prime-exponent method confirms the count. Since 36 = 2² × 3², a divisor independently chooses an exponent of 0, 1 or 2 for each prime. This gives 3 × 3 = 9 possibilities. The counting method follows from the structure of the divisors.
Read Can a Square Number Have an Odd Number of Factors? for the specialist explanation. The useful connection is between pairing, prime factorisation and proof. The answer is more transferable when a learner can reconstruct it in two different ways.
CHAPTER 17 OF 22 · Prove and test claims
17. A counterexample can settle a universal claim
Consider the proposed statement that n² + n + 41 is prime for every nonnegative integer n. The values at n = 0, 1, 2 and 3 are 41, 43, 47 and 53. Those examples encourage investigation, but they do not establish the universal claim.
At n = 40, the expression equals 1600 + 40 + 41 = 1681 = 41². This value is composite. One permitted counterexample is enough to disprove the statement as written.
The response should be to revise the claim or investigate a more precise one, not to discard the counterexample because many earlier values worked. In mathematics, a universal statement includes every case in its stated domain.
Computation is valuable for exploration and for checking a finite collection of cases. Exhaustive checking can establish a genuinely finite claim when coverage and calculation are sound. The problem is presenting a partial search as a proof of an unbounded statement. State what was tested and what remains to be shown.
CHAPTER 18 OF 22 · Explore and transfer
18. Specialist library: connect the number-theory ecosystem
Definitions, primes and the structure of integers
Begin with Is Zero an Even Number?, Why Is 1 Not a Prime Number? and Prime and Composite Numbers. Each resolves a boundary that later reasoning depends on. Definitions give the subject its precision.
Continue into Factors and Multiples, Zero as a Multiple and Squares and Odd Divisor Counts. These are useful routes when a learner can calculate but cannot yet explain the relationship represented by the answer.
School mathematics and deliberate practice
The Serangoon HCF and LCM guide develops grouping and repetition. The Bukit Timah fractions, ratio and negative numbers guide connects integer foundations with the transition into secondary mathematics. The Clementi Secondary 1 Mathematics learning reference connects clear explanations with sequenced practice and checking.
Use Retrieval Practice in Mathematics when the challenge is reproducing a method independently. Reconstruct the definition and the reason for the next step, then check the result. Reading an explanation fluently is different from being able to produce it.
Proof, related branches and applications
Mathematics supplies the broader subject root. The Branches of Mathematics and Pure and Applied Mathematics help locate number theory within a wider map.
Read Logic, Proof and Verification alongside The Gold Standard of Logic. Continue into Discrete Mathematics for connected reasoning about discrete structures and algorithms. Cryptography develops a specialist application in which mathematical properties must be connected with a complete security design.
Enrichment and longer learning routes
The guide to mathematics olympiad enrichment and genuine problem solving examines that educational setting. Enrichment should develop explanations and independent methods, rather than make a learner’s identity depend on a competition result.
For longer pathways, use Courses for Mathematics and Secondary Mathematics and Future Pathways. These provide orientation; a number-theory topic by itself does not prescribe a particular course or career. Follow the question and the learner’s developing interests.
CHAPTER 19 OF 22 · Explore and transfer
19. Diagnose the exact step that needs repair
If factors and multiples are being reversed, ask for an equation of the form b = ak and label each role. If prime classification is uncertain, return to the positive-divisor definition and the requirement that the number exceed one.
If an HCF or LCM answer is wrong, check both the arithmetic and the intended relationship. Does the proposed HCF divide each original number? Is the proposed LCM a positive multiple of each? Then check whether it is the greatest or least quantity required.
If a congruence solution seems wrong, substitute it into the original statement and test whether the relevant difference is divisible by the modulus. If a cancelled step fails, check whether the cancelled factor was invertible. Repairing the condition is more useful than repeating the same invalid move.
If an explanation relies on examples, ask what makes the argument cover every permitted case. If no step does, label the result as a conjecture or a tested pattern. A diagnosis should identify a mathematical move that can be repaired, rather than attach a vague label such as careless or weak.
CHAPTER 20 OF 22 · Explore and transfer
20. Frequently asked questions about number theory
Is number theory just arithmetic with bigger numbers?
No. Arithmetic provides operations; number theory investigates the structures and relationships behind integer questions. Large numbers can be involved, but a small example may reveal a substantial issue about divisibility, proof or valid cancellation.
Are HCF and gcd the same idea?
For the positive integers used in these worked examples, yes. Highest common factor and greatest common divisor name the same quantity. In more general settings, state the conventions and permitted inputs, especially around zero and signs.
Does congruent mean equal?
It means equal remainder class for a stated modulus. The integers 17 and 2 are different, while 17 ≡ 2 (mod 5) is true. The modulus specifies which difference the relation ignores: multiples of 5.
Can I always divide both sides of a congruence?
No. Cancellation with the same modulus requires an appropriate condition, such as the cancelled factor being coprime to that modulus. Otherwise the solution information can change. Chapter 10 gives both a failed cancellation and a valid inverse calculation.
Does number theory make a cryptographic system secure?
Some cryptographic constructions use number-theoretic structures. Security also depends on the construction, assumptions, parameters, implementation and operational setting. A classroom modular-arithmetic example is a learning model, not a deployable security design. Use the Cryptography root for that broader question.
Which parts of the examples are invented?
The numerical exercises are teaching choices with exact, checkable calculations. They are not measurements or reports about a real institution. The general mathematical results are established theorems or definitions, with further reading provided in the final chapter.
CHAPTER 21 OF 22 · Explore and transfer
21. Build a learning route from explanation to independent use
Begin by choosing a short set of definitions: integer, divides, prime, gcd and congruent. For each, give a valid example and a near-example that fails for a stated reason. This reveals whether the words are connected to mathematical structure.
Next work through one algorithm slowly. Reproduce the Euclidean calculation without looking at the table, explain why each remainder step preserves the gcd and check the final divisor in the original numbers. Change one input and apply the same reasoning.
Then write a short proof and test a false claim with a counterexample. The even-sum argument and the polynomial example offer a useful contrast: one establishes every case in a domain; the other defeats a universal claim with one permitted case.
Finally, transfer the distinction to a new problem. Choose between gcd, lcm and a remainder equation by explaining the relationship the situation needs. The aim described in Learning That Transfers into Life is visible when the learner chooses and justifies the method independently.
CHAPTER 22 OF 22 · Explore and transfer
22. Sources and the next mathematical question
MIT OpenCourseWare’s Theory of Numbers course provides a university route into the subject. Its Euclidean Algorithm and Primes notes connect algorithms with proof. This article uses its own teaching examples rather than reproducing a course worksheet.
Ben Lynn’s Stanford-hosted notes provide further reading on Euclid’s algorithm and integer combinations, modular arithmetic and the Chinese remainder theorem. They are mathematical learning resources; linking them does not imply endorsement of this article by their authors or institutions.
The arithmetic here is exact. The scope of a theorem remains part of its meaning: positive inputs where specified, integer coefficients where required, and coprime moduli where the stated result needs them. Checking a condition is part of solving the problem.
The gold standard of number theory is a conclusion that can be reconstructed from definitions and valid reasoning. Return to the Mathematics root or the specialist library for the next question. A useful next step is one that asks not only what the answer is, but which relationship makes it true.
Contents · Previous chapter · Learning that transfers into life