Homework 2
MATH 301/601
Test #2 is on Monday, March 3
 

Instructions. Read the Homework Guide to make sure you understand how to successfully complete the assignment. Click here for a pdf version of the homework.

Exercise 1.

For each pair of integers in Exercise 9, HW1, write the gcd as a linear combination.

Exercise 2.

Find all $n\in \mathbb{Z}$ satisfying each of the following equations.

1. $3n\equiv 2(mod7)$

2. $5n+1\equiv 13(mod23)$

3. $5n+1\equiv 13(mod26)$

4. $5n\equiv 1(mod6)$

5. $3n\equiv 1(mod6)$

Definition 1.

An equivalence relation on a set $S$ is a binary relation $\sim$ that is:

1. reflexive, that is, $a\sim a$ for all $a\in S$;

2. symmetric, that is, $a\sim b$ implies $b\sim a$ for all $a,b\in S$; and

3. transitive, that is, $a\sim b$ and $b\sim c$ implies $a\sim c$ for all $a,b,c\in S$.

Exercise 3.

Let $n\in \mathbb{N}$. Prove that equivalence modulo $n$ is an equivalence relation on $\mathbb{Z}$.

*Exercise 4.

Let $n\in \mathbb{N}$. Prove that given any $m\in \mathbb{Z}$ there exists a unique element $a\in \{0,1,2,\mathrm{\dots },n-1\}$ such that $m\equiv a(modn)$. (Hint: Use the division algorithm.)

Exercise 5.

Let $n\in \mathbb{N}$, and let $a,b\in \mathbb{Z}$. Prove that if $a\equiv b(modn)$, then

$$\gcd (a,n)=\gcd (b,n).$$

*Exercise 6.

Let $n\in \mathbb{N}$ with $n>1$, and let $a\in \mathbb{Z}$.

1. Prove that if $\gcd (a,n)=1$ and $b,c\in \mathbb{Z}$ such that $ab\equiv ac(modn)$, then $b\equiv c(modn)$.

2. Give an example of integers $n,a,b,c$ such that $a\not\equiv 0(modn)$, $b\not\equiv c(modn)$, and $ab\equiv ac(modn)$.

**Exercise 7.

Let $m,n\in \mathbb{N}$ be relatively prime, and let $a,b\in \mathbb{Z}$. Prove that there exists $x\in \mathbb{Z}$ such that

$x$ $\equiv a(modm)$

$x$ $\equiv b(modn).$

(Hint: Start by writing 1 as a linear combination of $m$ and $n$.)

Exercise 8.

Let $n\in \mathbb{N}$.

1. Prove that ${10}^n\equiv 1(mod9)$. (There are numerous ways to see this. One way is to use induction.)

2. (Divisibility by 9) Define $h:\mathbb{N}\to \mathbb{Z}$ by

   $$h(n)=\sum _{j=0}^k{a}_j,$$

   where

   $$n=\sum _{j=0}^k(a_j\cdot {10}^j).$$

   In words, $h(n)$ is the sum of the digits of $n$ when written in base 10. For example, if $n=27301$, then $h(n)=1+0+3+7+2=13$. Prove the following statement: Let $n\in \mathbb{N}$. Then, $9\mid n$ if and only if $9\mid h(n)$. (Hint: You will have to use part (a).)

*Exercise 9.

Let $n\in \mathbb{N}$.

1. Prove that ${10}^n\equiv {(-1)}^n(mod11)$. (Hint: use induction.)

2. (Divisibility by 11) Define $f:\mathbb{N}\to \mathbb{Z}$ by

   $$f(n)=\sum _{j=0}^k{(-1)}^j{a}_j,$$

   where

   $$n=\sum _{j=0}^k(a_j\cdot {10}^j).$$

   In words, $f(n)$ is the alternating sum of the digits of $n$ when written in base 10. For example, if $n=27301$, then $f(n)=1-0+3-7+2=-1$. Prove the following statement: Let $n\in \mathbb{N}$. Then, $11\mid n$ if and only if $11\mid f(n)$. (Hint: You will have to use part (a).)

Exercise 10.

Let $D_4$ denote the set of all rigid motions of a square.

