\documentclass{article}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{enumerate}
\newcommand{\noi}{\noindent}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\renewcommand{\c}{\gamma}
\renewcommand{\t}{\textrm}
\newcommand{\R}{\mathbb{R}}
\newcommand{\IFF}{\Leftrightarrow}
\newcommand{\thenif}{\Leftarrow}
\newcommand{\ifthen}{\Rightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\8}{\infty}
\newcommand{\bob}{
%begin{displaymath}
\left.\begin{array}}
\newcommand{\killbob}{
\end{array}\right.
}
\newcommand{\spacer}{\vskip .1 in}
\newcommand{\N}{\mathbb N}
\newcommand{\F}{\mathbb F}
\newcommand{\C}{\mathbb C}
\newcommand{\rectangle}[1]{\begin{tabular}{|c|}\hline \ensuremath{#1} \\
\hline\end{tabular}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\sixth}{\frac{1}{6}}
\newcommand{\third}{\frac{1}{3}}
\newcommand{\ret}{vskip.1in}
%\renewcommand{\mod}{\textrm{mod}}
%%\author{Nick Touikan}
\begin{document}
\begin{center}{\Large Basic Algebra 1\\Solutions to Assignment 3}\end{center}
\spacer
\noi{\bf Problem 1} The simplest way to do this is to check all the
cases, but to do less work we make the following observation: $ax
\equiv b \mod(n)$ and $ay \equiv b \mod(n) \IFF a(x-y) \equiv 0
\mod(b)$ (check it!). So if $x$ is a solution of $ax \equiv b
\mod(n)$ then the other solutions of the equation are of
the form $x+a'$ where $n \mid aa'$. We have, \\
(a) $3*4 \equiv 12 \equiv 5 \mod(7)$ and there are no other solutions because 7 is
prime.\\
(b) $3*4 \equiv 12 \equiv 1 \mod(11)$ and $x=4$ is the only solution.\\
(c) $3*2 \equiv 6 \mod(15)$ so we have $x=2$ is a solution but notice that
$15 \mid 3*5$ and $15 \mid 3*10$ so we have that $x=2+5=7$ is a solution and
$x=12$ is also a solution (moreover they are the only ones)\\
(d) We try for $x=0,1,2,3,4,5,6$ and notice that none of these work,
we can stop, why? We have that $6*7 \equiv 6*14 \equiv 0 \mod(21)$
so it follows that if $y$ is a solution to our equation, we can
chose $y<21$ and we also have that $y-7, y-14$ is a solution, thus
if there is a solution $21>y>6$ then there exists a solution $0 \leq
y'\leq 6$ but we checked that there were none.
\spacer
\noi{\bf Remark} In general one has the following result.
\spacer
{\it (i) The equation $ax\equiv b\mod m$ is soluble iff
gcd$(a,m)\mid b$.
(ii) If this is so, then there are exactly $d=$gcd$(a,m)$ solutions.
(iii) Given $x_0$ is one solution, then
$$x_0+\frac{m}{d},~x_0+2\frac{m}{d},\cdots,x_0+(d-1)\frac{m}{d}$$
are the other solutions.}
\spacer
\noi{\bf Problem 2} We compute the squares in $\Z_{8}$\[ \bob{l}
0^{2}=0\\ 1^{2} = 1 \\ 2^{2} = 4 \\ 3^{2} = 9 = 1\\ 4^{2} = 16 = 0 \\
5^{2}=25=1\\6^{2}=36=4\\7^{2}=49=1\\
\killbob \] We see that the possible sums of three squares are:
$$0+0+0=0;0+0+1=1;0+1+1=2;$$
$$1+1+1=3;0+0+4=4;0+1+4=5;1+1+4=6.$$
So seven can not be expressed as
a sum of three squares in $\Z_{8}$.
Now suppose towards a contradiction that every integer could be
expressed as a sum of three squares. Let $n \in [7]_{8}\subset \Z$
where $[7]_{8}$ is the equivalence class of integers congruent to 7
mod(8). Then by our supposition $n=a^{2}+b^{2}+c^{2}$ for some
$a,b,c \in \Z$, hence we have the congruence equation
$a^{2}+b^{2}+c^{2} \equiv n \equiv 7 \mod(8)$. This is a
contradiction, it follows that some integers (in particular 7) can
not be expressed as a sum of three squares. Note that 7 is the
smallest integer that can not be expressed as the sum of three
squares!
\spacer
\noi{\bf Problem 3} Show that $a^{5} \equiv a \mod(30)$ for all
integers $a$. We have the following equivalencies\[\bob{rl} &
a^{5} \equiv a \mod(30)\\ \IFF & a^{5}-a \equiv 0 \mod(30)\\
\IFF & 30 \mid a^{5}-a\\ \killbob \]
We also have that $30 \mid (a^{5}-a)$ if and only if $2,3$ and $5$ divide $a^{5}-a$.
One side of this implication is clear i.e. if $30 \mid x$ then $2,3$ and $5$ also
divide $x$. On the other hand suppose that $2,3$ and $5$ divide $x$. Then by the
fundamental theorem of arithmetic we have the unique prime factorization
$x=\pm 1*2^{\epsilon_{1}}*3^{\epsilon_{2}*}5^{\epsilon_{3}}*\ldots$ and in
particular we find that $\epsilon_{1},\epsilon_{2},\epsilon_{3}$ are all at
least 1. So $30=2*3*5$ divides $x$ as well. (It is sometimes useful to think
that $a$ divides $b$ if and only if $b$ ``contains'' $a$'s prime factorization.)
So if we show that $n \mid a^{5}-a$ for all $a$ when $n=2,3,5$, we're done. So
we check for each of them. I'll only do the case for $n=5$, we need to check for
$a=0,1,2,3,4$. When $a=0,1$ the equation clearly holds. For the rest:\[ \bob{rcl}
4^{5}=4^{2}*4^{2}*4&\equiv& 1*1*4 \equiv 4 \mod(5)\\
3^{5}=3^{2}*3^{2}*3&\equiv& (-1)*(-1)*3 \equiv 3 \mod(5)\\
2^{5}=4*2^{3}&\equiv& (-1)*3 \equiv 2 \mod(5)\\
\killbob \]
So we have that for each $a \in \Z$, $a^{5}\equiv a \mod(5)$. Similarly the
equations also hold for all $a$ modulo 2 and 3. We can therefore infer that
for all $a \in \Z, a^{5}\equiv a \mod(30)$.
\spacer
\noi{\bf Problem 4} We first consider $\Z_{11}$. We start checki and
find that in $\Z_{11}$:\[\bob{l}
2=2\\2^{2}=4\\2^{3}=8\\2^{4}=16=5\\2^{5}=2*5=10\\2^{6}=2*10=9\\2^{7}=2*9=7\\2^{8}=
2*7=3\\2^{9}=2*3=6\\2^{10}=2*6=1\\ \killbob \] So 2 is a primitive
root mod 11. And for the record, there is not really a nice way to
find such roots.
For $\Z_{24}$ a totally different approach is in order, checking every elements
will do the trick but it is too much work, especially because $\Z_{24}$ has no
such primitive roots. The two next propositions illustrate what's going on.
\spacer
\noi{\bf Proposition 1:} Let $R$ be a commutative ring and suppose that
$a,b \in R$ are such that $a,b \neq 0$ but $ab=0$, then $a$ may not have
a multiplicative inverse.
\noi Proof: Suppose that $a\neq 0$ did have a multiplicative inverse $a^{-1}$
but that there was some $b\neq 0$ such that $ab=0$. \[\bob{rl}
b~=&1*b\\
=&(a^{-1}a)b\\
=&a^{-1}(ab)=a^{-1}*0=0\\
&\ifthen b=0 \killbob \] Which is a contradiction.$\Box$ \spacer
\noi{\bf Proposition 2:} If every non-zero element of $\Z_{n}$ is a
power of some $a\in \Z_n$, then all non-zero elements of $\Z_n$ have
multiplicative inverses.
\noi Proof: Let $x\in \Z_{n}$ be any nonzero element. Then for some
$l,m \in \N$, $x=a^{l}$ and $a^{m}=1$. We may assume that $l2$ is prime, notice the following: Suppose there was some $[x]
\in \Z_{n}$ such that $[x]^{2}=[1]$. If $[x] \neq [1]$ or $[-1]$
then $[x+1], [x-1] \neq [0]$. Picking a representative $x_{0} \in
\Z$ from $[x]$ such that $x_{0}