Week 1 Problem Sheet
Group Theory and Linear algebra
Semester II 2011

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 1 July 2011

(1) Week 1: Vocabulary
(2) Week 1: Results
(3) Week 1: Examples and Computations

Week 1: Vocabulary

	Define set, subset and equal sets and give some illustrative examples.
	Define union of sets, intersection of sets, and product of sets and give some illustrative examples.
	Define partition of a set and give some illustrative examples.
	Define relation, symmetric relation, reflexive relation and transitive relation and give some illustrative examples.
	Define equivalence relation and equivalence class and give some illustrative examples.
	Define the order $\le$ on $\mathbb{Z}$ and give some illustrative examples.
	Define well ordered set and give some illustrative examples.
	Let $d\in \mathbb{Z}$. Define the ideal generated by $d$ and give some illustrative examples.
	Let $d,a\in \mathbb{Z}$ and define (i)   $d$ divides $a$, (ii)   $d$ is a factor of $a$, (iii)   $a$ is a multiple of $d$, and give some illustrative examples.
	Let $a,b\in \mathbb{Z}$. Define greatest common divisor of $a$ and $b$ and give some illustrative examples.
	Define relatively prime integers and give some illustrative examples.
	Define prime integer and give some illustrative examples.
	Let $m\in \mathbb{Z}$. Define congruence modulo $m$ and give some illustrative examples.
	Let $m\in \mathbb{Z}$. Define congruence class modulo $m$ and give some illustrative examples.
	Define ${\mathbb{Z}}_{>0}$ and give some illustrative examples.
	Define ${\mathbb{Z}}_{>0}$ and the operations of addition and multiplication on ${\mathbb{Z}}_{>0}$ and give some illustrative examples.
	Define ${\mathbb{Z}}_{\ge 0}$ and give some illustrative examples.
	Define ${\mathbb{Z}}_{\ge 0}$ and the operations of addition and multiplication on ${\mathbb{Z}}_{\ge 0}$ and give some illustrative examples.
	Define $\mathbb{Z}$ and give some illustrative examples.
	Define $\mathbb{Z}$ and the operations of addition and multiplication on $\mathbb{Z}$ and give some illustrative examples.
	Let $m\in \mathbb{Z}$. Define $\mathbb{Z}/m\mathbb{Z}$ and give some illustrative examples.
	Let $m\in \mathbb{Z}$. Define $\mathbb{Z}/m\mathbb{Z}$ and the operations of addition and multiplication on $\mathbb{Z}/m\mathbb{Z}$ and give some illustrative examples.
	Let $m\in \mathbb{Z}$. Define multiplicative inverse in $\mathbb{Z}/m\mathbb{Z}$ and give some illustrative examples.
	Which sets are the three elements of $\mathbb{Z}/3\mathbb{Z}$?