1. Describe all the elements of $D_4$. (You do not need to prove you have them all, but do your best. We will do an official count in class at a later date.)

2. Every rigid motion of the square permutes its vertices. Describe a permutation of the vertices of the square that cannot be obtained via a rigid motion. (It will be helpful to know something about distances, so you may assume the Pythagorean theorem: $a^2+b^2=c^2$, where $a$ and $b$ are the lengths of the legs of a right triangle and $c$ is the length its hypotenuse.)

*Exercise 11.

Let $D_{\mathrm{\infty }}$ denote the set of bijections $\{f:\mathbb{Z}\to \mathbb{Z}:|f(n)-f(m)|=|n-m|\}$. Alternatively, $D_{\mathrm{\infty }}$ is the set of rigid motions of the tick-mark pattern shown in Figure 1.

1. Describe the elements of $D_{\mathrm{\infty }}$. (Note there are infinitely many.)

2. Find a finite generating set for $D_{\mathrm{\infty }}$.

Figure 1: A pattern whose set of rigid motions is $D_{\mathrm{\infty }}$. The dots indicate that the pattern repeates indefinitely to the right and to the left.

**Exercise 12.

Let $S_{2\mathrm{\infty }}$ denote the set rigid motions of the Frieze pattern shown in Figure 2.

1. Describe the elements of $S_{2\mathrm{\infty }}$. (Note there are infinitely many.)

2. Find a finite generating set for $S_{2\mathrm{\infty }}$.

Figure 2: A frieze pattern. The dots indicate that the pattern repeates indefinitely to the right and to the left.

Exercises 13–16 each ask you to establish that a given set with an associated binary operation is a group. In each case, you can assume that the operation is associative, so you only need to establish an identity element and inverses.

Exercise 13.

Complete Exercise 2 in Section 3.5 of the textbook.

Exercise 14.

Recall that the complex numbers are the set $ℂ=\{x+iy:x,y\in ℝ\}$, where $i^2=-1$. For $z=x+iy\in ℂ$, we let $\overline{z}=x-iy$ and $|z|=\sqrt{z\overline{z}}=\sqrt{x^2+y^2}$. Let $𝕋=\{z\in ℂ:|z|=1\}$, so that $𝕋$ is the unit circle. Prove that $𝕋$, equipped with complex multiplication, is a group.

Exercise 15.

Prove that the set of matrices of the form

is a group under matrix multiplication. (This group is called the Heisenberg group. It is important in many areas, including quantum physics and robotic motions.)

*Exercise 16.

Let $p\in \mathbb{N}$. Let $\mathrm{GL}(2,p)$ denote the set of non-zero-determinant $2\times 2$ matrices with entries in ${\mathbb{Z}}_p$, that is,

Prove that $\mathrm{GL}(2,p)$ is a group if and only if $p$ is prime. (Hint: the formula for the inverse of a 2-by-2 matrix you learned in linear algebra is still going to be valid! But be careful: what is a fraction?)

Exercise 17.

Let $G$ be a group. Prove that for any $g_1,g_2,\mathrm{\dots },g_n\in G$, the inverse of $g_1{g}_2\mathrm{\cdots }{g}_n$ is $g_n^{-1}{g}_{n-1}^{-1}\mathrm{\cdots }{g}_1^{-1}$. (This is an induction problem.)

Exercise 18.

Let $U(n)$ be the group of units in ${\mathbb{Z}}_n$, i.e., $U(n)=\{\overline{a}:\gcd (a,n)=1\}$ equipped with multiplcation modulo $n$. If $n>2$, prove that there is an element $k\in U(n)$ such that $k^2=\overline{1}$ and $k\ne \overline{1}$.

Exercise 19.

Show that if $a^2=e$ for every element $a$ in a group $G$, then $G$ is abelian.

Exercise 20.

Show that if $G$ is a finite group of even order, then there exists $a\in G$ such that $a$ is not the identity and $a^2=e$.

*Exercise 21.

Let $G$ be a group. Prove that if ${(ab)}^2=a^2{b}^2$ for all $a$ and $b$ in $G$, then $G$ is abelian.