Modular arithmetic and algebra for computing

On an ordinary clock, adding hours wraps around a fixed cycle. In modular arithmetic, the same idea applies to all integers, including negative ones. Addition and multiplication remain well defined, but division behaves differently: a nonzero residue may have no inverse. A cancellation step that is valid over the real numbers can silently turn a true modular equation into a false one.

This module connects integer divisibility to legal modular operations. You will derive Euclid’s invariant, compute a Bézout certificate, identify invertible residues, trace fast powers, and distinguish groups, rings, and fields. The final examples separate binary field arithmetic from machine-word arithmetic and show precisely what a tiny checksum does and does not establish.

Retrieval check: manipulate integer equations, expand a finite product, and explain an invariant together with a decreasing integer variant. Review Module 01 and Module 04 as needed. The core lesson does not require the graph or counting modules. All moduli here are integers m≥2 unless a different convention is explicitly stated.

For integers a,b, a divides b, written a|b, means there is an integer k such that b=ak. This is an existence statement in the integer domain. It does not mean a/b is an integer, and it does not mean b must be larger than a. For example 3 divides −12 because −12=3·(−4). Every integer divides zero; zero divides only zero. Prime and gcd definitions below avoid confusing this special case with positive divisors.

If a|b and a|c, then a divides every integer linear combination xb+yc: substitute b=as and c=at to obtain xb+yc=a(xs+yt). If a|b and b|c, then a|c by multiplying the witnesses. These short proofs explain why subtracting a multiple of one integer from another preserves their common divisors. The coefficients must be integers; arbitrary real combinations would not preserve an integer divisibility conclusion.

The division algorithm is a theorem: for any integer a and positive integer m, there are unique integers q,r with a=qm+r and 0≤r<m. “Algorithm” here names the quotient–remainder property rather than requiring a particular implementation. One existence argument chooses q as the largest integer no greater than a/m, then r=a−qm. Its floor inequalities give exactly the stated remainder range, including when a is negative.

For uniqueness, suppose qm+r=q′m+r′ with both remainders in that range. Then (q−q′)m=r′−r. The right side has magnitude less than m; the only multiple of m in that interval is zero. Thus q=q′ and r=r′. A different remainder convention, such as allowing negative remainders after truncating division, changes the representation rule. Our mathematical representative matches Python’s integer remainder when the modulus is positive.

A prime is an integer p>1 whose positive divisors are only 1 and p. An integer greater than one that is not prime is composite. The integer one is neither prime nor composite; negative primes are outside this convention. To factor a positive integer greater than one, recursively split any composite factor into smaller factors until all factors are prime. Strong induction on the integer proves that this process has a prime factorisation.

The fundamental theorem of arithmetic also states uniqueness up to factor order. Its key lemma is that a prime dividing a product divides at least one factor. We justify that lemma using Bézout in the next section. Repeatedly apply it to match a prime on one factorisation to an equal prime on the other, cancel that positive integer factor, and continue. Existence and uniqueness are separate obligations; listing one successful factorisation proves only existence for that input.

Prime factorisation is a mathematical description, not a claim that finding the factors of every large integer is fast. Our small examples use exact arithmetic and elementary reasoning. Euclid computes gcd without first factoring both inputs, which is one reason the invariant-based algorithm is useful. Later cost analysis should count bit operations when integer sizes grow, rather than treating enormous products or divisions as fixed-cost steps.

For nonnegative integers a,b not both zero, the greatest common divisor gcd(a,b) is the greatest positive integer dividing both. It exists because common positive divisors are nonempty and bounded by a nonzero input. In particular gcd(a,0)=a for a>0. For arbitrary signs, use gcd(|a|,|b|). Both-zero has no greatest positive common divisor; software often defines gcd(0,0)=0 as a useful separate convention.

