Practice midterm

Student-provided solutions to the sample midterm created by Professor Darmon and made available here. The solutions may or may not be accurate.

1Question 1¶

Recall that the power set of a set $A$, denoted $P(A)$, is the set of all subsets of A. Let $f : A \to P(A)$ be a function from $A$ to its power set. Show that the subset $B$ of $A$ defined by

$$B = \{ a \in A \text{ such that } a \notin f(a)\}$$

is not an element of the image of $f$.

1.1Solution¶

We can show this by contradiction. Suppose $B$ is an element of the image of $f$. That means there must be an element $b \in A$ such that $f(b) = B$. Now, is $b$ in $B$? Well, if $b \notin f(b)$, then yes, $b \in B$. But $f(b) = B$. So if $b \notin B$ then $b \in B$. But that is a contradiction! $b$ would have to be both in and not in $B$ at the same time.

So $b$ can't be an element of $f(b)$. But if this is the case, then $B$ would have to contain $b$, as $b$ contains all elements in $A$ that are not in their image. So $b \in B$. Since $f(b) = B$, then $b \in f(b)$, contradicting the premise that $b \notin f(b)$. $b$ must be neither in nor not in $B$. Of course, that is another contradiction.

Consequently, $B$ cannot be an element of the image of $f$.

1.2Accuracy and discussion¶

This question bears a notable resemblance to question 9 of assignment 1. Both are quite nice. Solution confirmed by Darmon during class on Monday, October 22.

2Question 2¶

Compute the greatest common divisor of the integers $a = 13200000008150000000000000000132$ and $b = 1320000000815$,

2.1Solution¶

We can use the Euclidean algorithm for this:

$\begin{align*} a & = b \cdot 10000000000000000000 + 132 \\ b & = 132 \cdot 10000000000 + 815 \\ 132 & = 815 \cdot 0 + 132 \\ 815 & = 132 \cdot 6 + 23 \\ 132 & = 23 \cdot 5 + 17 \\ 23 & = 17 \cdot 1 + 6 \\ 17 & = 6 \cdot 2 + 5 \\ 6 & = 5 \cdot 1 + 1 \\ 5 & = 1 \cdot 5 + 0 \end{align*}$

So the gcd is 1.

2.2Accuracy and discussion¶

Solution confirmed by WolframAlpha. This question was also posted (almost certainly by someone in this class) on Yahoo! answers, and the only response at the time of writing agreed with this solution. Also, Darmon confirmed that the $\gcd$ is 1 during class on Monday, October 22 (and also mentioned that it wasn't supposed to be 1).

3Question 3¶

Compute the least residue modulo N = 95 of the integer $3^{11000000000000000000000000000000000000000000}$.

3.1Solution¶

We make use of the Chinese remainder theorem. First, note that the prime divisors of 95 are 19 and 5. To find the least residue modulo 95 of the integer (which we'll call $x$), we first have to find its least residue modulo 19 and its least residue modulo 5.

For modulo 5: first, we note that $3^4 \equiv 1 \pmod 5$, by Fermat's little theorem (since $\gcd(3,5)=1$). Since the exponent of $x$ is divisible by 100, it is also divisible by 4, and so $x = {3^4}^n$ where $n$ is some integer $n$. Consequently, $x \pmod 5 \equiv 1$.

For modulo 19: by Fermat's little theorem, $3^{18} \equiv 1 \pmod{19}$ (since $\gcd(3, 19) = 1$). Now, $18 = 2 \cdot 9$. For a number to be divisible by 18, it must be both even and divisible by 9. For a number to be divisible by 9, its digits must add up to 9. So $x + 16$ would be divisible by both 9 and 2 and thus would be divisible by 18. This tells us that $3^{11000000000000000000000000000000000000000016} \equiv {3^{18}}^n \equiv 1$ for some $n$. We can multiply both sides by $3^{-16}$, which gives us $x \equiv 3^{-16}$. If we then multiply both sides by $3^{18}$, we get that $3^{18}x \equiv 3^2$ and since $3^{18} \equiv 1$, $x \equiv 3^2 \equiv 9$.

To find the final answer, we need to find a number $y$ such that $y \equiv 1 \pmod 5$ and $y \equiv 9 \pmod{19}$ (where $0 \leq y \leq 95$). By trying different values of $y' \in \mathbb{N}$ in the equation $x = 19y' + 9$, and seeing which have a last digit of 1 or 6, we get that $y' = 3$ and $y = 66$. So the least residue modulo 95 of $x$ is 66.

3.2Accuracy and discussion¶

This problem was worked through by the TA during the tutorial session on Friday, October 19. Also worked through by Darmon on Monday, October 22.

4Question 4¶

Using only the basic properties of the gcd proved in class, (and not the fundamental theorem of arithmetic) show that if a $p$ is a prime and $p$ divides a product $ab$ of two integers, then $p$ necessarily divides either $a$ or $b$.

4.1Solution¶

Since $p\mid ab$ and $p \mid p$ (by the reflexivity of $\mid$), then $\gcd(p, ab) = p$ (since nothing greater than $p$ can divide $p$). We assume that $p \nmid a$ and $p \nmid b$. So $\gcd(p, a) = 1$ and $\gcd(p, b) = 1$. By theorem 9.1.2 in the notes (also known as Bézout's identity), there exist integers $x$ and $y$ such that $xp + ya = 1$ (from the fact that $\gcd(p, a) = 1$). If we multiply both sides of the identity by $b$, we get:

$$xbp + yab = b$$

Well, we know that $p \mid ab$, by a premise of this argument. From definition of a $\gcd$ (definition 9.0.5 (2) in the notes), we know that $p \mid yab$. We also know that $p \mid xbp$, since that's just a multiple of $p$ (definition 9.0.5 (2) again). Then, by definition 9.0.5 (3), we know that $p \mid xbp + yab$, and by the identity above then $p \mid b$. Since this contradicts the premise that $p \nmid b$, then our assumption that $p\nmid a$ and $p\nmid b$ must be wrong, and so $p$ must divide either $a$ or $b$ (or both).

Alternatively, we could just assume, without loss of generality, that $p \nmid a$ and from that conclude that $p \mid b$. Whichever.

4.2Accuracy and discussion¶

He might have gone over this in class on Monday, October 22, but I wasn't paying attention. This proof seems to make sense to me, though, and there are some notes available online that use the same method to prove this, so it should be solid.