# Abstract Nonsense

## Dummit and Foote Preliminaries Sections .1,.2, and .3

In exercises 1 to 4 let $\mathcal{A}$ be the set of all $2\times 2$ matrices with real number entries. Recall that matrix multiplication is defined by

$\begin{bmatrix}a & b\\ c& d\end{bmatrix}\begin{bmatrix}p & q\\ r & s\end{bmatrix}=\begin{bmatrix} ap+br & aq+bs\\ cp+dr & cq+ds \end{bmatrix}$

Let

$M=\begin{bmatrix}1 & 1\\ 0 & 1 \end{bmatrix}$

and

$\mathcal{B}=\left\{X\in\mathcal{A}:MX=XM\right\}$

1.

Problem: Determine which of the following matrices lie in $\mathcal{B}$

a) $M$

b) $\begin{bmatrix}1 & 1\\ 1&1 \end{bmatrix}$

c) $\begin{bmatrix}0 & 0\\ 0& 0\end{bmatrix}$

d) $\begin{bmatrix} 1 &1 \\ 1 &0 \end{bmatrix}$

e) $I$ (the identity)

f) $\begin{bmatrix}0 & 1\\ 1& 0\end{bmatrix}$

Solution:

a) Clearly $M\in\mathcal{B}$ since $MM=MM$

b) No.

c) Clearly this will commute with $M$.

d) Doesn’t commute.

e) Clearly this commutes, it’s the identity matrix.

f) Doesn’t commute.

2.

Problem: Prove that if $P,Q\in\mathcal{B}$ then $P+Q\in\mathcal{B}$

Proof: Note that

$\left(P+Q\right)M=PM+QM=MP+MQ=M\left(P+Q\right)$

The conclusion follows.

3.

Problem: Prove that if $P,Q\in\mathcal{B}$ then $PQ\in\mathcal{B}$

Proof: Merely note that

$\left(PQ\right)M=P\left(QM\right)=P\left(MQ\right)=\left(PM\right)Q=\left(MP\right)Q=M\left(PQ\right)$

from where the conclusion follows.

4.

Problem: Find the conditions on $p,q,r,s$ which determine when $\begin{bmatrix}p & q \\ r & s\end{bmatrix}=P\in\mathcal{B}$

Proof: A simple calculations shows that

$PM-MP=\begin{bmatrix} r & s-p \\ 0 & -r\end{bmatrix}$

And since evidently

$X\in \mathcal{B}\Leftrightarrow XM-MX=0$

It follows that

$P\in\mathcal{B}\Leftrightarrow r=0\text{ and }s=p$

5.

Problem: Determine whether the following functions $f$ are well-defined:

a) $\displaystyle f:\mathbb{Q}\to\mathbb{Z}:\frac{a}{b}\mapsto a$

b) $\displaystyle f:\mathbb{Q}\to\mathbb{Q}:\frac{a}{b}\mapsto\frac{a^2}{b^2}$

Proof:

a) Clearly this is not well defined since

$\displaystyle \frac{1}{2}=\frac{2}{4},\text{ but }f\left(\frac{1}{2}\right)=1\ne2=f\left(\frac{2}{4}\right)$

b) This is well-defined, to see this note that

$\frac{a}{b}=\frac{c}{d}\implies \frac{a^2}{b^2}=\frac{c^2}{d^2}$

6.

Problem: Determine whether the function $f:\mathbb{R}\to\mathbb{N}$ defined by mapping a real number to the first digit of its decimal point expansion is well-defined.

Proof: This problem is deliberately meant to trip you up. The answer is no, even though it should be yes.

$1.\overline{0}=.\overline{9}$

even though

$0\ne 9$

7.

Problem: Let $f:A\to B$ be a surjective map. Prove that the relation

$a\sim b\Leftrightarrow f(a)=f(b)$

is an equivalence relation whose equivalence classes are the fibers of $f$.

Proof: Clearly $\sim$ is reflexive. It’s symmetric just because $a\sim b\implies f(a)=f(b)\implies f(b)=f(a)\implies b\sim a$. Lastly , it’s transtive because $a\sim b,b\sim c$ implies that $f(a)=f(b),f(b)=f(c)$ and by the transitivity of the equality relation $f(a)=f(c)$ and thus $a\sim c$. The fact that it’s equivalence classes are the fibers is obvious.

