Last updates: 1 July 2011
(1) Week 1: Vocabulary
(2) Week 1: Results
(3) Week 1: Examples and Computations
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
 
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}$? 
(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 $ab$ and $bc$ then $ac$.  
Let $a,b$, and $c$ be integers. Show that if $ab$ and $ac$ then ${a}^{2}\left\right({b}^{2}+3{c}^{2})$.  
Show that if $a,b,c,d$ are integers such that $ab$ and $cd$ then $acbd$.  
Prove that if $a,b,c,d,x,y$ are integers such that $ab$ and $ac$ then $a\left\right(xb+yc)$.  
Prove that if $a,b$ are positive integers such that $ab$ and $ba$ 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
 
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 $dab$ and $\mathrm{gcd}(a,d)=1$ then $db$.  
Let $p,a,b\in \mathbb{Z}$. Show that if $p$ is prime and $pab$ then $pa$ then or $pb$.  
Give an example of positive integers $a,b,c$ such that $ac$ and $bc$ but $ab\nmid c$.  
Let $a,b,c\in \mathbb{Z}$ be integers with $\mathrm{gcd}(a,b)=1$. Prove that if $ac$ and $bc$ then $abc$.  
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 $\mathrm{gcd}(a,m)=1$.  
Let $p\in \mathbb{Z}$ be prime. Show that every nonzero 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$  
 

 
 
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=\mathrm{gcd}(27,33)$ find integers $x$ and $y$ such that $d=x27+y33$.  
Find $d=\mathrm{gcd}(27,32)$ find integers $x$ and $y$ such that $d=x27+y32$.  
Find $d=\mathrm{gcd}(312,377)$ find integers $x$ and $y$ such that $d=x312+y377$.  
 
 
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 $35=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}$.  
 
 
 
 
Calculate $24\cdot 25$ (mod 21).  
Calculate $84\cdot 125$ (mod 210).  
Calculate ${25}^{2}+24\cdot 36$ (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.  
 
Simplify the following, giving your answers in the form $a$ mod $m$,
where $0\le a<m$.
 
For the following, write your answers in the form 0, 1, . . . , 18 (mod 19).
 
(A test for divisibility by 11.) Let
$n={a}_{d}{a}_{d1}\cdots {a}_{2}{a}_{1}{a}_{0}$
be a positive integer written in base 10, i.e.
$n={a}_{0}+10{a}_{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.
 
 
Find the smallest positive integer in the set $\{6u+15v\phantom{\rule{0.5em}{0ex}}\phantom{\rule{0.5em}{0ex}}u,v\in \mathbb{Z}\}$. Always justify your answers. 
[GH] J.R.J. Groves and C.D. Hodgson, Notes for 620297: Group Theory and Linear Algebra, 2009.