Week 1: Results

	(Division with remainder) Show that if $a,d\in \mathbb{Z}$ and $d>0$ then there exist unique integers $q$ and $r$ such that $0\le r<d$ and $a=qd+r$.
	Let $a,b,c\in \mathbb{Z}$. Show that if $a|b$ and $b|c$ then $a|c$.
	Let $a,b$, and $c$ be integers. Show that if $a|b$ and $a|c$ then $a^2\left|\right(b^2+3c^2)$.
	Show that if $a,b,c,d$ are integers such that $a|b$ and $c|d$ then $ac|bd$.
	Prove that if $a,b,c,d,x,y$ are integers such that $a|b$ and $a|c$ then $a\left|\right(xb+yc)$.
	Prove that if $a,b$ are positive integers such that $a|b$ and $b|a$ then $a=b$.
	Show that if $a,d\in \mathbb{Z}$ and $q_1,r_1,q_2,r_2\in \mathbb{Z}$ and $0\le r_1<d$ and $0\le r_2<d$ and $a=q_{1}d+r_1$ and $a=q_{2}d+r_2$ then $q_1=q_2$ and $r_1=r_2$.
	Let $a,b\in \mathbb{Z}$. Show that (a)   $\gcd (a,b)=\gcd (b,a)=\gcd (-a,b)$, (b)   $\gcd (a,0)=a$, (c)   If $q$ and $r$ are integers such that $a=bq+r$ then $\gcd (a,b)=\gcd (b,r)$.
	Let $a,b\in \mathbb{Z}$ and let $d$ be the greatest common divisor of $a$ and $b$. Show that there exist integers $x$ and $y$ such that $ax+by=d$.
	Let $a,b\in \mathbb{Z}$ and let $d$ be the greatest common divisor of $a$ and $b$. Show that $d$ is the largest integer that divides both $a$ and $b$.
	Let $d,a,b\in \mathbb{Z}$. Show that if $d|ab$ and $\gcd (a,d)=1$ then $d|b$.
	Let $p,a,b\in \mathbb{Z}$. Show that if $p$ is prime and $p|ab$ then $p|a$ then or $p|b$.
	Give an example of positive integers $a,b,c$ such that $a|c$ and $b|c$ but $ab\nmid c$.
	Let $a,b,c\in \mathbb{Z}$ be integers with $\gcd (a,b)=1$. Prove that if $a|c$ and $b|c$ then $ab|c$.
	Let $m\in {\mathbb{Z}}_{\ge 0}$. Prove that congruence mod $m$ is an equivalence relation.
	Let $m\in {\mathbb{Z}}_{\ge 0}$. Prove that the operation of addition on $\mathbb{Z}/m\mathbb{Z}$ is well defined.
	Let $m\in {\mathbb{Z}}_{\ge 0}$. Prove that the operation of multiplication on $\mathbb{Z}/m\mathbb{Z}$ is well defined.
	Let $m\in {\mathbb{Z}}_{\ge 0}$ and let $a\in \mathbb{Z}$. Prove that $\left[a\right]$ has a multiplicative inverse in $\mathbb{Z}/m\mathbb{Z}$ if and only if $\gcd (a,m)=1$.
	Let $p\in \mathbb{Z}$ be prime. Show that every non-zero element of $\mathbb{Z}/p\mathbb{Z}$ has a multiplicative inverse.
	Prove that if $a=b$ mod $m$ and $b=c$ mod $m$ then $a=c$ mod $m$
	(a)   Prove that if $a,b,c$ are integers with $ac=bc$ mod $m$ and $\gcd (c,m)=1$ then $a=b$ mod m. (b)   Give an example to show that this result fails if we drop the condition that $\gcd (c,m)=1$. (c)   What can you conclude if $\gcd (c,m)=d$?
	(a)   Show that if $p$ is prime, then $p$ divides the binomial coefficient $\left(\genfrac{}{}{0ex}{}{p}{k}\right)=\frac{p\text{!}}{p\text{!}(p-k)\text{!}}$, for $0<k<p$. (b)   Deduce, using induction on $n$ and the binomial theorem, that if $p$ is prime then $n^p=n$ mod $p$, for all natural numbers $n$ (“Fermat’s Little Theorem”).