—————————————————————————————————————————–

1.

Problem: For each of the following pairs of integers $a$ and $b$, determine their greatest common divisor, their least common multiple and write their gcd as a linear combination of the two.

a) a=20,b=13

b) a=69,b=372

c) a=792,b=275

d) a=11391,b=5673

e) a=1761,b=1567

f) a=507885,b=60808

Proof: Omitted. What’s the point really? It’s just manual labor.

2.

Problem: Prove that if the integer $k$ divides the integers $a$ and $b$ then $k$ divides $as+bt$ for every $s,t\in\mathbb{Z}$

Proof: Since $k\mid a,k\mid b$ this implies that $a=z_1k,b=z_2k$ for some $z_1,z_2\in\mathbb{Z}$. Thus, $as+bt=z_1ks+z_2kt=k\left(z_1s+z_2t\right)$ and thus $k\mid as+bt$.

3.

Problem: Prove that if $n$ is composite, then there are integers $a$ and $b$ such that $n\mid ab$ but $n\nmid a$ and $n\nmid b$

Proof: I assume that we are to not consider $1$? Then, this is clearly true since $n=ab$ for some $0<|a|,|b| and so $n\mid ab=n$ but $n\nmid a,b$ since $0<|a|,|b|

4.

Problem: Let $a,b$ and $N$ be fixed integers with $a$ and $b$ nonzero, and let $d=(a,b)$. Suppose that $x_0$ and $y_0$ are particular solutions to $ax+by=N$. Prove that for any integer $t$ the integers $\displaystyle x=x_0+\frac{b}{d}t$ and $\displaystyle y=y_0-\frac{a}{d}t$ are also solutions to $ax+by=N$.

Proof: Plugging the numbers into the equation we get

$\displaystyle a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)$

which is equa lto

$ax_0+by_0+\frac{ab}{d}t-\frac{ba}{d}t=N+0=N$

thus, they are all, in fact, solutions.

5.

Problem: Determine the value for $\varphi(n)$ for $n=1,\cdots,30$

Proof: Omitted. Really? I would just plug these into a calculator.

6.

Problem: Prove the well-ordering property of $\mathbb{N}$ by induction

Proof: Let $S$ be a subset of the natural numbers which has no least element. We claim that $S=\varnothing$. To see this we first note that by assumption since $S$ has no least element, for each $s\in S$ there is some $t\in S$ such that $t otherwise $s$ is the least element. So, fix $n\in\mathbb{N}$ and suppose that $m\notin S,m=1,\cdots,n-1$. Then, clearly $n\notin S$ otherwise there would have to be some $m\in\{1,\cdots,n-1\}\cap S$  such that $m (by assumption), but this contradicts that $m\notin S,\text{ }m=1,\cdots,n-1$. Noting that the base case when there is $1$ element in $S$ is clearly true, since if $S$ had one element, clearly that element is minimal.  The conclusion follows.

To prove uniqueness we merely note that if $\alpha,\beta=\min\text{ }S$ then since $\beta\in S$ we have that $\alpha\leqslant \beta$ and since $\alpha\in S$ we have that $\beta\leqslant\alpha$ and so it follows by the anti-symmetry of the $\leqslant$ relation on $\mathbb{N}$ that $\alpha=\beta$.

7.

Problem: Prove that $\sqrt{p}\notin\mathbb{Q}$ for each prime $p$.

Proof: Suppose that $\displaystyle \sqrt{p}=\frac{m}{n},\text{ }(m,n)=1$ then $n^2p=m^2$. But, clearly this implies that $p\mid m^2$ which by Euclid’s lemma implies that $p\mid m$ and so $m=pm'$ for some $m'\in\mathbb{Z}$. Thus, $pn^2=p^2m'^2$ but this implies that $p^2\mid pn^2$ and so $p\mid n^2$ and so by the same lemma $p\mid n$. But, this implies that $p\mid 1$ which is a contradiction.

8.

Problem: Let $p$ be a prime, and $n\in\mathbb{N}$. Find a formula for the largest power of $p$ which divides $n!$

