Practice final

Student-provided solutions to the sample final created by Professor Darmon and made available here. The solutions shown below are student-provided and may or may not be accurate. To correct an error, feel free to edit the page directly or contact @dellsystem.

Instructor-provided solutions are available here.

1Question 1¶

Calculate $3^{10000000000000000000000000000000000001} \pmod{13}$.

1.1Solution¶

First, let $a = 10000000000000000000000000000000000001$. Clearly we need to use FLT here. Well, by FLT, $3^{12} \equiv 1 \pmod{13}$. Also, we know that $12 \times 833\ldots3$ (35 3's total) $= 99\ldots96$ (35 9's total). But that is equal to $a-5$.

Then, $3^a = 3^{12x + 5}$ (where $x = 833\ldots3$) $= 3^{12x} \cdot 3^5 = (3^{12})^x \cdot 3^5 = 1^x \cdot 3^5 = 3^5 = 243 = 9 \pmod{13}$.

So the answer is 9.

1.2Alternate Solution¶

First we can see that $3^3 \equiv 1 \pmod{13}$ (This can be done by square rooting $3^{12}$.)
n is divisible by 3 if and only if the sum of each digit is equal to a multiple of 3.
then $a - 2 = 9999.....99999$ is divisible by 3.
Then $3^a = 3^{3x + 2} = 3^{3x} 3^2 \equiv 1\cdot 9 \pmod{13}$

1.3Accuracy and discussion¶

Wolfram Alpha confirms! There might be a nicer way to do this though, my solution is kind of hacky.

2Question 2¶

Give an example of a ring $R$ and an ideal $I$ in it which is not principal. Describe the quotient $R/I$ for your choice.

$R = \mathbb Z[x]$, $I = \langle 2, x \rangle = \{2f(x) + xg(x) : f, g \in \mathbb Z[x]\}$.

The quotient $R/I$ includes all the functions with an odd constant term. So it's isomorphic to $\mathbb Z / 2 \mathbb Z$.

2.1Accuracy and discussion¶

This so happens to be exactly the same as the provided solution.

3Question 3¶

Compute the gcd of the polynomials

$$x^p - x, \quad x^3-1$$

in the ring $\mathbb Z/p \mathbb Z[x]$, when
(a) $p$ is a prime of the form $1+3m$;
(b) $p$ is a prime of the form $2 + 3m$.

(a) Our strategy is to use the Euclidean algorithm. First, we divide $x^{3m+1}-x$ by $x^3-1$.

$$x^{3m+1} - x = (x^3-1)(x^{3m+1-3} + x^{3m+1-3(2)} + \ldots) = (x^3-1)\underbrace{(x^{3(m-1) + 1} + x^{3(m-2)+1} + \ldots)}_{m \text{ terms}}$$

with the remainder being $x^1 - x = 0$, so it divides evenly, which means that the gcd is $x^3-1$.

(b) Same strategy as before, except the remainder is $x^2-x$. So then $\gcd(x^3-1, x^p-x) = \gcd(x^3-1, x^2-x) = \gcd(x^2-x, x-1) = x-1$.

3.1Accuracy and discussion¶

Discussed during lecture on Wednesday, December 5. Could use more rigour and a better explanation.

4Question 4¶

Let $F$ be a field and let $G = F^{\times}$ be its multiplicative group, i.e., its set of non-zero elements under the group operation. For all $t \geq 1$, show that $G$ has at most $t$ elements of order $t$.

I don't really know how to prove this, but there are some relevant links below:

• http://en.wikipedia.org/wiki/Multiplicative_order#Properties
• http://math.stackexchange.com/questions/129707/number-of-elements-of-order-k-in-the-multiplicative-group-z-nz
• http://en.wikipedia.org/wiki/Order_(group_theory)#Counting_by_order_of_elements

4.1Accuracy and discussion¶