If a=qb+r, the pairs (a,b) and (b,r) have exactly the same common divisors. A divisor of a and b divides r=a−qb. Conversely, a divisor of b and r divides a=qb+r. Hence gcd(a,b)=gcd(b,r). This proves preservation by Euclid’s algorithm, which repeatedly replaces (a,b) with (b,a mod b) while b is nonzero. The invariant is equality with the original gcd, not merely a decreasing remainder.

Termination follows because each nonzero second component is a nonnegative integer and the next remainder satisfies 0≤r<b. A strictly decreasing nonnegative integer cannot continue forever. When b=0, the first component is the gcd by the invariant and the gcd(a,0) base case. Preservation explains correctness if the loop ends; the decreasing variant separately proves that it does end. Both are needed, as in Module 04.

Bézout’s identity says there are integers x,y with ax+by=gcd(a,b). Extended Euclid computes them by tracking two coefficient pairs. Initially a=1·a+0·b and b=0·a+1·b. Subtracting q times the second tracked equation from the first updates the remainder and its coefficients together. Swapping the two rows preserves the representation invariant. The final nonzero remainder therefore carries a concrete integer certificate.

The coefficients are not generally unique. If ax+by=d, then replacing x by x+(b/d)t and y by y−(a/d)t preserves the identity for any integer t. A lab returning different coefficients can still be correct; check the actual equation and gcd value rather than demanding a particular pair. Zero inputs have valid identities too, while the both-zero software convention returns a representation of zero rather than a greatest positive divisor.

If p is prime and p does not divide a, then gcd(p,a)=1, so Bézout gives px+ay=1. If p divides ab, multiply that equation by b: pxb+aby=b. Both terms on the left are divisible by p, hence p divides b. Thus p|ab implies p|a or p|b. This proves the prime-product lemma used for factorisation uniqueness without assuming that an arbitrary composite divisor has the same property.

For example 6 divides 2·3 but divides neither 2 nor 3, so substituting “any integer” for “prime” would make the lemma false. The precise hypotheses matter again in modular cancellation. A nonzero factor and a factor coprime to the modulus have different powers. Bézout will turn coprimality into an inverse and allow a valid cancellation proof.

Euclid’s division count grows logarithmically in the smaller positive input. One elementary reason is that the second component falls by at least a factor two within two iterations: if the first remainder r≤b/2 the reduction is immediate; if r>b/2, the next remainder of b by r is b−r<b/2. This bounds the number of remainder steps. It is a step-count argument, not a proof that each division of long integers costs constant time.

For integers a,b and fixed m≥2, a is congruent to b modulo m, written $a\equiv b\pmod m$, when m divides a−b. This is a relation between integers, not an assertion that a and b are literally equal. Congruence is reflexive because m|0, symmetric because a divisibility witness can be negated, and transitive because divisible differences add. Its equivalence classes collect all integers differing by a multiple of m.

The class of a can be written [a]ₘ. It contains a+km for every integer k, including negative k. The division theorem gives each class a unique representative from 0 through m−1; call that representative a mod m. Thus [−17]₇=[4]₇, whereas −17 and 4 remain different integers. Writing an equation between classes is appropriate, but replacing it with equality between the original integers loses the distinction.

Define class addition and multiplication by [a]+[b]=[a+b] and [a][b]=[ab]. To be well defined, the result must be independent of representative choices. If a′=a+km and b′=b+ℓm, their sum differs from a+b by (k+ℓ)m, and their product differs from ab by m(kb+ℓa+kℓm). Both differences are divisible by m. This proof permits reducing operands before an operation without changing the final residue.

Subtraction is addition of the additive inverse: [a] has inverse [−a]. For example −3 mod7 is four, because 3+4≡0. This inverse always exists for addition. It should not be confused with a multiplicative inverse, which would solve ab≡1 rather than a+b≡0. The same word inverse refers to the chosen operation, so name the operation when it is ambiguous.

