Here are the /Solutions.
1. Matrices and graphs
Recall that a n×n matrix A has elements Aij for each i and j in { 1 ... n }, and that the product of two such matrices AB is defined as the matrix C where Cij = ∑k∈{1...n} AikBkj,,.
Given a directed graph G with vertices { 1 ... n }, define the adjacency matrix A(G) of G by the rule Aij = 1 if there is an edge from i to j in G and Aij = 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.
Show that for any element a of ℤp there exists a polynomial qa(x) in ℤp[x] with degree at most p-1 such that qa(x) = 1 if x = a and qa(x) = 0 otherwise.
Show that for any function f:ℤp→ℤp, there exists a polynomial qf(x) in ℤp[x] with degree at most p-1 such that qf(x) = f(x) for all x in ℤp.
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.
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.
Use this fact to compute a list of all irreducible polynomials of degree 2, 3, or 4 over ℤ2.