Here are the /Solutions.

1. Matrices and graphs

Recall that a n×n matrix A has elements A_ij for each i and j in { 1 ... n }, and that the product of two such matrices AB is defined as the matrix C where C_ij = ∑_k∈{1...n} A_ikB_kj,,.

Given a directed graph G with vertices { 1 ... n }, define the adjacency matrix A(G) of G by the rule A_ij = 1 if there is an edge from i to j in G and A_ij = 0 otherwise.

Prove that for each m > 0 and each i, j in { 1 ... n }, (A(G)^m)_ij is equal to the number of distinct paths of length m from i to j in G.

2. Functions and polynomials

Let p be a prime.

1. Show that for any element a of ℤ_p there exists a polynomial q_a(x) in ℤ_p[x] with degree at most p-1 such that q_a(x) = 1 if x = a and q_a(x) = 0 otherwise.

2. Show that for any function f:ℤ_p→ℤ_p, there exists a polynomial q_f(x) in ℤ_p[x] with degree at most p-1 such that q_f(x) = f(x) for all x in ℤ_p.

3. Show that if any two polynomials q and q' of degree p-1 or less in ℤ_p[x] satisfy q(a) = q'(a) for all a in ℤ_p, then q = q' (i.e., q and q' have the same coefficients).

3. Rationality and idealism

Show that ℚ has no nontrivial proper ideals, i.e., that any ideal of ℚ is either { 0 } or ℚ itself.

4. Irreducible polynomials

Let p be prime.

1. Show that a polynomial f of degree 2 or 3 over ℤ_p is irreducible if and only if f(a) ≠ 0 for all a in ℤ_p.

2. Use this fact to compute a list of all irreducible polynomials of degree 2, 3, or 4 over ℤ₂.