Proof: For notational convenience let $\eta(p,n)$ be the maximum $m$ such that $p^m\mid n$. Note that the only numbers divisible by $p$ are of the form $pz$ for some $z\in\mathbb{Z}$. Thus, there are $\displaystyle \left\lfloor \frac{n}{p^1}\right\rfloor=\alpha_1$ numbers less than or equal to $n$ which are divisible by $p$. Thus, there are exactly $\alpha_1$ factors of $n!$ for which $p$ divides them. Thus, one can think of $n!$ as being written as $zp^{\alpha_1}$ and so we know that $\eta(p,n)\geqslant \alpha_1$. Note though that every $p^2$th number is of the form $p^2z$ for some $z\in\mathbb{Z}$ and though one of the $p$‘s was “counted” by $\alpha_1$ one wasn’t. Thus, each of these contributes one more to $\eta(n,p)$. Thus, using the same logic $\displaystyle \eta(n,p)\geqslant\alpha_1+\alpha_2$ where $\displaystyle \alpha_2=\left\lfloor \frac{n}{p^2}\right\rfloor$. Then, noting that every $p^3$th number “contributes” three to $\eta(n,p)$ we note that $\displaystyle \alpha_1+\alpha_2+\alpha_3$ where $\displaystyle \alpha_3=\left\lfloor \frac{n}{p^3}\right\rfloor$. Continuing on this way and defining $\displaystyle \alpha_m=\left\lfloor\frac{n}{p^m}\right\rfloor$ we may conclude that

$\displaystyle \eta(n,p)=\sum_{m=1}^{\infty}\alpha_m$

Note that this sum “makes sense” in terms of convergence since for all but finitely many $m$ we have that $p^m>n\implies \alpha_m=0$.

Remark: This can be proven more rigorously using the Inclusion-Exclusion principle.

9.

Problem: Something with computers! No!

10.

Problem: Prove that for any given $N\in\mathbb{N}$ there exists only finitely many integers $n$ with $\varphi(n)=N$. Conclude that $\varphi(n)\xrightarrow[\quad]{n\to\infty}\infty$.

Proof: It is a pretty common fact that for $n\ne2,6$ we have that $\varphi(n)\geqslant \sqrt{n}$. The conclusion follows for both parts.

11.

Problem: Prove that if $d\mid n$ then $\varphi(d)\mid\varphi(n)$

Proof: Let $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$. Then, since $d\mid n$ we have that $d=p_{\gamma_1}^{\beta_{\gamma_1}}\cdots p_{\gamma_k}^{\beta_{\gamma_k}}$ where $\{p_{\gamma_1},\cdots,p_{\gamma_k}\}\subseteq\{p_1,\cdots,p_m\}$ and $\beta_{\gamma_\ell}\leqslant \alpha_{\gamma_\ell}$. Thus,

$\displaystyle \frac{\varphi(n)}{\varphi(d)}=\text{integer}\cdot p_{\gamma_1}^{\alpha_{\gamma_1}-\beta_{\gamma_1}}\frac{p_{\gamma_1}-1}{p_{\gamma_1}-1}\cdots p_{\gamma_k}^{\alpha_{\gamma_k}-\beta_{\gamma_k}}\frac{p_{\gamma_k}-1}{p_{\gamma_k}-1}$

where $\text{integer}$ is meant to represent the usual factors in $\varphi(n)=p_1^{\alpha_1-1}(p_1-1)\cdots p_m^{\alpha_m-1}(p_m-1)$ which have no corresponding prime in the representation $d=p_{\gamma_1}^{\beta_{\gamma_1}}\cdots p_{\gamma_k}^{\beta_{\gamma_k}}$. But, clearly since $\alpha_{\gamma_\ell}\geqslant \beta_{\gamma_\ell}$ we see that $\displaystyle \frac{\varphi(n)}{\varphi(d)}$ is the multiplication of two integers, and thus an integer. The conclusion follows.

———————————————————————————————————————————————————————————–

1.

Problem: Write down explicitly all the elements of the residue classes of $\mathbb{Z}/18\mathbb{Z}$.

Proof: Why? The idea is that each will look like

$\overline{k}=\left\{k+18n:n\in\mathbb{N}\right\}$

2.

Problem: Prove that the distinct equivalence classes in $\mathbb{Z}/n\mathbb{Z}$ are $\overline{0},\cdots,\overline{n-1}$.