Apparently you're supposed to use properties of polynomials ([link to solutions][solution]). I don't know if we ever proved this, but if you think about it, it makes a lot of sense, and is in fact quite pretty. Here's the gist: any element of order $t$ satisfies the equation $x^t=1$, from the definition of the order. Equivalently, any element of order $t$ satisfies $x^t-1$, and thus is a root of that polynomial. But $x^t-1$ is of degree $t$. So it can't have more than $t$ roots. !!!!!!!!

5Question 5¶

State Fermat's little theorem, and state Lagrange's Theorem in group theory. Explain how the latter can be used to prove the former.

Fermat's little theorem: if $p$ is prime, then for any integer $a$, $a^p \equiv a \pmod p$.

Lagrange's theorem: the order of a subgroup $H \subseteq G$ divides the order of $G$.

Let $a$ be an element in the finite group $(\mathbb Z/p\mathbb Z)^{\times}$. Since $\mathbb Z/p\mathbb Z$ consists of $\{0, 1, 2, \ldots, p-1\}$, and 0 is the only element that does not have an inverse (as $p$ is prime), then $(\mathbb Z/p\mathbb Z)^{\times} = \{1, 2, \ldots, p-1\}$, which has order $p-1$. $a$ then has a finite order, which we will denote $k$, such that $a^k=1$. The subgroup generated by $a$ is given by $\{1, a, a^2, \ldots, a^{k-1}\}$ and has order $k$. By Lagrange's theorem, $k$ divides $p-1$, so we can write $p-1 = mk$ where $m\in \mathbb Z$. So $a^{p-1} = a^{mk} = (a^k)^m = 1^m = 1$. So $a^{p-1} \equiv 1 \pmod p$, and if we multiply both sides by $a$ we get $a^p \equiv a\pmod p$, i.e., $a^p-a \equiv 0 \pmod p$, proving Fermat's little theorem.

5.1Accuracy and discussion¶

Question 9 on assignment 5 was pretty much the same. The instructor-provided solutions are probably better.

6Question 6¶

Show that the element $1 + \sqrt{-11}$ is irreducible in the ring $\mathbb Z[\sqrt{-11}]$, and that the ideal generated by 3 and $1 + \sqrt{-11}$ is not principal. What more familiar ring is the quotient $\mathbb Z[\sqrt{-11}]/(3, 1+\sqrt{-11})$ isomorphic to?

To show that it's irreducible, we make use of the norm function, which maps something of the form $a + b\sqrt{-11}$ to $a^2 + 11b^2$, basically multiplying by the conjugate. (It's a standard tool in this sort of situation.) Let's denote this function by $f$. Then $f(1 + \sqrt{-11} = 1^1 + 11 \cdot 1^2 = 12$. Now, the norm function is multiplicative, meaning that if we have $x, y \in \mathbb Z[\sqrt{-11}]$ and $x \mid y$, then $f(x) \mid f(y)$. Consequently, for $z = 1 + \sqrt{-11}$ to be reducible, there must be elements $u, v \in \mathbb Z[\sqrt{-11}]$ such that they both divide $z$, and so $f(u)$ and $f(v)$ must both divide 12 (with $1 < f(u), f(v) < 12$). So the possible values for $f(u)$ and $f(v)$ are 2, 3, 4 and 6.

Is it possible to have an element $a + b\sqrt{-11} \in \mathbb Z[\sqrt{-11}]$ whose norm is 2, 3, 4 or 6? Well, $f(a + b\sqrt{-11}) = a^2 + 11b^2$. First of all, we conclude that $b = 0$, or else it would be greater than 6 already lol. And only 4 can be a norm, if $a = 2$, since 2, 3 and 6 are not perfect squares. But then the norm for the other divisor has to be 3. But that's not possible. So we cannot have elements that are non-trivial divisors of $z$, and hence $z$ is irreducible. $\blacksquare$

