Fall 2009 Final

Student-provided solutions to the December 2009 final exam. Examiner: Eyal Goren; associate examiner: James Loveys.

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 I: Multiple-choice questions¶

1.1Question 1¶

Same as December 2007, question 1. The answers have been rearranged.

1.2Question 2¶

Same as December 2007, question 6. The answers have been rearranged.

1.3Question 3¶

Same as December 2007, question 2. The answers have been rearranged.

1.4Question 4¶

Same as December 2007, question 5.

1.5Question 5¶

Group actions. Ignore.

1.6Question 6¶

Same as December 2007, question 10. The answers have been rearranged.

1.7Question 7¶

Let $A, B, C$ be sets. Then $(A\cup B) \setminus (B \setminus C)$ is equal to:

(a) $(A \cap C) \cup B)$
(b) $(A \cup B \cup C) \setminus (A \cap B \cap C)$
(c) $(A \cup B) \setminus (B \cap C)$
(d) $(A \setminus B) \cup (B \cap C)$.

Draw the diagram. It looks like this:

(a) is obviously wrong because the rest of $A$ is neglected, (b) is wrong because it includes the rest of $C$, (c) has to be wrong because it's so similar. It looks like it has to be (d). And you know what? It is!

1.7.1Accuracy and discussion¶

Pretty sure I'm right. Not confirmed though.

1.8Question 8¶

Same as December 2007, question 12. The answers have been rearranged.

1.9Question 9¶

$5^{91} \cdot (3^3 + 2)^{53}$ is congruent to:

(a) $10\pmod{19}$.
(b) $1 \pmod{19}$.
(c) $16\pmod{19}$.

Since we're working in mod 19, we'll need to make use of FLT: $a^{18} \equiv 1 \pmod{19}$. Now, $18 \times 5 = 90$, so $5^{91} = 5^{90 + 1} = 5^{90}\times 5 = 5^{18\times 5}\times 5 = (5^{18})^5\times 5 = 1^5 \times 5 = 5$. So we just get $5(3^3 + 2)^53$. Well, $3^3 = (3^2)\times 3 = 27 = 8$ in mod 19. So we have $5(8 + 2)^{53} = 5(10)^53$. Making use of FLT again, we have that $18 \times 3 = 54$, so $10^{53} = 10^{54} \times 10^{-1} = 10^{18\times 3} \times 10^{-1} = (10^{18})^3 \times 10^{-1} = 1 \times 10^{-1}$. Now, $x=10^{-1}$ is the inverse of 10 such that $10x = 1 \pmod{19}$. $x=2$ seems to work (is there a better method for finding this????), so the answer is just $5 \times 2 = 10$.

The answer is (a).

1.9.1Accuracy and discussion¶

Wolfram Alpha confirms.

2Part II: Short-answer questions¶

2.1Question 1¶

Let $\mathbb F$ be the field with 7 elements.

(a) Write all the squares and cubes in $\mathbb F$.
(b) Construct a field $\mathbb L$ with $7^2$ elements. Show that both the polynomials $x^2-3$ and $x^2+x-1$ can be solved in $\mathbb L$ and write down their solutions.
(c) Construct a field $\mathbb K$ with $7^3$ elements.
(d) (Bonus question) Show that the polynomial $x^2-3$ cannot be solved in $\mathbb K$.

First, we note that $\mathbb F = \mathbb Z/7\mathbb Z$, which has the elements $\{0, 1, 2, 3, 4, 5, 6\}$ (it is a field because all the non-zero elements have multiplicative inverses).

(a) What does this mean. Like, evaluate $a^2$ and $a^3$ for every $a$ in the field? If so:

(b) We need a irreducible polynomial of degree 2. Well, using the table above, we know that there is no solution to $x^2 = 3 \pmod 7$. So, $x^2-3$ should be irreducible. We can construct a field $\mathbb L$ by taking the quotient of $\mathbb F$ and $(x^2-3)$ (the ideal generated by that irreducible polynomial). Then $\mathbb L = (\mathbb Z/7\mathbb Z)/(x^2-3)$. Clearly, $x^2-3$ can be solved in $\mathbb L$, since $x^2-3 = 0\pmod{x^2-3}$, lol. As for $x^2+x-1$, well, this is just $(x^2-3) + (x+2)$, so we need to solve $x+2 = 0 \pmod{x^2-3}$. But $x = 5$ works.

