Fall 2012 Midterm

Student-provided solutions to the in-class midterm on Wednesday, October 24, 2012. Written up because Professor Darmon indicated that he might not post solutions for it. All the answers should be 100% correct, barring typos and things like that.

I don't have the actual question sheet on me right now so the questions have been reconstructed from memory and from my solutions.

1Grade distribution¶

2Question 1¶

Evaluate $(1 + i)^{100}$.

Let $z = 1 + i$. First, we find $z$'s polar representation. $r = \sqrt{1^2+1^2} = \sqrt{2}$ and $\theta = \frac{\pi}{4}$ (just draw the triangle to confirm). So $z = r \cos(\theta) + ri\sin(\theta) = \sqrt{2}\cos(\pi/4) + \sqrt{2} \sin (\pi/4) i = \sqrt{e^{i\pi/4}}$ by Euler's identity ($e^{i\theta} = \cos \theta + i\sin\theta$).

So, $z^{100} = (\sqrt{2}e^{i\pi/4})^{100} = \sqrt{2}^{100} e^{100i\pi/4} = 2^{50} e^{25\pi i}$.

Using Euler's identity again, we have that $e^{25\pi i} = \cos(25\pi) + i\sin(25\pi)$. But $25\pi \equiv \pi \pmod{2\pi}$ so $\sin(25\pi) = \sin(\pi) = 0$, who would have guessed. So $e^{25\pi i} = \cos(25\pi) = \cos(\pi) = -1$.

So $(1 + i)^{100} = z^{100} = 2^{50}e^{25\pi i} = -2^{50}$. $\blacksquare$

3Question 2¶

Let $L$ be the set of all positive linear combinations of two integers $a$ and $b$. Using only the basic properties of the $\gcd$ (not the fundamental theorem of arithmetic or anything fancy like that), prove that:

(a) the least element in $L$ divides both $a$ and $b$;
(b) the least element in $L$ is equivalent to $\gcd(a, b)$.

This is pretty much exactly the same as this, but I'll write it up again anyway.

(a) First of all, we note that $L$ is clearly not empty - for example, $a\cdot a + b \cdot b \in L$. So by the well-ordering principle, $L$ has a least element. We denote that least element by $d = ua + vb$ for some integers $u$ and $v$.

Now, we can write $a = qd + r$ for some integer $q$ and some $0 \leq r < d$. Substituting $d = ua + vb$ in there, we get $a = q(ua + vb) + r = qua + qvb + r$. So $r = a - qua - qvb = a(1-qu) - (qv)b$. Clearly, $r$ is a linear combination of $a$ and $b$. Is $r \in L$? Well, since it's positive, it has to be either in $L$ or 0. But it can't be in $L$, as it's less than $d$ - if it were, it would contradict the minimality of $d$. So it must be 0. But this just means that $a = qd + 0 = qd$ which means that $d \mid a$. By similar reasoning, we can show that $d \mid b$. So $d \mid a$ and $d \mid b$ which is exactly what we needed to show. $\blacksquare$

(b) Consider any common divisor of $a$ and $b$, which we will denote by $d'$. But by the properties of divisors, $d'$ must also divide any linear combination of $a$ and $b$. Most notably, $d'$ must divide $d$. This means that $d' \leq d$ since no number greater than $d$ can divide $d$ for $d > 0$. But this is true for any arbitrary common divisor $d'$, and so we conclude that the largest $d'$ which divides both $a$ and $b$ has to be equal to $d$ itself. Consequently, $\min(L) = \gcd(a, b)$. $\blacksquare$

4Question 3¶

Let $a = 7^b$ where $b$ is some large number that looks like $13198\ldots 4531$.

(a) Calculate $a \pmod 5$.
(b) Calculate $a \pmod{11}$.
(c) Calculate $a \pmod{55}$.

(a) We know that $4 \mid b + 1$ since $4 \mid 100$ and $4 \mid 32$ (so it divides any linear combination of 100 and 32, notably $b + 1 = 13198\ldots 4532$. So $b + 1 = 4k$ where $k \in \mathbb{N}$. So $b = 4k-1$. So $a = 7^b = 7^{4k-1} = 7^{4k}7^{-1} = (7^4)^k 7^{-1}$. By Fermat's little theorem, since $\gcd(4, 7) = 1$, then $a^4 \equiv 1\pmod 5$ for all $a$. So $7^4 \equiv 1 \pmod 5$. So $a = 1^k 7^{-1} = 7^{-1}$. Multiplying both sides by $7^4 = 1$, we get $7^4 a = 1 \cdot a = 7^{-1}7^4 = 7^3$ (working mod 5 of course). So $a \equiv 7^3 \equiv 243 \equiv 3 \pmod 5$. $\blacksquare$

(b) We know that $10 \equiv 0 \pmod{b - 1}$ since $b - 1$ is clearly a multiple of 10. Then, $b-1 = 10k$ where $k \in \mathbb{N}$. So $b = 10k+1$. So $a = 7^{10k+1} = (7^{10})^k \cdot 7^1$. By Fermat's little theorem, since $\gcd(7, 10) = 1$, $a^{10} \equiv 1 \pmod{11}$ for all $a$, then $7^{10} \equiv 1$. So $(7^{10})^k \equiv 1$. So $a \equiv 7 \pmod{11}$. $\blacksquare$.

(c) 55's prime divisors are 11 and 5. By the Chinese remainder theorem, if $x$ solves the congruence relations $x = 1 \pmod 5$ and $x = a \pmod{11}$, then $x \equiv a \pmod{55}$. Now, from parts (a) and (b), we have that $x \equiv 3 \pmod 5$ and $x\equiv 7\pmod{11}$. So $x = 5\alpha + 3 = 11\beta + 7 \pmod{55}$, where $\alpha, \beta \in \mathbb{Z}$. If $\alpha = 3$ and $\beta = 1$ (determined through trial and error), then $x \equiv 18 \pmod{55}$. $\blacksquare$

5Question 4¶

Solve the following congruence relations.

(a) $5x \equiv 2 \pmod{11}$
(b) $10x \equiv 4 \pmod{22}$
(c) $10x \equiv 3 \pmod{22}$

(a) Possibilities for $5x$, based on the fact that it has to be in the form $11k + 2$ where $k \in \mathbb{Z}: \{2, 13, 24, 35, 46, 57, 68, 79, 90, \ldots\}$. 35 is divisible by 5, with $x = 7$. Also, 90 is divisible by 5, with $x = 18$ but that is just 7 in mod 11. So $x = [7]$. $\blacksquare$

(b) Possibilities for $10x: \{ 4, 26, 48, 70, 92, 114, 136, 158, 180, 202, 224 \ldots \}$. 70 is divisible by 10, with $x = 7$, as is 180, with $x = 18$. So $x = [7], [18]$. $\blacksquare$

(c) Possibilities for $10x: \{ 3, 25, 47, 69, \ldots\}$. Not solvable because $22\alpha + 3$ for some $\alpha \in \mathbb{Z}$ will always be odd but $10x$ must be even, so $22 \alpha + 3 = 10x$ has no solutions for $x \in \mathbb{Z} /22\mathbb{Z}$. $\blacksquare$