Proof: We first note that each of these equivalence classes are distinct, since if $\overline{k}\cap\overline{\ell}\ne\varnothing,\text{ }k\ne \ell$ then we have there is some $x\in\overline{k}\cap\overline{\ell}$. Thus, by the first membership we have that $n\mid x-k$ and the second membership says that $n\mid x-\ell$ and thus $n\mid \ell-k$. But, since $-(n-1)\leqslant \ell-k\leqslant n-1$ this is clearly impossible.

To prove that they are the only distinct equivalence classes we note that if $k\in\mathbb{Z}$ then by the division algorithm says that $k=mn+r$ for some $0\leqslant r\leqslant n-1$. Thus, noting that the condition on $r$ implies that $r\in\{0,\cdots,n-1\}$ we note $\overline{mn+r}=\overline{r}\in\left\{\overline{0},\cdots,\overline{n-1}\right\}$. The conclusion follows.

3.

Problem: Prove that if $a=a_0+\cdots+a_n10^n$ then $a\equiv a_0+\cdots+a_n\text{ mod }9$.

Proof: This is clear since each $a_k10^k\equiv a_k\cdot 1=a_k\text{ mod }9$ since $10\equiv 1\text{ mod }9$.

4.

Problem: Compute the remainder of $37^{100}\text{ mod }29$.

Proof: We first note that since $37\equiv 8\text{ mod }9$ that $37^{100}\equiv 8^{100}\text{ mod }9$. Thus, noting that $(8,29)=1$ and $\varphi(29)=28$ we may appeal to Euler’s theorem to see that

$\displaystyle 8^{100}=8^{3\varphi(29)+16}\equiv 8^{16}\text{ mod }29$

but

$8^{16}=64^8\equiv 6^{8}\text{ mod }29$

and

$6^8=36^4\equiv 7^4\text{ mod }29$

and finally

$7^4=49^2\equiv 20^2=400\equiv 23\text{ mod }29$

Remark: There is a more clever way to do this introducing the notion of the sum of a geometric sequence in modular arithmetic, but this is slightly more advanced than the book probably wanted.

5.

Problem: Compute the last two digits of $9^{1500}$

Proof: Note this is the same as computing $9^{1500}\text{ mod }100$. Thus, noting again that $(9,100)=1$ and $\varphi(100)=40$ we see that

$9^{1500}=9^{37\varphi(100)+20}\equiv 9^{20}\text{ mod }100$

Thus, doing again what we did last time we see that

$9^{20}=6561^5\equiv 61^5\text{ mod }100$

and

$61^5=61\times 3721^2\equiv 61\times 21^2=26901\equiv 1\text{ mod }100$

6.

Problem: Prove that the squares of the elements of $\mathbb{Z}/4\mathbb{Z}$ are $\overline{0},\overline{1}$

Proof: $\overline{0}^2=\overline{0^2}=\overline{0}$, $\overline{1}^1=\overline{1^2}=\overline{1}$, $\overline{2}^2=\overline{2^2}=\overline{4}=\overline{0}$, and $\overline{3}^2=\overline{3^2}=\overline{9}=\overline{1}$.

7.

Problem: Prove that any integers $a$ and $b$ never leave a remainder of three when divided by four.

Proof: By our last problem we have that $0\leqslant a^2+b^2\leqslant 2\text{ mod }4$, from where the conclusion follows.

8.

Problem: Prove that the equation $a^2+b^2=3c^2$ has no solutions in nozero integers $a,b$ and $c$.

Proof: Note that since $(a_0,b_0,c_0)$ is a solution implies that $( |a_0|,| b_0|,|c_0|)$ is a solution, it suffices to show there is no solution in $\mathbb{N}$. Do do this suppose that $(a_0,b_0,c_0)$ is a solution. Then, we have that $a_0^2+b_0^2=3c_0^2$. Now, we must have that $2\mid c_0$ since otherwise we have that $c_0\equiv 1,3\text{ mod }4$ and so $3c_0^2\equiv 3\text{ mod }4$ and thus $a_0^2+b_0^2\equiv 3\text{ mod }4$, but this is impossible by the last problem. Thus, $2\mid c_0\implies 4\mid c_0^2$. So, $a_0^2+b_0^2=12d_0^2$ for some $d_0\in\mathbb{Z}$. But, this clearly implies that $2\mid a_0,b_0$ and so $4e_0^2+4f_0^2=12d_0^2\implies e_0^2+f_0^2=3d_0^2$ and so $(e_0,f_0,d_0)$ is another solution in $\mathbb{N}$ such that $e_0. But, clearly we may repeat this process ad infinitum to produce infinitely many solutions to $a^2+b^2=3c^2$ each of which contains numbers strictly less than the previous solution. But, this implies there are infinitely many numbers less than a fixed natural number…which is impossible. It follows that the assumption of an initial solution must have been flawed. The conclusion follows.

