Wikinotes

Maintainer: admin

Student-provided questions and solutions to the December 2005 final exam. Examiner: Henri Darmon; associate examiner: Daniel Wise.

It is recommended that you do this exam yourself before checking the solutions provided here. If you notice any errors with the content on this page, feel free to either contact @dellsystem or edit the page directly.

Let $\mathbb N = \{0, 1, 2, \ldots \}$ be the set of non-negative integers and let $f: \mathbb N \times \mathbb N \to \mathbb N$ be the function defined recursively by the rule
$$f(a, 0) = a, \quad f(a, b+1) = f(a, b) + 1, \quad \text{for all }a, b \in \mathbb N.$$
Show that $f$ satisfies
$$f(f(a, b), c) = f(a, f(b, c)),$$
for all $a, b, c \in \mathbb N$. (Hint: Use induction on $c$.)

In the base case, we have $c = 0$. So: $f(f(a, b), c) = f(f(a, b), 0) = f(a, b) = f(a, f(b, 0)) = f(a, f(b, c))$ $\checkmark$.

Now we assume that it holds for $c = n$ and attempt to prove it for $c = n+1$. $f(f(a, b), c) = f(f(a, b), n + 1) = f(f(a, b), n) + 1 = f(a, f(b, n)) + 1$ (by the induction hypothesis) $ = f(a, f(b, n) + 1) = f(a, f(b, n+1)) = f(a, f(b, c))$ $\checkmark$

I might rewrite it at some point using align to make it clearer.

Solve each of the following congruence relations.
(a) $2x=1 \pmod{101}$
(b) $6x=5 \pmod{30}$
(c) $x^6=1\pmod 7$

(a) 101 is prime - to see that, note that it's not divisible by 3 (because the digits don't sum to 3), nor 5, nor 7 (because 98 is), nor 11 (because 110 is), nor 13 (because 91 is). So we can't use the Chinese Remainder Theorem. Instead, we can simply enumerate all the possibilities. We need to find $x$ such that $2x$ is equal to 102, or 203, or 304, or 405, or 506, etc. Well, we can skip the odd terms. And 304/2 = 152 which is of course just 51 + 101. So the answer is $[51]$.

(b) We could use the Chinese Remainder Theorem if we really wanted, but this is pretty clear even without it. Possibilities: 35, 65, etc. Well, that's obviously not possible. So there are no solutions. Another way to see that this is impossible: multiplying 6 by anything will result in an even number. But we need an odd number to solve this.

(c) I was going to just list out all the possibilities, but then I realised this is just an application of Fermat's Little Theorem. So of course every non-zero number works. The solution is: $[1], [2], [3], [4], [5], [6]$.

(a) Wolfram Alpha confirms.

(b) Wolfram Alpha confirms.

State and prove Fermat's Little Theorem.

Fermat's Little Theorem says that for all $a$, $a^p \equiv a \pmod p$ where $p$ is prime. If $\gcd(a, p) = 1$, this is equivalent to $a^{p-1} \equiv 1 \pmod p$.

To prove this, we first prove the following lemma: if $p$ is prime, then it divides the binomial coefficient $\displaystyle \binom{p}{k}$ for all $1 \leq k \leq p -1$. To see this, we expand the binomial coefficient as follows:

$$\binom{p}{k} = \frac{p!}{k!(p-k)!} = \frac{p \cdot (p-1) \cdot \ldots \cdot (p-k+1)}{k!}$$

Since the binomial coefficient is always an integer, the denominator must divide the numerator. Since $k < p$, the factorial of $k$ does not divide $p$. So it must divide the other part. But that means that the binomial coefficient is a multiple of $p$, since that is not cancelled out by the denominator. So $p$ must divide it, which proves the lemma.

Now we prove Fermat's Little Theorem itself using induction on $a \in \mathbb N$ (we can easily generalise the result to $\mathbb Z$ afterwards if need be). The base case, $a = 1$, is trivial, as $1^p \equiv 1 \pmod p$ is true for all prime $p$. For the induction hypothesis, we assume that it holds for $a =n$: $n^p \equiv n \pmod p$. For the induction step, we use the binomial theorem, which states that

