Fall 2007 Final
Student-provided questions and solutions to the December 2007 final exam. Examiner: Eyal Goren; associate examiner: John Labute.
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 $S_{17}$ has elements of order:
(a) 19 and 66.
(b) 3 and 19.
(c) 3 and 66.
(c). You can't make 19 ... there are no numbers $x, y \leq 17$ such that $\text{lcm}(x, y) = 19$, because 19 is prime.
1.1.1Accuracy and discussion¶
Pretty sure
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$
The answer is (b)
1.2.1Accuracy and discussion¶
^
1.3Question 3¶
Any two groups with 6 elements are isomorphic. Yes or no?
No
1.3.1Accuracy and discussion¶
1.4Question 4¶
$3^{144}$ is congruent to
(a) $1 \pmod{13}$
(b) $2\pmod 5$
(c) $1 \pmod{11}$
Well, by FLT, $3^{12} = 1$, so $3^{144} = 3^{12 \times 12} = (3^{12})^{12} = 1^{12} = 1$ so (a) lol
1.4.1Accuracy and discussion¶
Wolfram Alpha confirms.
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.
1.5.1Accuracy and discussion¶
1.6Question 6¶
Let $G$ be a group and $H$ a subgroup of $G$. Define a relation on elements of $G$ by saying that $a \sim b$ if $b^{-1}a \in H$. This relation is:
(a) reflexive and transitive, but transitive only if $G$ is abelian.
(b) reflexive and transitive, but symmetric only if $G$ is abelian.
(c) reflexive, symmetric, and transitive.
Let's investigate all the possible properties. Is it reflexive? Do we have that $a \sim a$? Well, $a^{-1}a = e$, and $e \in H$ because $H$ is a subgroup, so it is reflexive. (We already knew it was reflexive from the format of the question but it's nice to verify it anyways.) Is it symmetric? Well, $a \sim b$, then $\alpha b^{-1}a \in H$, and since $H$ is a subgroup, the inverse of $\alpha$ is also in $H$. So $\alpha^{-1} = (b^{-1}a)^{-1} = a^{-1}(b^{-1})^{-1} \in H$. But this just means that $b \sim a$.
Now let's look at transitivity. If $a \sim b$, then $\alpha = b^{-1}a \in H$, and if $b \sim c$, then $\beta = c^{-1}b \in H$. What can we then deduce about $c^{-1}a$? Well, $\beta \alpha \in H$ by closure, and $\beta\alpha = c^{-1}bb^{-2}a = c^{-1}a$ so yeah it's transitive whether or not $G$ is abelian.
So, (c).
1.6.1Accuracy and discussion¶
For showing that the relation is symmetric iff $G$ Abelian, how about this: If $a\sim b$, $b^{-1}a \in H$. Then by definition of a subgroup $(b^{-1}a)^{-1} = ba^{-1}\in H$. If $G$ abelian, this is equal to $a^{-1}b \in H$, so $b \sim a$. So if $G$ abelian the relation is symmetric. - @ikones
Nice catch, although I don't think $G$ even has to be abelian: http://crazyproject.wordpress.com/2010/03/22/alternate-characterization-of-cosets-as-equivalence-classes/ - @dellsystem
1.7Question 7¶
Let $p$ be prime number. Any two groups of order $p$ are isomorphic.
Yes.
1.7.1Accuracy and discussion¶
1.8Question 8¶
Transitive actions. Ignore.
1.9Question 9¶
The units of the ring $\mathbb C[\epsilon]$ are
(a) $\mathbb C \setminus \{0\}$.
(b) $\{a + b\epsilon: a, b \in \mathbb C, a \neq 0\}$.
(c) $\{1\}$.
(d) $\{b\epsilon: b\in \mathbb C, b \neq 0\}$.
A unit is an element with a multiplicative inverse. Some examples of elements with multiplicative inverses: 1, $1 + \epsilon$ (the inverse is $1 - \epsilon$). Some elements that don't have multiplicative inverses: $\epsilon$. Right away we can rule out (c) (since $1+\epsilon$ is a unit) and (d) (since $\epsilon$ is not a unit). So that leaves (a) and (b). (a) is obviously smaller than (b), and (a) doesn't include $1+\epsilon$ so it must be (b).
1.9.1Accuracy and discussion¶
Apparently I'm right? Dual number on Wikipedia
1.10Question 10¶
Let $B$ be a subset of two sets, $A_1$ and $A_2$. If $|A_1 \setminus B| = |A_2 \setminus B|$, then the statement $|A_1| = |A_2|$ is:
(a) always true.
(b) true if $A_1, A_2$ are finite, but need not be true in general.
(c) may be false even of $A_1, A_2$ finite.
(a) I think?
1.10.1Accuracy and discussion¶
I don't know!
1.11Question 11¶
Let $p \neq q$ be positive prime numbers. Let $r$ be the number of solutions for the equation $x^3 = 1$ in the ring $\mathbb Z/pq\mathbb Z$. Then:
(a) $r \leq 3$.
(b) $r \leq 6$.
(c) $r \leq 9$.
(d) $r$ can be arbitrarily large.
We're looking for the number of solutions to $x^3 = 1$. It's definitely not (a) or (b) - for example, if $p = 13$ and $q = 7$, then there are 9 solutions, according to Wolfram Alpha. In fact, I'm pretty sure that (c) is the answer. According to a paper I found called Number of Solutions of the Congruence $x^m = r \pmod n$ (it's on jstor so if you're not on a campus Internet connection, you'll have to log in using your McGill credentials), the number of solutions is (in this particular case) limited to $3 \times 3 = 9$. If the equation were instead $x^2 = 1$, the number of solutions would be limited to $2 \times 2$, and if it were $x^4 = 1$, it would be limited to $4 \times 4$. Now, if instead of just $p$ and $q$ we had $p$, $q$, and $r$, all positive primes, then it would be $\alpha^3$ where $\alpha$ is the exponent for $x$.
As an example, I will estimate the number of solutions to $x^3 = 1 \pmod{3763}$, where $3763 = 53 \cdot 71$, both of which are prime. The formula is $\gcd(3, 52) \cdot \gcd(3, 70)$ (see the paper). Well, neither 52 nor 70 is divisible by 3, so we have $1 \cdot 1 = 1$. And indeed, Wolfram Alpha confirms that there is one solution.
Another example: $x^3 = 1 \pmod{559}$, where $559=13\cdot 43$, both of which are prime. Well, $\gcd(3, 12) = 3$, and $\gcd(3, 42) = 3$, so the number of solutions is $3 \cdot 3 = 9$. And you know what? It's true!
(I don't think we learned exactly how to do this in class, and it's not that useful in general, so this is mostly an interesting aside. We probably learned some general things about congruences that would have allowed us to solve this question, but I must have missed that class.)
1.11.1Accuracy and discussion¶
Prove me wrong, I dare you
1.12Question 12¶
Consider the following list of principal ideals $(2), (3), (5), (6)$ in the ring $\mathbb Z/14 \mathbb Z$. There are
(a) Only one ideal in this list.
(b) Two distinct ideals in this list.
(c) Three distinct ideals in this list.
(d) Four distinct ideals in this list.
Let's quickly sketch each ideal:
$(2) = \{0, 2, 4, 6, 8, 10, 12\}$
$(3) = \{0, 3, 6, 9, 12, 1, 4, 7, 10, 13, 2, 5, 8, 11\}$ (so the entire ring)
$(5) = $ same as above because 5 and 14 and relatively prime
$(6) = \{0, 6, 12, 4, 10, 2, 8\}$ so same as (2)
The answer is (b).
1.12.1Accuracy and discussion¶
Feels right to me, could use confirmation though
2Part B: Short-answer questions¶
2.1Question 1¶
Ignore
2.2Question 2¶
(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) Find all the solutions for the equation $x^2 = -1$ modulo $17 \cdot 37$. The final answer should be given as congruence classes modulo $17 \cdot 37 = 629$.
(a) This is the same as question 3 (a) on fall 2006 final.
(b) First, we solve $x^2=-1 \pmod{17}$. The first few multiples of 17 are: 17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187. Well, $x=4$ works (nothing less than 4 can work). 5, 6, 7, 8, 9, 10, 11, 12 don't work. 13 does work - 169 is 170-1. So the congruence classes that work are $[4], [13]$.
Now for $x^2=-1\pmod{37}$. Oh god, this is a lot longer. I guess you just have to be good at mental math (unless there's a nicer trick to it). Well, the first few multiples are: 37, 74, 111, 148, 185, 222, 259, 296, 333, 370. The first one that works is 6. 18 doesn't work. 19 is just -18, so nothing greater than 19 can work except 31 which is equal to -6. So the congruence classes that work are $[6], [31]$. (Actually, we didn't even have to check 13 for the previous one - we know it works because $13^2 = (-4)^2 = 4^2$.)
Then, we just need to combine them somehow. Let's write out all the terms for each equivalence class:
[4] = 4, 21, 38, 55, 72, 89, 106, 123, 140, 157, 174, 191, ...
[13] = [-4] = 13, 30, 47, 64, 81, 98, 115, 132, 149, 166, 183, 200, 217, 234, 251, 268, 285, 302, 319, ...
[6] = 6, 43, 80, 117, 154, 191, 228, 265, 302, ...
[31] = [-6] = 31, 68, 105, 142, 179, 216, 253, 327, 364 ...
Now let's try to find terms that appear in one of the top lists as well as in one of the bottom lists. [191] shows up in [4] and [6] so that's good. [302] shows up in [13] and [6]. That seems like it. Of course, we also have 629 - 191 = 438 and 629 - 302 = 327. So the congruence classes are $[191], [302], [327], [438]$.
2.2.1Accuracy and discussion¶
Checked computationally. Not sure how you would know a priori that you've found all the congruence classes, though. Also, there is probably a more elegant way of doing this.
2.3Question 3¶
(a) Let $f \in \mathbb F[x]$ be an irreducible polynomial with coefficients in a field $\mathbb F$ and of degree $\geq 1$. Let $L = \mathbb F[x] / (f(x))$. Prove that $L$ is a field. You may assume that $L$ is a commutative ring.
(b) Let $\mathbb F$ now be the field of five elements $\mathbb Z / 5\mathbb Z$ and let $f(x) = x^2+2x-1$. Prove that $f$ is irreducible.
(c) Find a square root of 2 in $L$. Call it $t$.
(d) Consider the map $\alpha: \mathbb F[x] \to L$, given by $x \mapsto t$. Prove that this is a ring homomorphism.
(e) Find the kernel of $\alpha$.
(f) Prove that $\alpha$ induces an isomorphism. ($\mathbb F[x] /(x^2-2) \cong L$)
(a) This is the same as question 4 (a) on the 2006 final.
(b) $f$ has degree 2, so for it to be reducible, it must have 2 linear factors. Since $\mathbb F$ has 5 elements, there are 5 possible linear factors: $x-0$, $x-1$, $x-2$, $x-3$, $x-4$. For $x-0$ to be a linear factor, it must be that $f(0) = 0$ (by the relationship between linear factors and roots of a polynomial). But $f(0) = 0^2+2\cdot 0 - 1 = -1 = 4$, so that is not true. Also, $f(1) = 1^2 + 2\cdot 1 - 1 = 2$, $f(2) = 2^2+2\cdot 2 - 1 = 7 = 2$, $f(3) = 3^2 + 2\cdot 3 - 1 = 14 = 4$, and $f(4) = 4^2 + 2\cdot 4 - 1 = 24-1 = 23 = 3$. So none of the possible linear factors in this field are factors of $f$, which means that $f$ is irreducible. $\blacksquare$
(c) Assuming that we're using the field and irreducible polynomial mentioned in part (b) (which seems like a reasonable assumption), then we just need to solve the congruence $t^2 = 2 \pmod{x^2+2x-1}$. Well, if $t^2 = x^2+2x+1 = (x+1)^2$, then $t = (x+1)$ would work.
(d) We need to check that $\alpha(u + v) = \alpha(u) + \alpha(v)$ and that $\alpha(uv) = \alpha(u) \cdot \alpha(v)$ for any $u, v \in \mathbb F[x]$. Well, anything in $L$ can be written in the form $ax + b$ (since $f$ is of degree 2). Anything in $\mathbb F$ can be written in the form $c_nx^n + c_{n-1}x^{n-1} + \ldots + c_0$, with $n$ being some natural number and the $c$'s coming from the field. So if $u = u_nx^n + u_{n-1}x^{n-1} + \ldots + u_0$ and $v=v_nx^n + v_{n-1}x^{n-1} + \ldots + v_0$, then what? ???
Later.
2.3.1Accuracy and discussion¶
(a) See the other final.
(b) Not sure if this answer is sufficient to prove irreducibility.
(c) Looks ok
(d) Don't know