(c) We need an irreducible polynomial of degree 3. Using, again, the table above, we know that there is no solution to $x^3 = 2 \pmod 7$. So $x^3-2$ should be irreducible. So our field is $\mathbb K = (\mathbb Z/7\mathbb Z)/(x^3-2)$. Do we need to prove that this has $7^3$ elements??

(d) To show that $x^2-3$ cannot be solved, we need to show that it is irreducible. But it obviously is. $\blacksquare$

2.1.1Accuracy and discussion¶

(a) I think it's right. The table at least should be correct, I checked it. - @dellsystem

It's kind of right. He's asking for numbers that can be written as squares or cubes, I'm pretty sure at least. So I guess it would be 1, 2, 4, and 6. - @ikones

Good enough - @dellsystem

(b) Should be ok, unless we need to prove it

(c) ^

(d) jk

2.2Question 2¶

(a) Same as December 2007, question 2 (a).
(b) Find all the solutions to the polynomial equation
$$x^2+x+11 \equiv 0 \pmod{221}$$
(The final answer should be given as congruence classes modulo 221. Note that $221=13\times 17$.)

(b) First, let's solve this mod 13. It's true for 1, not 2-10, yes 11, not 12 (or 13). So the congruence classes are [1] and [11].

Then, for 17, it's true for 2, not 3-13, yes 14, no for the rest. So [2] and [14]. Could we use the quadratic equation for this? Would it be faster, considering that we need to find inverses (instead of dividing)?

Now, let's write down the possibilities (numbers that appear in both halves are highlighted):

[1]: 1, 14, 27, 40, 53, 66, 79, 92, 105, 118, 131, 144, 157, 170, 183, 196, 209
[11]: 11, 24, 37, 50, 63, 76, 89, 102, 115, 128, 141, 154, 167, 180, 193, 206, 219
[2]: 2, 19, 36, 53, 70, 87, 104, 121, 138, 155, 172, 189, 206
[14]: 14, 31, 48, 65, 82, 99, 116, 133, 150, 167, 184, 201

So the final answer is [14], [53], [167], [206]. I don't know an elegant method of coming up with this though.

2.2.1Accuracy and discussion¶

Wolfram Alpha confirms the final answer. Still not sure about the correct method.

2.3Question 3¶

Prove Lagrange's theorem: Let $G$ be a finite group and $H$ a subgroup of $G$ then the number of elements of $H$ divides that of $G$.

Let's look at the set of left cosets of $H$: $\{aH: a \in G\}$. Now, $G$ is a disjoint union of these cosets, as cosets form equivalence classes under the equivalence relation defined by $x \sim y$ iff $xy^{-1} \in H$ (equivalent to defining it as $xh = y$ for some $h \in H$). We can verify this fairly easily:

Reflexivity: $x \sim x$ as $xx^{-1} = e \in H$. $\checkmark$
Transitivity: $x \sim y$ means $xy^{-1} \in H$, $y \sim z$ means $yz^{-1} \in H$, and so $(xy^{-1})(yz^{-1}) = x(y^{-1}y)z = xez = xz \in H$ which means that $x \sim z$. $\checkmark$
Symmetry: $x \sim y$ so $xy^{-1} \in H$. Since $H$ is a subgroup, the inverse of $xy^{-1}$ must also be in $H$. But $(xy^{-1})^{-1} = yx^{-1}$ which shows that $y \sim x$. $\checkmark$

Now, we need to show that each coset $aH$ has exactly the same cardinality as $H$, for if that is true, then the cardinality of $G$ is simply the cardinality of any coset times the number of cosets (proving that the cardinality of a subgroup divides the cardinality of $G$). To do this, we create a bijection from $H$ to an arbitrary coset $aH$, defined by $f(h) = ah$ (where $h \in H$ and $a$ is given). We can verify that this is bijective as follows. First, surjectivity: if $g \in aH$, then there exists an $h \in H$ such that $f(h) = ah = g$, by definition; this shows that $f$ is surjective. Injectivity: if $f(u) = f(v)$, then $au = av$ and then if we multiply both sides by $a^{-1}$, we have that $u = v$. $\blacksquare$

Alternatively, we could show bijectivity by producing the following inverse for $f$: if $g \in aH$, then there exists $h \in H$ such that $ah = g$; consequently, $h = a^{-1}g$ and so $f(g) = a^{-1}g = h$, which is in $H$. So $f^{-1}(x) = a^{-1}x$.

2.3.1Accuracy and discussion¶

Theorem 28.2.1 in the notes. Also on ProofWiki. This was pretty useful as well: http://www.mathstore.ac.uk/headocs/Brown_WorkbookCosetsLagrangeTheorem.pdf