Fall 2006 Final

Student-provided (and sometimes TA-verified) questions and solutions to the December 2006 final exam. Examiner: Eyal Goren; associate examiner: Henri Darmon.

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.

1Part A: Multiple-choice questions¶

1.1Question 1¶

The group of permutations of five elements, $S_5$, has an element of order 7. Yes or no?

No. You would need one element of order 7, or two elements whose orders' lcm is 7. But the max order of an element is 5, for obvious reasons, and 7 is prime so yeah.

You could, however, have an element of order 6. For example: $(12)(345)$ has order 6, since lcm$(2, 3) = 6$.

1.1.1Accuracy and discussion¶

Solution given during the tutorial on Friday, November 30.

1.2Question 2¶

The $\gcd$ of the polynomials $f(x) = x^4 + 5x + 1$ and $g(x) = x^2-1$ in $\mathbb Z/7\mathbb Z [x]$ is:

(a) $x^2-1$
(b) $x-1$
(c) $1$
(d) $x+1$

Run the Euclidean division algorithm as follows:

$$\begin{align*} x^4+5x+1 & = (x^2-1) \cdot(x^2 + 1) + (5x-5) \tag{as $5x+2 = 5x-5$}\\ x^2-1 & = (5x-5)(3x + 3) + 0\tag{as $15x^2 - 15x + 15x - 15 = x^2 -1$} \\ \end{align*}$$

Therefore, $x-1$ is the gcd (since we use the monic version by convention), so (b).

1.2.1Accuracy and discussion¶