Modular powers with nonnegative exponent are repeated class multiplication, with exponent zero interpreted as the empty product [1]. This algebraic convention also makes the exponent-zero algorithm return one for base zero. It does not settle every analytic use of the expression 0⁰; the earlier discussion of domains still applies. Negative exponents require a multiplicative inverse and cannot be defined for every residue.

A residue clock displays addition as rotation by a fixed number of steps. Adding a is always a permutation of the m residue positions, since subtracting a reverses it. Multiplication by a is different: it can send distinct positions to the same result. Modulo six, multiplying one and four by two gives two in both cases. The next section explains exactly when this multiplication map is a permutation.

Comparing or ordering canonical representatives is a display convention. From a≡b mod m it does not follow that they have the same ordinary magnitude or sign. Similarly, reducing an inequality modulo m is not a valid order-preserving operation: 6<8 but 6 mod7=6 exceeds 8 mod7=1. Congruence supports algebraic operations with a proof, not every operation that happens to work on integers.

The representative set {0,…,m−1} is often used as shorthand for the classes themselves. Keep the interpretation visible when crossing into software. A Python integer such as three does not carry a modulus in its type; the programme must apply the intended modulus consistently. Combining residues from different moduli without a stated map is not a single modular calculation, even if their numeric representatives happen to match.

A multiplicative inverse of a modulo m is a residue b satisfying ab≡1 mod m. It exists exactly when gcd(a,m)=1. For necessity, ab−1=km gives ab−km=1, so every common divisor of a and m divides one. For sufficiency, Bézout gives ax+my=1 when the gcd is one, so x is an inverse modulo m. These directions prove an if-and-only-if statement rather than a rule supported by sample calculations.

If an inverse exists, it is unique as a class. Given ab≡1 and ac≡1, multiply by b to obtain b≡c. Equivalently use a’s established inverse to cancel a. An inverse representative may be negative before canonical reduction: extended Euclid gives −2 as an inverse of three modulo seven, and −2 mod7 is five. Uniqueness concerns classes, not all integer representatives of one class.

Cancellation from ax≡ay mod m to x≡y mod m is valid when gcd(a,m)=1: multiply both sides by the inverse. Without that condition it can fail. Modulo six, 2·1≡2·4, yet one is not congruent to four. Dividing both representatives by ordinary integer two does not preserve the original modulus. In this example the remaining condition is x≡y modulo three, a different and weaker statement.

More generally let d=gcd(a,m). From m|a(x−y), divide the integer divisibility equation by d. The integers a/d and m/d are coprime, so Bézout cancellation gives (m/d)|(x−y). Thus the appropriate reduced modulus is m/d. Integer division of an exact equation and inversion of a class are different operations; writing the intermediate divisibility equation prevents a misleading cancellation symbol from hiding that distinction.

The linear congruence ax≡b mod m has a solution exactly when d=gcd(a,m) divides b. Necessity follows because d divides ax and m, hence also b. For sufficiency, divide a,b,m by d; now a/d is invertible modulo m/d, giving one reduced solution x₀. In the original residue range the solutions are x₀+k(m/d), k=0,…,d−1. They are distinct modulo m and exhaust the solutions because any solution differs from x₀ by a multiple of m/d.

For 4x≡2 mod6, d=2 and the reduced equation is 2x≡1 mod3. Two has inverse two modulo three, so x≡2 mod3; representatives modulo six are two and five. For 2x≡1 mod6, d=2 does not divide one, so there is no solution. An equation can have zero, one, or several solutions depending on its gcd condition; treating every nonzero coefficient as a unique divider loses all three distinctions.

When d=m, such as a=0 modulo m, divisibility of b by m determines the result. If b≡0, every residue solves 0x≡0; otherwise none does. The reduced modulus is one, which is a trivial congruence relation rather than the m≥2 algebraic structures we otherwise study. State this boundary separately instead of calling the modulo-one class an ordinary nontrivial field.