To show that it's not principal, we use a proof by contradiction and make use of the norm function again. We assume that this ideal is principal, meaning that we can write it in the form $x=a + b\sqrt{-11}$ where $a, b \in \mathbb Z$. Since $x$ must divide both 3 and $z = 1 + \sqrt{-11}$, we have that $f(x) \mid f(3) = 9$ and that $f(x) \mid f(z) = 12$. The only non-trivial divisor of both 9 and 12 is 3. But there does not exist an element $y = c + d\sqrt{-11}$ such that $f(y) = c^2 + 11d^2 = 3$, since we must have $d=0$ (or else $f(y)$ would already exceed 3) and there is no solution to $c^2=3$ in $\mathbb Z$. Also, we know that the trivial divisor 1 doesn't work either, because the ideal generated by 1 is the whole ring and this ideal is not the whole ring (1 is not in it, for instance). This tells us that the ideal is not principal.

My guess is that it's isomorphic to $\mathbb Z / 3 \mathbb Z$. To prove this, we sent $a + b\sqrt{-11}$ to the class $[a-b]$ in $\mathbb Z / 3\mathbb Z$. Verifying the ring homo properties is fairly easy. To show that it's surjective, we just show that we can make all of $\{0, 1, 2\}$ (easy). Then we see that the ideal is in the kernel. So then we use the first isomorphism theorem, etc. I'm done.

6.1Accuracy and discussion¶

Question 1 on assignment 2 is tangentially related to the first part, in that it uses the norm function. At least it shows that using the norm function is acceptable (my usage of it may not be rigourous enough though). I'm pretty sure that it's the right thing to do in this case, although I don't recall seeing this question in class or on an assignment. There are some useful posts about this on mathoverflow: http://math.stackexchange.com/questions/94999/irreducible-in-mathbbz-sqrt-5, http://math.stackexchange.com/questions/86383/proving-2-3-1-sqrt-5-and-1-sqrt-5-are-irreducible-in-mathbbz-sqrt

The second part (not principal): http://math.stackexchange.com/questions/37468/show-that-the-ideal-2-1-sqrt-7-in-mathbbz-sqrt-7-is-no. Another: http://math.stackexchange.com/questions/32577/show-that-a-specific-ideal-is-not-principal

Last part: see solutions.

7Question 7¶

Show that the group $GL_2(\mathbb Z/2\mathbb Z)$ of invertible $2\times 2$ matrices with entries in $\mathbb Z / 2\mathbb Z$ has cardinality 6, and that it is isomorphic to the symmetric group $S_3$ on 3 letters.

There are $2^4 = 16$ possible matrices with entries in $\mathbb Z / 2 \mathbb Z$, but only 6 of them are invertible. How do we know this? Well, there are 3 possibilities for the first row: $[0, 1], [1, 1], [1, 0]$ (since $[0, 0]$ would not result in an invertible matrix). For the second row, there are only two choices, because $[0, 0]$ is still out but we also can't use the same row we used in the first row. So $3 \times 2 = 6$.

Incidentally, the group looks like this:

$$\left \{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \right \}$$

How do we show that it is isomorphic to $S_3$? We can create a homomorphism as follows: $f: GL_2 (\mathbb Z/ 2\mathbb Z) \to S_3$ which takes a matrix and maps it to the permutation of the elements 1, 2, 3 that is induced by the matrix. If we let $X$ be the set of possible column vectors in our group, we can enumerate the elements as follows:

$$X = \left \{ \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 1 \end{pmatrix} \right \} = \{1, 2, 3\}$$

So multiplying a matrix in the group by each column vector results in a permutation of the set:

$$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \qquad \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \qquad \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 1\end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

so this maps 1 to 3, 2 to 2, and 3 to 1 so it's equivalent to $(13)$.

We know this homomorphism is injective, because the kernel is the identity matrix. Since we know that $S_3$ has a cardinality of 6, then it's also surjective. Hence, $f$ is an isomorphism and so $GL_2(\mathbb Z/2\mathbb Z) \cong S_3$.