$$(n+1)^p = n^p + \binom{p}{1} n^{p-1} + \binom{p}{2} n^{p-2} + \ldots + \binom{p}{p-1}n + 1$$

Now let's rearrange the terms so that the binomial coefficients are the only things on the right:

$$(n+1)^p - n^p - 1 = \binom{p}{1} n^{p-1} + \binom{p}{2} n^{p-2} + \ldots + \binom{p}{p-1}n$$

By the lemma above, we know that $p$ divides each binomial coefficient, and so it divides each term on the right. Consequently, we have:

$$p \mid \binom{p}{1} n^{p-1} + \binom{p}{2} n^{p-2} + \ldots + \binom{p}{p-1}n$$

from which we can conclude that

$$p \mid (n+1)^p - n^p - 1$$

Now, we know by the induction hypothesis that $p \mid n^p - n$. Then $p$ must also divide the sum of $n^p-n$ and $(n+1)^p - n^p - 1$, which is given by
$$n^p - n + (n+1)^p - n^p - 1 = (n+1)^p - n - 1 = (n+1)^p - (n+1)$$

Which tells us that $p \mid (n+1)^p - (n + 1)$, or, equivalently, that $(n+1)^p = (n+1) \pmod p$, which is exactly what we needed to prove, so this proof by induction is complete.

For negative numbers, we simply note that $(-a)^p = (-1)^pa^p = (-1)^p a \pmod p$. Then we just have to show that $(-1)^p = -1 \pmod p$. If $p > 2$, then $p$ is odd, and for odd $p$ we have that $(-1)^p = -1$. In the case that $p=2$, we have that $(-1)^2 = 1 = -1\pmod 2$. So this proves it for negative numbers.

For $a = 0$, the equality $0^p = 0 \pmod p$ is trivial.

See questions 9 and 10 for assignment 2 (link to solutions).

Prove that the ring $\mathbb R$ of real numbers and the ring $\mathbb Q$ of rational numbers are not isomorphic.

For the two rings to be isomorphic, there must exist a bijective ring homomorphism between them. But there does not exist a bijection from $\mathbb R$ to $\mathbb Q$, for the former is uncountable while the latter is countable.

For the real proof, one would probably need to use Cantor's diagonal argument or something along those lines.

List the powers $[x]^j$ (for $0 \leq j \leq 7$) of $[x] = x + (x^3 + x + 1)\mathbb Z_2[x]$ in the quotient ring $\mathbb Z_2[x]/(x^3+x+1)$. You should label each result by its unique representative of degree $\leq 2$. Using this calculation, write down the multiplicative inverse of $[x]$.

j	0	1	2	3	4	5	6	7
$[x]^j$	1	$x$	$x^2$	$x+1$	$x^2+x$	$x^2+x+1$	$x^2+1$	1