A nonzero residue with a nonzero partner whose product is zero is a zero divisor. In modulo six, two and three multiply to zero. In a prime modulus p, every nonzero residue is coprime to p and invertible, so no such pair exists: multiplying a zero product by an inverse would force the other factor to zero. This is the algebraic reason prime moduli differ from composite ones.

Repeated squaring evaluates aᴱ mod m for a nonnegative integer E without performing E consecutive multiplications. Maintain result r, current base b, and remaining exponent e, initially 1,a mod m,E. The invariant is rbᵉ≡aᴱ mod m. If e is odd, multiply r by b; square b; replace e by floor(e/2). For even e=2k, the new product is r(b²)ᵏ. For odd e=2k+1, it is (rb)(b²)ᵏ. Both equal the old product as classes.

The nonnegative exponent strictly decreases when positive, so the loop terminates at e=0. The invariant then gives r≡aᴱ. Zero exponent takes no iterations and returns one under the empty-product convention. Reducing after every multiplication preserves the invariant and bounds stored residues by m−1. It avoids constructing the enormous unreduced power, although multiplication itself still has a bit cost depending on the modulus size.

For E>0 the iteration count is floor(log₂E)+1, its binary length. Each iteration performs at most two modular multiplications, giving O(log(E+1)) such operations including the E=0 boundary. This is logarithmic in the exponent’s numeric value and linear in its bit length, not logarithmic in the length of its binary encoding. Very large moduli make each operation more expensive; the multiplication count alone is not a complete runtime proof.

Fermat’s little theorem states: if p is prime and p does not divide a, then aᵖ⁻¹≡1 mod p. To prove it, multiplication by a permutes the nonzero residues, because a has an inverse. Multiply all p−1 nonzero outputs: aᵖ⁻¹(p−1)!≡(p−1)! mod p. Every factorial factor is nonzero and invertible modulo p, so its product can be cancelled. The remaining equation is exactly the claimed power congruence.

For a divisible by p, the nonzero-base conclusion is false; instead the common all-integer form is aᵖ≡a mod p, proved by handling zero and nonzero classes separately. A composite modulus does not satisfy the prime theorem in general: 2⁵ mod6 is two, not one, and even the coprime base five gives 5⁵ mod6 equal to five. Some composite numbers pass particular power checks, so one successful check is not automatically a proof of primality.

When p is prime and a is nonzero modulo p, the inverse can be computed as aᵖ⁻² modulo p. This follows by multiplying a by that power and using Fermat. The hypotheses remain necessary; extended Euclid works for any coprime modulus without needing primality. Our labs use both the gcd condition and Python’s exact modular power contract rather than applying the prime formula indiscriminately.

The Chinese remainder theorem (CRT) for coprime positive moduli m,n states that specified residues modulo m and modulo n determine a unique class modulo mn. Construct a solution using inverses: if u is an inverse of n modulo m and v an inverse of m modulo n, then x=anu+bmv has residues a modulo m and b modulo n. Each term vanishes in one modulus and supplies the requested residue in the other.

For the uniqueness proof in general, if m and n both divide a difference Δ, write Δ=mk. Coprimality lets n be cancelled from n|mk, giving n|k, hence mn|Δ. Without coprimality the compatibility condition changes and the combined period need not be mn. For example x≡0 mod2 and x≡1 mod4 is impossible because every second condition’s representative is odd. We do not claim the coprime construction handles this conflicting pair.

An algebraic structure specifies a set together with operations and laws. A group has one closed associative operation, an identity, and an inverse for every element. A group is abelian if its operation is commutative. Integers with addition form an abelian group: zero is identity and −a is the inverse of a. Integers with multiplication do not form a group, because zero and most other integers have no integer multiplicative inverse.

Residue classes modulo m form an abelian group under addition. Under multiplication, the units, exactly the classes coprime to m, form a group: one is identity, products of units have inverses obtained by multiplying their inverses, and each unit’s inverse is another unit. All nonzero classes modulo a composite number need not form such a group, because zero divisors may multiply to zero and may lack inverses. Here a unit means an invertible element; it is distinct from the operation’s identity.