Extension: what if we had to find the cardinality of $GL_n$ with entries in $\mathbb Z/p \mathbb Z$? Well, in the first row, there are $p^n-1$ choices. In the second row, we have to stay away from the all-zero row as well as any multiple of the first row (there are $p$ of them). So $p^n - p$ choices. In the third row, there are $p^2$ combinations of the first two rows, so we have $p^n-p^2$ possibilities. So in total we have $(p^n-1)(p^n-p)(p^n-p^2) \ldots (p^n-p^{n-1})$ possibilities.

7.1Accuracy and discussion¶

He went over this in class. My explanation is a bit handwavy though.

8Question 8¶

Let $H$ be a subgroup of a group $G$ and suppose that $H$ has index two in $G$, i.e., that there are precisely two elements in $G/H$. Show that $H$ is a normal subgroup of $G$.

The left cosets are $G/H = \{H, aH\}$ (where $a \notin H$). Then, the right cosets must be $H\backslash G = \{H, Ha\}$. Now, the union of the left cosets is all of $G$. Same for the right cosets. But then we can conclude that $aH=Ha$, which shows that $H$ is a normal subgroup. Of course, this is only possible because $H$ has index two.

Alternatively, we could make the following homomorphism¹ $f: G \to \mathbb Z /2\mathbb Z$, whose kernel would be all of $H$:

$$f(g) = \begin{cases} 0 & \text{if } g \in H \\ 1 & \text{if } g \notin H \end{cases}$$

Then, since the kernel of any homomorphism is a normal subgroup, $\blacksquare$.

8.1Accuracy and discussion¶

Discussed during lecture on Wednesday, December 5. The explanation could definitely be improved.

9Question 9¶

Let $H$ be a subgroup of a group $G$, and let $N$ be a normal subgroup of $G$. Show that $H \cap N$ is a normal subgroup of $H$.

Let $H = H_1 \cap H_2$. To show that $H$ is a subgroup, we need to show that it satisfies the following properties:

1. The identity element $e \in H$,
2. If $h \in H$, then the inverse $h^{-1} \in H$,
3. If $h \in H$ and $g \in H$, then $gh \in H$.

So:

1. Since both $H_1$ and $H_2$ are subgroups, we have that $e \in H_1$ and $e \in H_1$. Consequently, $e \in H_1 \cap H_2$ $\checkmark$
2. Let $h \in H_1 \cap H_2$. Then since $h \in H_1$, $h^{-1} \in H_1$, as $H_1$ is a subgroup; by the same reasoning we can conclude that $h^{-1} \in H_2$. Consequently, $h \in H_1 \cap H_2$ $\checkmark$
3. If $h \in H$ and $g \in H$, then we have that $h, g \in H_1$ and $h, g \in H_2$. Consequently, $hg \in H_1$ and $hg \in H_2$, by property 3 of a subgroup. So $hg \in H_1 \cap H_2$ $\checkmark$ $\blacksquare$

9.1Accuracy and discussion¶

This was the first part of question 8 on assignment 5 (I just copied and pasted from mine). Should be accurate, barring typos and the like.

Oops, forgot to show that it's normal. Whatever. See the solutions.

10Question 10¶

Recall that any group is said to be simple if it has no non-trivial normal subgroups other than $G$ and $\{1\}$. Show that any non-trivial homomorphism $f: G \to G'$ (i.e., for which $f(G) \neq \{1\}$) is necessarily injective if $G$ is a simple group.

Recall that the kernel of any group homomorphism $f: G \to G'$ is a normal subgroup of $G$. Since $G$ is simple, we have that $\ker(f)$ is either $\{e\}$ or all of $G$. Since the homomorphism is non-trivial (i.e., not the zero homomorphism), then $\ker(f) \neq G$, and so it must be that $\ker(f) = \{e\}$. This just means that $f$ is injective, which concludes the proof.

10.1Accuracy and discussion¶

From the solutions. Quite nice.