Week 1: Examples and Calculations

	(a)   Find the quotient and remainder when 25 is divided by 3. (b)   Find the quotient and remainder when 68 is divided by 7. (c)   Find the quotient and remainder when −33 is divided by 7. (d)   Find the quotient and remainder when -25 is divided by 3.
	(a)   Find the quotient and remainder when 25 is divided by -3. (b)   Find the quotient and remainder when -25 is divided by -3. (c)   Find the quotient and remainder when 25 is divided by 0. (d)   Find the quotient and remainder when 0 is divided by 25.
	Show that gcd(4, 6) = 2.
	Show that gcd(10, −20) = 10.
	Show that gcd(7, 3) = 1.
	Show that gcd(0, 5) = 5.
	Show that 12 and 35 are relatively prime.
	Show that 12 and 34 are not relatively prime.
	Find gcd(4163, 8869).
	Solve the equation $131x+71y=1$. Explain why this question is not well stated. Fix up the question and solve it.
	Using Euclid’s Algorithm find gcd(14, 35).
	Using Euclid’s Algorithm find gcd(105, 165).
	Using Euclid’s Algorithm find gcd(1287, 1144).
	Using Euclid’s Algorithm find gcd(1288, 1144).
	Using Euclid’s Algorithm find gcd(1287, 1145).
	Find $d=\gcd (27,33)$ find integers $x$ and $y$ such that $d=x27+y33$.
	Find $d=\gcd (27,32)$ find integers $x$ and $y$ such that $d=x27+y32$.
	Find $d=\gcd (312,377)$ find integers $x$ and $y$ such that $d=x312+y377$.
	(a)   Show that $3=1$ mod 2. (b)   Show that $3=17$ mod 17.
	(a)   Show that $3=-15$ mod 9. (b)   Show that $4=0$ mod 2.
	Show that $6\ne 1$ mod 4.
	Explain the most efficient way to calculate ${29}^4$ modulo 12.
	Show that $3+4=1$, $3\cdot 5=3$, and $3-5=4$ in $\mathbb{Z}/6\mathbb{Z}$.
	Write down the addition and multiplication tables for $\mathbb{Z}/5\mathbb{Z}$ and $\mathbb{Z}/6\mathbb{Z}$.
	Show that 2 has no multiplicative inverse in $\mathbb{Z}/4\mathbb{Z}$.
	Find the multiplicative inverse of 71 in $\mathbb{Z}/\mathrm{131}\mathbb{Z}$.
	(a)   Decide whether 3 = 42 (mod 13). (b)   Decide whether 2 = −20 (mod 11). (c)   Decide whether 26 = 482 (mod 14).
	(a)   Decide whether −2 = 933 (mod 5). (b)   Decide whether −2 = 933 (mod 11). (c)   Decide whether −2 = 933 (mod 55).
	(a)   Simplify 482 (mod 14). (b)   Simplify 511 (mod 9). (c)   Simplify −374 (mod 11).
	(a)   Simplify 933 (mod 55). (b)   Simplify 102725 (mod 10). (c)   Simplify 57102725 (mod 9).
	Calculate $24\cdot 25$ (mod 21).
	Calculate $84\cdot 125$ (mod 210).
	Calculate ${25}^2+24\cdot 3-6$ (mod 9).
	Calculate ${36}^3-3\cdot 19+2$ (mod 11).
	Calculate $1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6$ (mod 7),
	Calculate $1\cdot 2\cdot 3\cdots 20\cdot 21$ (mod 22).
	Use congruences modulo 9 to show that the following multiplication in $\mathbb{Z}$ is incorrect: $326\cdot 4471=1357546$.
	Determine the multiplicative inverses in $\mathbb{Z}/7\mathbb{Z}$.
	Determine the multiplicative inverses in $\mathbb{Z}/8\mathbb{Z}$,
	Determine the multiplicative inverses in $\mathbb{Z}/12\mathbb{Z}$,
	Determine the multiplicative inverses in $\mathbb{Z}/13\mathbb{Z}$,
	Determine the multiplicative inverses in $\mathbb{Z}/15\mathbb{Z}$,
	If it exists, find the multiplicative inverse of 32 in $\mathbb{Z}/27\mathbb{Z}$.
	If it exists, find the multiplicative inverse of 32 in $\mathbb{Z}/39\mathbb{Z}$.
	If it exists, find the multiplicative inverse of 17 in $\mathbb{Z}/41\mathbb{Z}$.
	If it exists, find the multiplicative inverse of 18 in $\mathbb{Z}/33\mathbb{Z}$.
	If it exists, find the multiplicative inverse of 200 in $\mathbb{Z}/911\mathbb{Z}$.
	Write down all the common divisors of 56 and 72.
	(a)   Use Euclid’s algorithm to find $d=\gcd (323,377)$. (b)   Find integers $x,y$ such that $323x+377y=d$.
	Simplify the following, giving your answers in the form $a$ mod $m$, where $0\le a<m$. (a)   $14\cdot 13-67+133$ (mod 10), (b)   53 (mod 7), (c)   $53+2\cdot 4$ (mod 7), (d)   $21\cdot 22\cdot 23\cdot 24\cdot 25$ (mod 20).
	For the following, write your answers in the form 0, 1, . . . , 18 (mod 19). (a)   Calculate $3^2,3^4,3^8,3^{16},3^{32},3^{64},3^{128}$ and $3^{256}$ modulo 19. (b)   Use (a) to calculate $3^{265}$ modulo 19. (Hint: 265 = 256 + 8 + 1.)
	(A test for divisibility by 11.) Let $n=a_d{a}_{d-1}\cdots a_2{a}_1{a}_0$ be a positive integer written in base 10, i.e. $n=a_0+10a_1+{10}^2{a}_2+\cdots +{10}^d{a}_d$, where $a_0,a_1,\dots a_d$, are the digits of the number $n$ read from right to left. (a)   Show that $n=a_0-a_1+a_2-a_3+\cdots +{(-1)}^d{a}_d$ mod 11. Hence $n$ is divisible by 11 exactly when $a_0-a_1+a_2-a_3+\cdots +{(-1)}^d{a}_d$ is divisible by 11. (b)   Use this test to decide if the following numbers are divisible by 11: (i) 123537, (ii) 30639423045.
	(a)   Write down the addition and multiplication tables for $\mathbb{Z}/7\mathbb{Z}$. (b)   Find the multiplicative inverse of 2 in $\mathbb{Z}/7\mathbb{Z}$.
	Find the smallest positive integer in the set $\{6u+15v|u,v\in \mathbb{Z}\}$. Always justify your answers.

References

[GH] J.R.J. Groves and C.D. Hodgson, Notes for 620-297: Group Theory and Linear Algebra, 2009.