A commutative ring with identity has an abelian additive group and a closed associative commutative multiplication with identity, distributing over addition. We use nontrivial rings with 1≠0 here. The integers and the modulo-m classes are examples. Addition, multiplication, and distributivity survive reduction because the class operations are well defined. A ring does not promise division by every nonzero element; that extra promise distinguishes a field.

A field is a commutative ring with 1≠0 in which every nonzero element has a multiplicative inverse. The rationals and reals are fields; the integers are not, since two has no integer inverse. Modulo p is a field exactly when p is prime. Prime p gives inverses by the gcd criterion; composite m=uv with 1<u,v<m gives nonzero classes [u],[v] with product zero, which a field cannot permit.

Many fixed-width unsigned operations wrap modulo 2ʷ, but the representation and language still determine behaviour. A modulo-256 ring has zero divisors, for example 16·16≡0, and is not a field. Python integers do not automatically wrap at a fixed width; an explicit reduction is required in our scripts. These observations describe the model used in an example, not every language’s signed-overflow rule or every hardware instruction.

A checksum can be a function c(values)=sum(values) mod7 for byte values from zero through 255. Its output is one of seven residues. Equal inputs necessarily give equal checksums; different checksums therefore prove inputs differ. Equal checksums do not prove equality. The distinct lists [1,2] and [0,3] both give three; reversing [1,2] also preserves the sum, and adding seven to an allowed byte preserves its residue.

Compression to a small output set inevitably permits collisions over a larger input set: an injective assignment would need a different output for each distinct input. More specifically this checksum has easily constructed collisions and ignores order. It may detect some accidental changes, such as increasing one byte by one while staying in range, but it fails on compensating changes, transpositions, and changes by a multiple of seven. A report should state the particular detection property rather than advertising universal error detection.

Modular arithmetic also appears in cryptographic mathematics, but the presence of primes, inverses, or a fast power calculation does not itself establish security. A toy checksum or a small illustrative modular construction supplies no resistance claim against an adversary. Such a claim needs a specified construction, threat model, assumptions, and analysis far beyond the calculations here. The lesson’s transfer goal is to recognise the algebraic operations and the limits of the evidence, not to design a production security system.

Use Python 3.11+ and the standard library. Predict the identities and counterexamples before running. Downloaded scripts are the exact sources used to capture the output below.

Lab A Euclid and extended Euclid

Predict: the gcd and Bézout coefficients for 252,105. Run: read quotient rows and verify each reported identity. Explain: why zero inputs need separate conventions, especially (0,0). Change: add a positive pair with gcd one and verify that either coefficient gives an inverse with the appropriate modulus. Negative inputs are outside this lab’s declared input domain.

Download lab1_euclid.py

"""Euclid and extended Euclid for nonnegative integer inputs."""
from math import gcd

def euclid_trace(a, b):
    if a < 0 or b < 0:
        raise ValueError("This lab uses nonnegative integers")
    rows = []
    while b:
        q, r = divmod(a, b)
        rows.append((a, b, q, r))
        a, b = b, r
    return a, rows

def extended_gcd(a, b):
    if a < 0 or b < 0:
        raise ValueError("This lab uses nonnegative integers")
    old_r, r = a, b
    old_x, x, old_y, y = 1, 0, 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y

value, rows = euclid_trace(252, 105)
for a, b, q, r in rows:
    print(f"{a} = {q}*{b} + {r}")
print("Last nonzero remainder / gcd:", value)
for a, b in [(252, 105), (12, 18), (0, 7), (9, 0), (0, 0)]:
    d, x, y = extended_gcd(a, b)
    assert d == gcd(a, b) and a * x + b * y == d
    print(f"a={a}, b={b}: gcd={d}, x={x}, y={y}; a*x+b*y={a*x+b*y}")