The inverse is $[x]^6$ (for $[x] \cdot [x]^6 = 1$.

I think it's accurate. Can't confirm though.

Give an example of two non-isomorphic rings of cardinality 16 that are non-commutative. (You should justify your answer and prove that these two rings are not isomorphic to each other.)

Give the definitions of: maximal ideal and prime ideal in a commutative ring $R$. Show that if $I$ is a maximal ideal then $R/I$ is a field.

Maximal ideal: a proper ideal $I$ (that is, $I \neq R$) is said to be maximal if, for any ideal $J$ with $I \subseteq J$, we have that either $J = I$ or $J = R$.

Prime ideal: an ideal $I$ is said to be prime if $ab \in I$ implies $a \in I$ or $b \in I$.

Proof: suppose that $I$ is a maximal ideal. If $1 \in I$, then $I = R$ so it must be that $1 \notin I$. Consequently, in $R/I$ we have that $[1] \neq [0]$. Since $R$ is commutative, so is $R/I$, so we just need to prove that every non-zero element $[a] \in R/i$ is invertible. Consider the ideal $(a, I) = (a) + I$ of $R$, where $[a]$ is a non-zero element in $R/I$. This means that $a \notin I$, which means this ideal strictly contains $I$. Since $I$ is maximal, any ideal strictly containing it must be the ring itself. So $(a) + I = R$, which means that for some $r \in R$ and $j \in I$, we have that $ar + j = 1$. Consequently, in $R/I$, since $j = 0$, we have that $[a][r] = 1$ and so $[r]$ is the inverse, proving that any non-zero element in $R/I$ is invertible. Consequently, $R/I$ must be a field.

Definitions: See Definition 24.0.10 in the notes.

Proof: See Theorem 24.0.11 (2) in the notes.

Write down the class equation for the symmetric group $S_5$ on 5 elements. (i.e., list all of the conjugacy classes in $S_5$, along with their cardinalities.) Use this to give a list of all the normal subgroups of $S_5$.

The identity. Cardinality: 1.
The 2-cycles. Representative: $(12)$. Cardinality: 10.
The 3-cycles. Representative: $(123)$. Cardinality: 20.
The 2-2-cycles. Representative: $(12)(34)$. Cardinlity: 15.
The 4-cycles. Representative: $(1234)$. Cardinality: 30.
The 2-3-cycles. Representative: $(12)(345)$. Cardinality: 20.
The 5-cyles. Representative: $(12345)$. Cardinality: 24.

The normal subgroups are: $S_5$, $\{e\}$, and the union of the classes consisting of an even number of cycles with even length (so the 3-cycles, the 2-2-cycles, the 5-cycles, and the identity).

See the last question on assignment 5 (link to solutions).

Show that the groups $\mathbb{GL}_2(\mathbb Z_2)$ and $S_3$ are isomorphic by constructing an isomorphism from one to the other.

Write down five non-isomorphic groups of order 8. (You do not need to show that these groups are non-isomorphic.)

$\mathbb Z/8\mathbb Z$, $\mathbb Z/2 \mathbb Z \times \mathbb Z/2 \mathbb Z \times \mathbb Z/2 \mathbb Z$, $\mathbb Z/2 \mathbb Z \times \mathbb Z/4 \mathbb Z$, the dihedral group $D_8$, the quaternion group (no idea what this is but it was mentioned during a tutorial).

http://en.wikipedia.org/wiki/List_of_small_groups

Show that there is no surjective homomorphism from $\mathbb Z_2[x]$ to the ring $\mathbb Z_2 \times \mathbb Z_2 \times \mathbb Z_2$.

Suppose there is a surjective homomorphism. Then $\exists a,b \in \mathbb{GL}_2(\mathbb Z_2)$ satisfying $\Phi(a) = \Phi(b) = c$, where $c$ is some element of $\mathbb Z_2 \times \mathbb Z_2 \times \mathbb Z_2$.

It follows that:
$\Phi(a) + \Phi(b) = 2c$¸
But all elements of $\mathbb Z_2 \times \mathbb Z_2 \times \mathbb Z_2$ are order 2, so $2c = 0$

By the definition of a homomorphism, addition is preserved, so we must also have:
$\Phi(a+b) = 2c = 0$

A homomorphism must also map zero to itself, so we conclude that $a + b = 0$.
$a$ must be the additive inverse of $b$, but we see that in $\mathbb Z_2[x]$ every element is its own additive inverse (try it).

Thus we conclude that $a = b$, a contradiction if $\Phi$ is surjective.

Should be fine.

Fall 2005 Final

1Question 1¶

1.1Accuracy and discussion¶

2Question 2¶

2.1Accuracy and discussion¶

3Question 3¶

3.1Accuracy and discussion¶

4Question 4¶

4.1Accuracy and discussion¶

5Question 5¶

5.1Accuracy and discussion¶

6Question 6¶

6.1Accuracy and discussion¶

7Question 7¶

7.1Accuracy and discussion¶

8Question 8¶

8.1Accuracy and discussion¶

9Question 9¶

9.1Accuracy and discussion¶

10Question 10¶

10.1Accuracy and discussion¶

11Extra credit¶

11.1Accuracy and discussion¶