9.

Problem: Show that the square of any odd integer always leaves a remainder of 1 when divided by 8

Proof: The only distinct odd residue classes $\text{ mod }8$ are $1,3,5,7$ and so if $n$ is any odd number we have that $n^2\equiv 1^2,3^2,5^2,7^2=1,9,24,48\equiv 1\text{ mod }8$

10.

Problem: Prove that the number of elements of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ is $\varphi(n)$

Proof: I’m not sure what’s to prove. It was proven in the book that the elements of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ are those numbers $m$ such that $(m,n)=1$. Thus, noting that we must only consider such $m$ with the property that $0\leqslant m\leqslant n-1$ we see that there is exactly $\varphi(n)$ of them.

11.

Problem: Prove that $\overline{a},\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\implies \overline{a}\cdot\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$

Proof: By assumption there exists $\overline{c},\overline{d}\in\mathbb{Z}_n$ such that $\overline{a}\overline{c}=\overline{b}\overline{d}=\overline{1}$. Thus, since $\overline{c}\overline{d}\in\mathbb{Z}_n$ we can see that $\overline{a}\overline{b}\overline{c}\overline{d}=\overline{a}\overline{c}\overline{b}\overline{d}\overline{1}\overline{1}=\overline{1}$ and so $\overline{a}\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$

12.

Problem: Let $n\in\mathbb{Z}$ and $n>1$, and let $a\in\mathbb{Z}$ with $1\leqslant a\leqslant n$. Prove if $a$ and $n$ are no relatively prime there exists an integer $b$ with $1\leqslant b< n$ such that $ab\equiv 0\text{ mod }n$ and thus deduce there is no $c\in\mathbb{Z}$ such that $ac\equiv 1\text{ mod }n$

Proof: Let $d=(a,n)>1$. Note then that $\displaystyle \frac{a}{d}\in\mathbb{Z}$ and $\displaystyle 1\leqslant \frac{a}{d}. Also, note that $\displaystyle a\cdot\frac{n}{d}=\frac{a}{d}\cdot n=mn\equiv 0\text{ mod }n$, the important part noting that $\displaystyle \frac{a}{d}=m\in\mathbb{Z}$. This proves the second part by letting $\displaystyle b=\frac{a}{d}$

Now, clearly we can’t have that $ac\equiv 1\text{ mod }n$ otherwise we’d have that $b\equiv b(ac)=(ba)c\equiv 0\cdot c=0\text{ mod }n$ which is preposterous.

13.

Problem: Let $n\in\mathbb{Z},n>1$ and let $a\in\mathbb{Z}$ with $1\leqslant a\leqslant n$. Prove that if $(a,n)=1$ then there is an integer $c$ such that $ac\equiv 1\text{ mod }n$.

Proof: This follows immediately since $ax+bn=1$ has a solution for $x,y\in\mathbb{Z}$.

14.

Problem: Conclude from the previous two exercises that $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ is the set of elements $\overline{a}\in\mathbb{Z}/n\mathbb{Z}$ with $(a,n)=1$.

Proof: If $R(n)=\left\{\overline{a}:(a,n)=1\right\}$ the first exercise shows that $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\subseteq R(n)$ and the second shows that $R(n)\subseteq\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$.

We choose to omit 15 and 16 being computational and computer related.

June 14, 2010 -

## 1 Comment »

1. Hi Drexel,
Nice blog! You should make PDFs with your solutions.
I’d just like to suggest different solutions to 2.11 and to 3.8.

2.11 : let f : (Z/nZ)^* –> (Z/dZ)^* be reduction mod d. This is a surjective homomorphism, so phi(d) | phi(n).

3.8 : We can suppose gcd(a,b,c)=1. Now reduce both sides mod 4; the only possibility is that a,b,c all be even, which contradicts the assumption!

Comment by Bruno | June 19, 2010 | Reply