print("The (0,0) gcd is zero by software convention; it has no positive greatest common divisor.")

252 = 2*105 + 42
105 = 2*42 + 21
42 = 2*21 + 0
Last nonzero remainder / gcd: 21
a=252, b=105: gcd=21, x=-2, y=5; a*x+b*y=21
a=12, b=18: gcd=6, x=-1, y=1; a*x+b*y=6
a=0, b=7: gcd=7, x=0, y=1; a*x+b*y=7
a=9, b=0: gcd=9, x=1, y=0; a*x+b*y=9
a=0, b=0: gcd=0, x=1, y=0; a*x+b*y=0
The (0,0) gcd is zero by software convention; it has no positive greatest common divisor.

Lab B Repeated squaring and operation counts

Predict: 3¹³ mod7 and its four loop-head triples. Run: compare results with Python’s three-argument pow, including zero exponent and negative base. Explain: why one million as an exponent takes twenty iterations and why this does not make all long-integer multiplications constant-cost. Change: skip the final unused square, keep the invariant and outputs, and compare exact multiplication counts. The script’s zero-base zero-exponent case uses the stated empty-product convention; its nonnegative exponent restriction is narrower than Python’s full pow interface.

Download lab2_modular_powers.py

"""Repeated squaring with exact integer arithmetic and an explicit operation count."""
def power_mod(base, exponent, modulus):
    if exponent < 0 or modulus < 2:
        raise ValueError("Require exponent >= 0 and modulus >= 2")
    original_base, original_exponent = base, exponent
    result, base = 1, base % modulus
    steps, multiplications, trace = 0, 0, []
    while exponent:
        trace.append((result, base, exponent))
        if exponent % 2:
            result = result * base % modulus
            multiplications += 1
        base = base * base % modulus  # Also counted in the final iteration.
        multiplications += 1
        exponent //= 2
        steps += 1
    assert result == pow(original_base, original_exponent, modulus)
    return result, steps, multiplications, trace

for base, exponent, modulus in [(3, 13, 7), (5, 0, 11), (0, 0, 7), (-2, 9, 13), (17, 1_000_000, 97)]:
    value, steps, multiplications, trace = power_mod(base, exponent, modulus)
    assert steps == exponent.bit_length()
    print(f"({base})^{exponent} mod {modulus} = {value}; iterations={steps}, multiplications={multiplications}")
    if (base, exponent, modulus) == (3, 13, 7):
        print("Loop-head (result, base, exponent):", trace)
print("At most two modular multiplications per iteration; their bit cost is not constant in general.")
for base, exponent, modulus in [(3, -1, 7), (3, 5, 1)]:
    try:
        power_mod(base, exponent, modulus)
    except ValueError as error:
        print("Rejected:", (base, exponent, modulus), str(error))

(3)^13 mod 7 = 3; iterations=4, multiplications=7
Loop-head (result, base, exponent): [(1, 3, 13), (3, 2, 6), (3, 4, 3), (5, 2, 1)]
(5)^0 mod 11 = 1; iterations=0, multiplications=0
(0)^0 mod 7 = 1; iterations=0, multiplications=0
(-2)^9 mod 13 = 8; iterations=4, multiplications=6
(17)^1000000 mod 97 = 35; iterations=20, multiplications=27
At most two modular multiplications per iteration; their bit cost is not constant in general.
Rejected: (3, -1, 7) Require exponent >= 0 and modulus >= 2
Rejected: (3, 5, 1) Require exponent >= 0 and modulus >= 2

Lab C Illegal division and checksum collisions

Predict: inverse availability, the solutions of 4x≡2 mod6, and each collision’s output. Run: inspect rejected inverses and exhaustive six-residue solutions. Explain: why the inverse gcd condition is a theorem, whereas finite enumeration checks only these specific equations. Change: substitute modulus eleven in the checksum and build a new permitted-byte collision. A larger residue range does not turn this sum into a security construction.

