Appendix D: Solutions for Chapter 2

This page collects solutions and editorial notes for the exercises in Chapter 2: Mathematical preliminaries. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Every block below is self-contained, so a block that uses a chapter helper restates it at the top. The fuller versions of these routines, with the reasoning written out, are in the prelim_algebra package under solutions/ch02-algebra. From a clone of the companion repository, pytest tests/ch02 runs its suite. Appendix C has the setup.

Exercise 1

Both routes reduce to 3 modulo 13. Reducing the exponent modulo 12 first is the standard application of Fermat’s little theorem. With the exponent already reduced from 200 to 8, the second computation is a sanity check rather than a separate calculation. The exercise asks for the chapter’s mod_pow rather than the built-in, so the block restates it and then confirms the built-in agrees.

def mod_pow(base, exponent, modulus):
    assert exponent >= 0, "exponent must be non-negative"
    assert modulus >= 1, "modulus must be at least 1"
    result = 1 % modulus
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result


direct = mod_pow(7, 200, 13)
reduced = mod_pow(7, 200 % 12, 13)
print(direct, reduced)
print(direct == reduced == pow(7, 200, 13))
# ==> 3 3
# ==> True

Exercise 2

The candidate $g = 2$ fails because $2^8 \equiv 1 \pmod{17}$, so the order of 2 is 8, not 16, and the orbit covers only half of the group. The next candidate $g = 3$ has order exactly 16 and is a generator. The full power sequence is shown below. Verify that the multiset matches $\{1, 2, \ldots, 16\}$.

Order always divides $p - 1$ by Lagrange’s theorem, which is why comparing the order against $p - 1$ is the whole generator test and no separate check is needed.

def order(g, p):
    x, k = g % p, 0
    while True:
        k += 1
        if x == 1:
            return k
        x = (x * g) % p


def find_generator(p):
    for candidate in range(2, p):
        if order(candidate, p) == p - 1:
            return candidate
    raise AssertionError(f"no generator found modulo {p}")


powers_of_3 = [pow(3, k, 17) for k in range(1, 17)]
print(order(2, 17), order(3, 17))
print(find_generator(17))
print(powers_of_3)
# ==> 8 16
# ==> 3
# ==> [3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1]

Exercise 3

The values are $f(0)=1, f(1)=3, f(2)=4, f(3)=3, f(4)=6, f(5)=5, f(6)=6$. None is zero modulo 7, so $f$ has no root in $\mathbb{F}_7$. Because $f$ has degree 3, the equivalence cited in the exercise applies: a proper factorization of a degree-3 polynomial over a field would include a linear factor, and a linear factor would force a root. There is no root, so there is no proper factorization, so $f$ is irreducible over $\mathbb{F}_7$.

Returning the list of roots rather than a boolean costs nothing and says more: the empty list is the irreducibility witness here, and on a polynomial that does factor the same call names the linear factors.

def poly_eval(coeffs, x, p):
    return sum(c * pow(x, i, p) for i, c in enumerate(coeffs)) % p


def roots(coeffs, p):
    return [k for k in range(p) if poly_eval(coeffs, k, p) == 0]


# f(x) = 1 + x + 0*x^2 + 1*x^3
coeffs = [1, 1, 0, 1]
print([poly_eval(coeffs, k, 7) for k in range(7)])
print(roots(coeffs, 7))
# ==> [1, 3, 4, 3, 6, 5, 6]
# ==> []

Exercise 4

The rank is 2. Reducing modulo 7 sends the entry 7 in row 4 to 0, but the structural argument does not depend on that detail. Every row is an arithmetic progression with common difference 1, so successive rows differ by the all-ones vector $\mathbf{1} = (1, 1, 1, 1)$. That gives row $i =$ row 1 $+ (i-1) \cdot \mathbf{1}$, so every row lies in $\operatorname{span}(\text{row 1}, \mathbf{1})$. The two spanning vectors are linearly independent because no scalar multiple of $\mathbf{1}$ equals row 1, so the row space has dimension exactly 2.

The same conclusion can be reached from the other side. The rows satisfy two independent relations, $\text{row 3} - 2 \cdot \text{row 2} + \text{row 1} = \mathbf{0}$ and $\text{row 4} - 2 \cdot \text{row 3} + \text{row 2} = \mathbf{0}$, which show the rank is at most 2. The span argument above shows it is at least 2. Together they pin it at exactly 2. Exhibiting relations alone would not be enough: two relations bound the rank from above and leave open whether a third exists.

def gauss_eliminate(matrix, p):
    assert p > 1, "p must be prime; this helper does not test primality"
    m = [row[:] for row in matrix]
    rows = len(m)
    cols = len(m[0]) if m else 0
    rank = 0
    for col in range(cols):
        pivot = None
        for r in range(rank, rows):
            if m[r][col] % p != 0:
                pivot = r
                break
        if pivot is None:
            continue
        m[rank], m[pivot] = m[pivot], m[rank]
        inv = pow(m[rank][col], p - 2, p)
        m[rank] = [(x * inv) % p for x in m[rank]]
        for r in range(rows):
            if r != rank and m[r][col] % p != 0:
                factor = m[r][col]
                m[r] = [(m[r][c] - factor * m[rank][c]) % p for c in range(cols)]
        rank += 1
    return m, rank


M = [[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7]]
_reduced, rank = gauss_eliminate(M, 7)
print("rank =", rank)

ones = [1, 1, 1, 1]
diff = [[(M[i][j] - M[i - 1][j]) % 7 for j in range(4)] for i in range(1, 4)]
print(all(row == ones for row in diff))

r1, r2, r3, r4 = M
print([r3[j] - 2 * r2[j] + r1[j] for j in range(4)])
print([r4[j] - 2 * r3[j] + r2[j] for j in range(4)])
# ==> rank = 2
# ==> True
# ==> [0, 0, 0, 0]
# ==> [0, 0, 0, 0]