Well, $x+1$ does indeed divide both: $(x-1)(x^3+x^2+x-1) = x^4 - 2x + 1 = x^4 + 5x + 1$, and $(x-1)(x+1) = x^2-1$. And $x^2-1$ and $x+1$ do not seem to divide the larger polynomial. Not really sure to confirm this though (Wolfram Alpha doesn't seem to handle computing the gcd in $\mathbb Z /n\mathbb Z$ very well).

1.3Question 3¶

Any two groups with 6 elements are isomorphic. Yes or no?

No. $S_3$ and $\mathbb Z/6\mathbb Z$ both have 6 elements, but because one is Abelian and the other is not, they are not isomorphic.

1.3.1Accuracy and discussion¶

Solution given during the tutorial on Friday, November 30.

1.4Question 4¶

The ring $\mathbb Q[x]/(x^3-1)$ is a field. Yes or no?

No, because $x^3-1$ is reducible in $\mathbb Q[x]$ (just $(x-1)(x^2+x+1)$ - if you can't see that right away, just note that $x=1$ is clearly a root, so $(x-1)$ is clearly a factor, which means it's reducible).

1.4.1Accuracy and discussion¶

pretty sure

1.5Question 5¶

Let $n \geq 1$ be an integer. Every homomorphism of groups $f: \mathbb Z / n \mathbb Z \to \mathbb Z$ is the zero homomorphism. Yes, no, or depends on $n$?

Yes. (The zero homomorphism is the one whose kernel is equal to $\mathbb Z/n\mathbb Z$ itself, i.e., every element is mapped to the identity element in $\mathbb Z$, which happens to be 0.) Consider the homomorphism $f: \mathbb Z / n \mathbb Z \to \mathbb Z$. Let $a = f(1)$. Then, we have:

$$f(n) = f(\underbrace{1 + \ldots + 1}_{n \text{ times}}) = \underbrace{f(1) + \ldots + f(1)}_{n \text{ times}} = \underbrace{a + \ldots + a}_{n \text{ times}} = na$$

Now, since it's a homomorphism, we know that $f(0) = 0$. But $n \equiv 0$ in the domain, and so we have that $f(n) = na = f(0) = 0$. But that means that $na = 0$. Since $n \neq 0$, then it must mean that $a = 0$! (Since $\mathbb Z$ is, of course, an integral domain.) So any element in the domain is mapped to 0. But this is the definition of the zero homomorphism.

1.5.1Accuracy and discussion¶

Solution given during the tutorial on Friday, November 30.

1.6Question 6¶

$2^{144}$ is congruent to:

(a) $1 \pmod{13}$
(b) $2 \pmod{5}$

I love these questions. Well, 144's prime divisors are 3 and 4 ($144 = 12 \cdot 12 = 3^2\cdot 4^2$). Let's assume that (a) is true for now (because it is, lol). Then $2^{144} = (2^{12})^{12}$. But by FLT, $2^{12} \equiv 1 \pmod{13}$. Then $2^{144} \equiv 1^{12} \equiv 1 \pmod{13}$. So (a). That worked out nicely.

1.6.1Accuracy and discussion¶

Wolfram Alpha confirms that it's congruent to 1 in mod 13. Incidentally, it's also congruent to 1 in mod 5.

1.7Question 7¶

Let $G$ be a group. The relation on $G$ defined by "$a \sim b$ if there exists $g \in G$ such that $gag^{-1} = b$" is an equivalence relation. Yes or no?

Yes.

1.7.1Accuracy and discussion¶

Solution given during the tutorial on Friday, November 30. The proof that this is an equivalence relation was given during the tutorial on Friday, November 23.

1.8Question 8¶

Some question about transitive groups

Don't think we need to know this, or we just haven't learned it yet or something

1.9Question 9¶

Let $G$ be a group and $a, b\in G$ be two elements of order 2, i.e., $a^2 = e$ and $b^2=e$. Then $(ab)^2=e$. Yes or no?

No. $(ab)^2 = abab$, and $a^2b^2 = aabb = 1$. So $(ab)^2 = aabb$ IF we know that $ab = ba$, i.e., if the group is Abelian. So this property is only true for Abelian groups, not for groups in general.

1.9.1Accuracy and discussion¶

Solution given during the tutorial on Friday, November 30.

2Part B: Short-answer questions¶

2.1Question 1¶

Unlikely to be asked (about the Cauchy-Frobenius formula, and orbits)

2.2Question 2¶

Unlikely to be asked (about roulette/necklace permutations)

2.3Question 3¶

(a) Let $m, n$ be relatively prime positive integers. Prove the Chinese Remainder Theorem: $\mathbb Z/(mn)\mathbb Z \cong \mathbb Z / m \mathbb Z \times \mathbb Z /n \mathbb Z$ (isomorphism of rings).
(b) State the analogous theorem for the ring of polynomials $\mathbb F[x]$, where $\mathbb F$ is a field.

(a) To prove that $\mathbb Z/(mn)\mathbb Z$ and $\mathbb Z / m \mathbb Z \times \mathbb Z /n \mathbb Z$ are isomorphic, we define the following function $f: \mathbb Z/(mn)\mathbb Z \to \mathbb Z / m \mathbb Z \times \mathbb Z /n \mathbb Z$, such that $f(a) = (a \pmod m, a \pmod n)$.

This function is a ring homomorphism, which we will now proceed to show (it's pretty easy):

(1) Identity: $f(1) = (1 \pmod m, 1 \pmod n) = (1_{\mathbb Z / m \mathbb Z}, 1_{\mathbb Z / n \mathbb Z})$ $\checkmark$
(2) Addition: $f(a + b) = ((a+b) \pmod m, (a+b) \pmod n) = (a \pmod m, a \pmod n) + (b \pmod m, b \pmod n) = f(a) + f(b)$ $\checkmark$
(3) Multiplication: $f(ab) = ((ab) \pmod m, (ab) \pmod n) = (a \pmod m, a \pmod n) \cdot (b \pmod m, b \pmod n) = f(a) \cdot f(b)$ $\checkmark$

Now, to show that it's injective, we need to show that $f(x) = 0$ implies that $x = 0$. Well, $f(x) = (x \pmod m, x \pmod n)$, and 0 in the image would be $(0, 0)$, which means that $x \pmod m = 0$ and $x \pmod n = 0$ - that is, $x$ is a multiple of $m$ as well as a multiple of $n$. But then, since $m$ and $n$ are relatively prime, $x$ must also be a multiple of $mn$, which means that $x = 0 \pmod{mn}$. So the function is injective.

Lastly, we need to show that it's surjective by finding $x$ such that $f(x) = (a\pmod m, b\pmod n)$ for any $a, b \in \mathbb Z$. So we need to find an $x$ such that $x = a \pmod m$ and $x = b \pmod n$. Well, we know that $m$ and $n$ are relatively prime, i.e., $\gcd(m, n) = 1$. Using the basic properties of the gcd, we know that there exist integers $u, v$ such that $um + vn = 1$. Consider $x = bum + avn$. What is this mod m? Well, since $m = 0 \pmod m$, $bum = 0 \pmod m$ and so $x = avn \pmod m$. But we know that $aum + avn = a$ (from multiplying a previous equation by $a$), which means that $avn = a - aum$, and so $x = a - aum = a \pmod m$ (since $aum = 0 \pmod m$). Similarly, we have that $x = b \pmod n$. So $f$ is indeed surjective, and thus must be an isomorphism, which concludes the proof that $\mathbb Z/(mn)\mathbb Z \cong \mathbb Z / m \mathbb Z \times \mathbb Z /n \mathbb Z$.

(b) $\mathbb F[x] / (fg) \cong \mathbb F[x] / (f) \times \mathbb F[x]/(g)$ if $f, g$ are two non-constant polynomials with $\gcd(f, g) = 1$.

2.3.1Accuracy and discussion¶

(a) Theorem 23.3.1 in the notes. The proofs I used for surjectivity and injectivity differ from those used in the notes, mostly because using the first isomorphic theorem isn't quite intuitive for me yet. I followed the basic idea used here: http://mathforum.org/library/drmath/view/73205.html.

(b) Exercise 12 in section 25 (under ring theory) states it and asks us to prove it.

2.4Question 4¶

Let $f \in \mathbb F[x]$ be an irreducible polynomial with coefficients in $\mathbb F$ and of degree $\geq 1$.

(a) Prove that $L = \mathbb F[x]/(f)$ is a field.
(b) Prove that $f$ has a root in $L$.

(a) We already know that $\mathbb F[x]/(f)$ is a commutative ring, since $F[x]$ is a field and has a unit element (1). So we have to show that every non-zero element has an inverse, and that $[0] \neq [1]$. Well, we know the the latter is true because $f$ is irreducible, and thus is not constant, so $1 = 1 - 0 \notin (f)$. To show the former, let $g$ be any non-zero element in the quotient ring. Since $f$ is irreducible, $g$ does not divide $f$, and $f$ does not divide $g$ because $g$ is non-zero. So, we have that $\gcd(f, g) = 1$. Then, by the properties of the gcd, there exist $u, v \in \mathbb F[x]$ such that $uf + vg = 1$. But $uf = [0]$ in the quotient ring. So then $kv = 1$, which shows that any non-zero polynomial has an inverse. This suffices to prove that $L$ is a field.

(b) Well, $x$ is a root because $f(x) \equiv 0 \pmod{f(x)}$, lol

2.4.1Accuracy and discussion¶

(a) Theorem 22.1.2 in the text. This was also useful: http://people.virginia.edu/~mve2x/3354_Fall2010/lecture27.pdf

(b) Mentioned during the tutorial on Friday, November 30.

2.5Question 5¶

(a) Prove that there are infinitely many prime numbers.
(b) Prove that every positive integer is a product of prime numbers. (Note: no need to prove uniqueness. Also, this doesn't require part (a).)

(a) The easiest proof is by contradiction. We assume that there is a finite number of primes, which can be enumerated (in ascending order) as $A = \{a_1, a_2, \ldots a_n\}$. Let $N$ be the product of all these numbers: $N = a_1 \times a_2 \times \ldots \times a_n$. Consider $N'=N+1$. Well, clearly none of the primes can evenly divide $N'$ - there will always be a remainder of 1. But that means $N'$ is prime. Then, we get a contradiction, because $A$ was supposed to be a complete list of primes, and yet $N'$ - which is a prime - is not in $A$ (since $N' > a_n$, and the list is in ascending order). We can conclude, then, that there are infinitely many primes.

(b) This proof uses the well-ordering property of the natural numbers in a proof by contradiction. Suppose that there are positive integers that can not be written as a product of primes. We represent these integers in the set $S$. By the well-ordering property, $S$ must have a minimal element (since it is not empty). We can denote this element by $n_0$. Now, $n_0$ cannot be prime, or equal to 1, because those can be trivially written as the product of primes. So $n_0$ must be composite - that is, there must exist two integers $s, t \in \mathbb N$ such that $1 < s, t < n_0$ with $n_0 = st$. Now, $s$ and $t$ cannot be in $S$, because they are less than $n_0$ and we chose $n_0$ to be the least element of $S$. So $s$ and $t$ can be written as the product of primes. We write $s$ as $s = q_1\ldots q_a$ and $t$ and $t = p_1\ldots p_b$ (where the $q$s and $p$s are all primes).

But then we can write $n_0 = st = q_1 \ldots q_a p_1 \ldots p_b$, which is a product of primes. This contradicts our original premise that $n_0$ cannot be written as a product of primes, by virtue of belonging to $S$. Consequently, $S$ must be empty, meaning that there are no positive integers that cannot be written as product of primes.

2.5.1Accuracy and discussion¶

(a) See the lecture notes for Monday, September 24 (Euclid's theorem).

(b) See the lecture notes for Monday, September 24 (The existence property).

2.6Question 6¶

(a) State and prove the first isomorphism theorem for groups.
(b) Prove that there is no surjective homomorphism $S_3 \to \mathbb Z /3\mathbb Z$.

(a) Let $f$ be a surjective homomorphism $f: G \to Q$, where $H = \ker(f)$. Then there is an isomorphism from the quotient $G/H$ to $Q$.

Proof: Recall that the quotient $G/H$ consists of all the left cosets of $H$. We construct the following function $g: G/H \to Q$: $g$ maps any left coset $aH$ to $f(a)$. We need to show that $g$ is (1) well-defined; (2) a group homomorphism; and (3) bijective.

(1) If $aH = bH$, then $b^{-1}aH = b^{-1}bH = eH$ and so $f(b^{-1}a) = e$. Then, $f(b) = f(b)f(b^{-1}a) = f(bb^{-1}a) = f(a)$. So then $g(aH) = g(bH)$. $\checkmark$

(2) $g(aH \cdot bH) = g((ab)H)$ (from the definition of coset multiplication) $ = f(ab) = f(a)f(b)$ (since $f$ is a homomorphism) $ = g(aH) \cdot g(bH)$. $\checkmark$

(3) Injectivity: let $aH \in \ker(g)$ such that $g(aH) = e$. Then $f(a) = e$, and so $a$ is in the kernel of $f$, that is $H$. But then $aH$ must be the identity in $G/H$, proving that the kernel of $g$ is trivial and so the function is injective. Surjectivity: since $f$ is surjective, given $q \in Q$, we can find $a \in G$ such that $f(a) = q$. But then $F(a) = f(a) = q$. So $g$ is surjective.

(b) We can do a proof by contradiction. We assume that there is a surjective homomorphism. Then, by the first isomorphism theorem, there is a normal subgroup $N$ in $S_3$ such that $S_3/N \cong \mathbb Z / 3\mathbb Z$. Recall that any normal subgroup is a union of conjugacy classes. What are the conjugacy classes in $S_3$? We have $\{e\}$, $\{$the 2-cycles$\}$ (there are 3 of them), and $\{$the 3-cycles$\}$ (there are two).

Now, $S_3$ has 6 elements, and $\mathbb Z / 3\mathbb Z$ has 3 elements, so $N$ must have 2 elements. But can you make a normal subgroup with only 2 elements? Well, no, because you need the identity, so there's only room for one other element. But there is no other conjugacy class that has one element. So there is no way to form a normal subgroup of 2 elements.

From this we can conclude that there is no surjective homomorphism from $S_3$ to $\mathbb Z / 3\mathbb Z$.

2.6.1Accuracy and discussion¶

(a) Theorem 33.3.1 in the text. Also briefly mentioned during lecture on Friday, November 30 (the proof was left as an exercise).

(b) Explained during the tutorial on Friday, November 30.