Download lab3_division_and_collisions.py

"""Counterexamples to universal modular division and checksum uniqueness."""
from math import gcd

def inverse(a, modulus):
    if modulus < 2:
        raise ValueError("Require modulus >= 2")
    if gcd(a, modulus) != 1:
        raise ValueError("Residue is not invertible")
    return pow(a, -1, modulus)

for a, modulus in [(3, 7), (2, 6), (5, 6), (0, 7)]:
    try:
        inv = inverse(a, modulus)
        assert a * inv % modulus == 1
        print(f"Inverse of {a} mod {modulus}: {inv}")
    except ValueError as error:
        print(f"Inverse of {a} mod {modulus}: rejected ({error})")
for a, b, modulus in [(4, 2, 6), (2, 1, 6)]:
    solutions = [x for x in range(modulus) if (a * x - b) % modulus == 0]
    assert bool(solutions) == (b % gcd(a, modulus) == 0)
    print(f"{a}x = {b} mod {modulus}: solutions {solutions}")
print("Illegal cancellation:", "2*1 mod 6 =", 2 * 1 % 6, "; 2*4 mod 6 =", 2 * 4 % 6)
assert (2 * 1 - 2 * 4) % 6 == 0 and (1 - 4) % 6 != 0

def checksum(values):
    if any(not isinstance(v, int) or v < 0 or v > 255 for v in values):
        raise ValueError("Values must be bytes")
    return sum(values) % 7

pairs = [([1, 2], [0, 3]), ([1, 2], [2, 1]), ([1, 2], [8, 2])]
for left, right in pairs:
    assert left != right and checksum(left) == checksum(right)
    print("Collision:", left, right, "; checksum =", checksum(left))
print("Different checksum proves a difference; equal checksum does not prove equal input or security.")

Inverse of 3 mod 7: 5
Inverse of 2 mod 6: rejected (Residue is not invertible)
Inverse of 5 mod 6: 5
Inverse of 0 mod 7: rejected (Residue is not invertible)
4x = 2 mod 6: solutions [2, 5]
2x = 1 mod 6: solutions []
Illegal cancellation: 2*1 mod 6 = 2 ; 2*4 mod 6 = 2
Collision: [1, 2] [0, 3] ; checksum = 3
Collision: [1, 2] [2, 1] ; checksum = 3
Collision: [1, 2] [8, 2] ; checksum = 3
Different checksum proves a difference; equal checksum does not prove equal input or security.

Exercises 1–12 are required; 13–14 are optional extensions. Give domains, inverse conditions, and exact modular checks rather than an unexplained division sign.

Automatic scoring covers Questions 1–9. The last question is written and self-reviewed.

Read number-theory selections in MIT Mathematics for Computer Science. The MIT Theory of Numbers notes provide Euclidean-algorithm and linear-congruence/CRT selections for comparison. Check the integer three-argument interface in the Python pow documentation. These are external primary readings; our lesson examples and required practice are original.

Python’s modular negative exponent requires the base to be coprime to the modulus. Our repeated-squaring lab deliberately accepts nonnegative exponents and moduli at least two, so do not mistake its restricted interface for every case supported by Python.

Without notes, state quotient–remainder uniqueness, prove Euclid’s preservation and termination, and derive inverse existence from Bézout. Explain the difference between a class and a representative, give one failed cancellation, and state Fermat’s and CRT’s exact hypotheses.

Exit task: work modulo ten. Find the units, solve 4x≡6, and compare a field with this ring. Units are 1,3,7,9. Dividing the congruence by gcd two yields 2x≡3 mod5, so x≡4 mod5 and representatives four,nine solve it. Modulo ten is not a field: two and five are nonzero zero divisors.

Ready to move on: you can justify an operation before computing it and qualify the conclusion of a toy experiment. The linear-algebra branch starts with vectors, geometry, and array shapes; the CS route later returns to probability. See the course overview for available lessons and routes.