Courses / Mathematics / Elementary number theory: divisibility, reciprocity and Diophantine equations Mathematics · unit version 1 Elementary number theory: divisibility, reciprocity and Diophantine equations A proof-based undergraduate sequence in integer arithmetic, congruences, arithmetic functions, reciprocity and Diophantine methods. Exact calculations support proofs; implementation and independent assessment remain separate evidence.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Readiness and preparation Check your starting point Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
What does a divide b mean, including when a is negative? Number-theoretic claims need exact integer witnesses.
Compare reasoning and find a refresher It means b=ak for some integer k. For example −3 divides 12 with k=−4. Divisibility is not a comparison of sizes or a rounded numerical ratio.
Review divisibility proofs
Why can a proof assume a claim for every smaller positive integer? Factorization and descent use well-ordering and strong induction.
Compare reasoning and find a refresher Strong induction proves a base case, then proves the claim at n assuming all required smaller cases. A minimal-counterexample argument is the equivalent well-ordering perspective; the reduction must be strictly smaller and remain in the domain.
Review strong induction
What extra condition permits division by a modulo m? Cancelling nonunits can create false congruence arguments.
Compare reasoning and find a refresher A multiplicative inverse exists exactly when gcd(a,m)=1. Bézout supplies integers u,v with au+mv=1, so u is an inverse modulo m. Without that condition, division may lose or invent solutions.
Review modular inverses
Loading saved mathematics work…
Number theory: exact arithmetic, structure and proof
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Lesson sequence Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Lesson details and objectives Build divisibility and division with remainder from integer order.
Translate divisibility into an integer witness. Prove division with remainder and its uniqueness. Use well-ordering or strong induction without assuming the conclusion. 6 practice tasks.
Lesson details and objectives Prove Euclidean reduction, termination and the Bézout identity.
Compute Euclidean remainders and Bézout coefficients. Prove the common-divisor invariant and termination. Derive cancellation when two integers are coprime. 6 practice tasks.
Lesson details and objectives Establish Euclid’s lemma, factorization uniqueness and elementary infinitude arguments.
Prove Euclid’s lemma using Bézout. Prove uniqueness of integer prime factorization. Construct infinitude arguments without assuming generated numbers are prime. 8 practice tasks.
Lesson details and objectives Use gcd divisibility to solve linear integer equations and parameterize all solutions.
Prove the gcd solvability criterion. Derive the full one-parameter solution family. Impose nonnegativity bounds without losing integer cases. 6 practice tasks.
Lesson details and objectives Prove congruence arithmetic and distinguish units from zero divisors.
Prove operations are well-defined on residue classes. Use polynomial substitution under congruence. Diagnose invalid cancellation and zero divisors. 6 practice tasks.
Lesson details and objectives Derive solvability and solution counts for ax≡b modulo m.
Apply the gcd criterion to a linear congruence. List all distinct solution classes. Construct inverses and justify reduced-modulus cancellation. 6 practice tasks.
Lesson details and objectives Construct CRT solutions and prove uniqueness modulo the correct common period.
Build a solution for pairwise coprime moduli. Prove uniqueness modulo the product. Handle noncoprime compatibility using a gcd condition. 6 practice tasks.
Lesson details and objectives Prove Euler’s theorem, Fermat’s theorem and the limits of converse primality claims.
Prove the unit-permutation argument. Compute powers with the correct coprimality condition. Distinguish necessary prime identities from primality certificates. 8 practice tasks.
Lesson details and objectives Prove order divisibility and compute periods of powers.
Prove an order divides every return exponent. Derive the order-of-a-power formula. Use prime-factor tests to certify a proposed order. 6 practice tasks.
Lesson details and objectives Establish primitive roots for primes and their permitted composite extensions.
Prove finite field unit groups are cyclic. Lift primitive roots to odd prime powers. Explain the classification of moduli admitting primitive roots. 6 practice tasks.
Lesson details and objectives Develop multiplicative arithmetic functions and divisor-sum identities.
Derive formulas for φ, divisor count and divisor sum. Distinguish multiplicative from completely multiplicative functions. Prove divisor identities by classifying integers. 8 practice tasks.
Lesson details and objectives Define the Möbius function and prove inversion through a finite double sum.
Compute Möbius values from prime factorization. Prove the divisor cancellation identity. Apply inversion and squarefree counting with justified finite rearrangements. 6 practice tasks.
Lesson details and objectives Count square classes, define the Legendre symbol and use primitive-root parity.
Count nonzero squares modulo an odd prime. Derive multiplicativity of the Legendre symbol. Separate prime-field square tests from composite-modulus behavior. 6 practice tasks.
Lesson details and objectives Prove Euler’s criterion and Gauss’s lemma, including supplementary residue laws.
Prove Euler’s criterion without a converse gap. Derive Gauss’s signed-product lemma. Obtain the supplementary laws for −1 and 2. 6 practice tasks.
Lesson details and objectives Derive quadratic reciprocity through Gauss parity and a lattice-point count.
Convert Gauss’s count into a floor-sum parity formula. Prove reciprocity by partitioning a lattice rectangle. Use reciprocity with supplementary laws in explicit calculations. 6 practice tasks.
Lesson details and objectives Solve prime quadratic congruences and combine component roots with CRT.
Complete the square modulo odd primes. Enumerate composite roots by compatible CRT components. Explain why Jacobi value one is not a square certificate. 6 practice tasks.
Lesson details and objectives Derive the first-order lifting congruence.
Derive the first-order lifting congruence. Distinguish unique, multiple and impossible lifts. Construct a root modulo successive prime powers. 6 practice tasks.
Lesson details and objectives Compute finite continued fractions by Euclidean division.
Compute finite continued fractions by Euclidean division. Separate rational termination from irrational expansion. Explain the ambiguity in a terminal coefficient. 6 practice tasks.
Lesson details and objectives Derive numerator and denominator recurrences.
Derive numerator and denominator recurrences. Prove the adjacent determinant identity. Bound irrational approximation using the complete quotient. 6 practice tasks.
Lesson details and objectives Use norm multiplication to generate Pell solutions.
Use norm multiplication to generate Pell solutions. Prove existence using bounded convergent norms. Distinguish finite search evidence from impossibility. 6 practice tasks.
Lesson details and objectives Derive the coprime opposite-parity parametrization.
Derive the coprime opposite-parity parametrization. Explain why its hypotheses give primitive triples. Recover parameters from a primitive triangle. 6 practice tasks.
Lesson details and objectives Prove the obstruction from primes congruent to three modulo four.
Prove the obstruction from primes congruent to three modulo four. Construct a representation of primes congruent to one modulo four. Combine prime representations multiplicatively. 6 practice tasks.
Lesson details and objectives Identify a positive integer that strictly decreases.
Identify a positive integer that strictly decreases. Prove the square-area right-triangle obstruction. Transfer an integer impossibility to rational triangles. 10 practice tasks.
Lesson details and objectives Implement repeated squaring with an exact modular invariant.
Implement repeated squaring with an exact modular invariant. Prove RSA correctness for every residue using CRT. Separate arithmetic correctness from cryptographic security. 6 practice tasks.
Lesson details and objectives Prove both directions of Wilson’s criterion.
Prove both directions of Wilson’s criterion. Use factors and order witnesses as certificates. Explain why a Fermat pass need not certify primality. 6 practice tasks.
Lesson details and objectives Derive the shortcut for primes congruent to three modulo four.
Derive the shortcut for primes congruent to three modulo four. Execute Tonelli–Shanks with exact invariants. Prove termination by decreasing a power-of-two order bound. 7 practice tasks.
Lesson details and objectives Construct cyclotomic polynomials, prove irreducibility and identify their field automorphisms.
Construct cyclotomic polynomials and prove integrality. Relate prime divisors of values to exact orders. Prove infinitely many primes congruent to one modulo a fixed integer. Prove cyclotomic irreducibility by reduction modulo primes. Identify cyclotomic Galois groups with invertible residues. 9 practice tasks.
Lesson details and objectives Derive finite-prime Euler products by geometric series.
Derive finite-prime Euler products by geometric series. Justify the infinite product for real exponent greater than one. Relate divisor convolution and Möbius inversion to Dirichlet series. 6 practice tasks.
Lesson details and objectives Verify the four-square multiplication identity.
Verify the four-square multiplication identity. Produce a prime multiple with a bounded multiplier. Carry out the multiplier descent proving Lagrange’s theorem. 6 practice tasks.
Lesson details and objectives Derive a rational circle parametrization by intersecting a line.
Derive a rational circle parametrization by intersecting a line. Recover the slope and account for exceptional points. Explain why the existence of a rational base point matters. 6 practice tasks.
Learn