%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{makeidx}
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="31">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="Exercises">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Thu Feb 13 16:58:53 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=MathHelp.cst}
%TCIDATA{<LINK REL="first" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="contents" HREF="DM0-0.tex">}
%TCIDATA{<LINK REL="end" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="index" HREF="DMIndex.tex">}
%TCIDATA{<LINK REL="parent" HREF="DM12.tex">}
%TCIDATA{<LINK REL="previous" HREF="DM12-5.tex">}
%TCIDATA{<LINK REL="top" HREF="DM0-0.tex">}

\input{tcilatex}
\begin{document}


\section{Exercises\label{Exercises}}

\begin{enumerate}
\item[1.]  \label{q1}Give a multiplication table for the integers modulo $11$%
. From the table, find the inverses of $2$ and $3$. Verify your answers by
evaluating $2^{-1}\limfunc{mod}11$ and $3^{-1}\limfunc{mod}11$.\hfill 
\hyperref{\TCIIcon{BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}}{}{}{a1}

\item[2.]  \label{q2}Solve the congruence $5x+4\equiv 8\,\left( \limfunc{mod}%
13\right) $. Verify your answer by evaluating $5x+3\limfunc{mod}13$.\hfill 
\hyperref{\TCIIcon{BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}}{}{}{a2}

\item[3.]  \label{q3}A jar of jelly beans sits on a table. If the jelly
beans are evenly divided among five children, there are three jelly beans
left over; and if the jelly beans are evenly divided among seven adults,
there are five jelly beans left over. How many jelly beans are in the jar?
Are other solutions possible? If so, what are they?\hfill \hyperref{\TCIIcon{%
BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}}{}{}{a3}

\item[4.]  \label{q4}What is the smallest $100$-digit prime?\hfill \hyperref{%
\TCIIcon{BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}}{}{}{a4}

\item[5.]  \label{q5}If $p$ is the smallest $100$-digit prime, what is $%
2^{p-1}\limfunc{mod}p$? What is $2^{(p-1)/2}\limfunc{mod}p$? What about $%
2^{(p-1)/4}\limfunc{mod}p$?\hfill \hyperref{\TCIIcon{BITMAPSETAnswer}{%
0.2006in}{0.1859in}{0in}}{}{}{a5}

\item[6.]  \label{q6}The matrix $M=\left[ 
\begin{array}{ccc}
1 & 1 & 1 \\ 
1 & 2 & 4 \\ 
1 & 4 & 9
\end{array}
\right] $ is used as a block cipher modulo 26 to scramble letters in a
message, three letters at a time. Assume $A\leftrightarrow 0$, $%
B\leftrightarrow 1$, $C\leftrightarrow 2$, and so forth. Descramble the
ciphertext $FKBHRTMTU$.\hfill \hyperref{\TCIIcon{BITMAPSETAnswer}{0.2006in}{%
0.1859in}{0in}}{}{}{a6}

\item[7.]  \label{q7}Find an irreducible polynomial of degree $3$. Use this
polynomial to describe how to calculate sums and products in the field $%
GF_{27}$.\hfill \hyperref{\TCIIcon{BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}%
}{}{}{a7}

\item[8.]  \label{q8}A barge company transports bales of hay and barrels of
beer up the Mississippi River. The company charges \$2.30 for each bale of
hay and \$3.00 for each barrel of beer. The bales of hay average 75 pounds
and take up 5 cubic feet of space; the barrels of beer weigh 100 pounds and
take up 4 cubic feet of space. A barge is limited to a payload of 150,000
pounds and 8,000 cubic feet. How much beer and how much hay should a barge
transport to maximize the shipping charges?\hfill \hyperref{\TCIIcon{%
BITMAPSETAnswer}{0.2006in}{0.1859in}{0in}}{}{}{a8}
\end{enumerate}

\section{Solutions\label{Solutions}}

\begin{enumerate}
\item[1.]  \label{a1}Define the function $f(i,j)=ij$. From the \textsf{Matrix%
} submenu, choose \textsf{Fill Matrix} with 10 rows and 10 columns, and use
the function $f$ to generate a matrix. Then, reduce the matrix $\limfunc{mod}%
11$ to get the following: \hfill \hyperref{\TCIIcon{BITMAPSETProbSolvHint}{%
0.1807in}{0.2197in}{0in}}{}{}{q1} 
\[
\fbox{$
\begin{array}{cccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 
2 & 4 & 6 & 8 & 10 & 1 & 3 & 5 & 7 & 9 \\ 
3 & 6 & 9 & 1 & 4 & 7 & 10 & 2 & 5 & 8 \\ 
4 & 8 & 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 \\ 
5 & 10 & 4 & 9 & 3 & 8 & 2 & 7 & 1 & 6 \\ 
6 & 1 & 7 & 2 & 8 & 3 & 9 & 4 & 10 & 5 \\ 
7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\ 
8 & 5 & 2 & 10 & 7 & 4 & 1 & 9 & 6 & 3 \\ 
9 & 7 & 5 & 3 & 1 & 10 & 8 & 6 & 4 & 2 \\ 
10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
$}
\]
Select the matrix, from the \textsf{Edit} menu choose \textsf{Insert
Column(s)}, and add 1 column at position 1. You have now added a column on
the left. Repeat this procedure using \textsf{Insert Row(s)}, adding a row
at position 1. Fill in the empty boxes with $\times $ and the integers 1
through 10 to generate the final multiplication table, 
\[
\fbox{$
\begin{array}{ccccccccccc}
\times  & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 
1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 
2 & 2 & 4 & 6 & 8 & 10 & 1 & 3 & 5 & 7 & 9 \\ 
3 & 3 & 6 & 9 & 1 & 4 & 7 & 10 & 2 & 5 & 8 \\ 
4 & 4 & 8 & 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 \\ 
5 & 5 & 10 & 4 & 9 & 3 & 8 & 2 & 7 & 1 & 6 \\ 
6 & 6 & 1 & 7 & 2 & 8 & 3 & 9 & 4 & 10 & 5 \\ 
7 & 7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\ 
8 & 8 & 5 & 2 & 10 & 7 & 4 & 1 & 9 & 6 & 3 \\ 
9 & 9 & 7 & 5 & 3 & 1 & 10 & 8 & 6 & 4 & 2 \\ 
10 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
$}
\]
From the table, $2\cdot 6=1$ implies $2^{-1}=6$, and $3\cdot 4=1$ implies $%
3^{-1}=4$. As a check, $2^{-1}\limfunc{mod}11=6$ and $3^{-1}\limfunc{mod}11=4
$.

\item[2.]  \label{a2}The solution is given by $x=(8-4)/5\limfunc{mod}13=\,6$%
. As a check, $6\cdot 5+4\limfunc{mod}13=\,8$.\hfill \hyperref{\TCIIcon{%
BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{}{}{q2}

\item[3.]  \label{a3}The problem requires the solution to the system 
\begin{eqnarray*}
x &\equiv &3\;\left( \limfunc{mod}5\right) \\
x &\equiv &5\;\left( \limfunc{mod}7\right)
\end{eqnarray*}
of congruences. The system is equivalent to the equation $x=3+5a=5+7b$, or $%
3+5a\equiv 5\;\left( \limfunc{mod}7\right) $, which has a solution $a=(5-3)/5%
\limfunc{mod}7=6$, which means $x=3+5a=33$ jelly beans. Other possible
solutions are $x=33+35n$, where $n$ is any positive integer.\hfill \hyperref{%
\TCIIcon{BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{}{}{q3}

\item[4.]  \label{a4}Define the function $\limfunc{nextp}$ as indicated in
this chapter. Then $\limfunc{nextp}(10^{99})$ produces a number with lots of
zeroes that ends in 289. The prime $p$ can be written as $p=10^{99}+289$%
.\hfill \hyperref{\TCIIcon{BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{%
}{}{q4}

\item[5.]  \label{a5}Note that $2^{p-1}\limfunc{mod}p=1$ and $2^{(p-1)/2}%
\limfunc{mod}p=1$, whereas $2^{(p-1)/4}\limfunc{mod}p$ produces another
number with lots of zeroes that ends in $288$. More precisely, $%
2^{(p-1)/4}\equiv -1\limfunc{mod}p$. This congruence illustrates the fact
that, if $p$ is a prime, then $x^{2}\equiv 1\;\left( \limfunc{mod}p\right) $
has only two solutions, $x\equiv 1\;\left( \limfunc{mod}p\right) $ and $%
x\equiv -1\;\left( \limfunc{mod}p\right) $.\hfill \hyperref{\TCIIcon{%
BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{}{}{q5}

\item[6.]  \label{a6}We have $\left[ 
\begin{array}{ccc}
1 & 1 & 1 \\ 
1 & 2 & 4 \\ 
1 & 4 & 9
\end{array}
\right] ^{-1}\limfunc{mod}26=\left[ 
\begin{array}{ccc}
24 & 5 & 24 \\ 
5 & 18 & 3 \\ 
24 & 3 & 25
\end{array}
\right] $. The ciphertext \textsf{F\ K\ B\ H\ R\ T\ M\ T\ U} has a numerical
equivalent of $\left[ 5,10,1,7,17,19,12,19,20\right] $. Picking three at a
time, we get 
\[
\left[ 
\begin{array}{ccc}
24 & 5 & 24 \\ 
5 & 18 & 3 \\ 
24 & 3 & 25
\end{array}
\right] \left[ 
\begin{array}{ccc}
5 & 7 & 12 \\ 
10 & 17 & 19 \\ 
1 & 19 & 20
\end{array}
\right] \limfunc{mod}26=\left[ 
\begin{array}{ccc}
12 & 7 & 5 \\ 
0 & 8 & 20 \\ 
19 & 18 & 13
\end{array}
\right] 
\]
The vector $\left[ 12,0,19,7,8,18,5,20,13\right] $ corresponds to the
plaintext \textsf{M\ A\ T\ H\ I\ S\ F\ U\ N}, or \textsf{MATH\ IS\ FUN}%
.\hfill \hyperref{\TCIIcon{BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{%
}{}{q6}

\item[7.]  \label{a7}Defining $g(x)=x^{3}+x+1$, we see that $g(1)\limfunc{mod%
}3=0$, and hence $g(x)$ is not irreducible (since it has a root in $GF_{3}$%
). However, if $f(x)=x^{3}+2x+1$, then $f(0)\limfunc{mod}3=1$, $f(1)\limfunc{%
mod}3=1$, and $f(2)\limfunc{mod}3=1$, and hence $f(x)$ is irreducible. (If $%
f(x)$ were reducible, it would have a linear factor, and hence a root.) An
element of $GF_{27}$ can be thought of as a polynomial of degree less than 3
with coefficients in $GF_{3}$. Given the field elements $2x^{2}+x+2$ and $%
2x+1$, the product is $\left( \left( 2x^{2}+x+2\right) \left( 2x+1\right) 
\limfunc{mod}\;x^{3}+2x+1\right) \limfunc{mod}3=x^{2}+1$, and the sum is
given by $\left( 2x^{2}+x+2\right) +\left( 2x+1\right) \limfunc{mod}3=2x^{2}$%
.\hfill \hyperref{\TCIIcon{BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{%
}{}{q7}

\item[8.]  \label{a8}The objective function is $2.3h+3b$. The constraints
are $4h+5b\leq 8000$, $75h+100b\leq 150000$, $b\geq 0$, and $h\geq 0$. Apply 
\textsf{Maximize} from the \textsf{Simplex} submenu to the system 
\[
\begin{array}{c}
2.3h+3b \\ 
5h+4b\leq 8000 \\ 
75h+100b\leq 150000 \\ 
b\geq 0 \\ 
h\geq 0
\end{array}
\]
to get the result: \thinspace Maximum is $4550$ at $h=1000,b=750$.\hfill 
\hyperref{\TCIIcon{BITMAPSETProbSolvHint}{0.1807in}{0.2197in}{0in}}{}{}{q8}
\end{enumerate}

\label{Appendix}

\subsection{\ Related topics}

\hyperref{Solving Equations}{}{}{DM12-1.tex#Integer solutions}

\hyperref{Integers Modulo m}{}{}{DM12-2.tex#Integers modulo m}

\hyperref{Other Systems Modulo m}{}{}{DM12-3.tex#Matrices modulo m}

\hyperref{Polynomials Modulo Polynomials}{}{}{DM12-4.tex#Polynomials modulo
polynomials}

\hyperref{Linear Programming}{}{}{DM12-5.tex#Linear programming}

\rule{0.67in}{0.01in}

\hyperref{\FRAME{itbpF}{0.5275in}{0.3399in}{0.0519in}{}{}{index.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";display "PICT";valid-file
"F";width 0.5275in;height 0.3399in;depth 0.0519in;original-width
36.875pt;original-height 22.5625pt;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'index.wmf';file-properties "XNPEU";}}}{}{}{%
DMIndex.tex#Math Index}\quad {\small Index entries: \hyperref{Applied modern
algebra}{}{}{DMIndex.tex#Applied modern algebra}, \hyperref{Integers}{}{}{%
DMIndex.tex#Integers}, \hyperref{Linear programming}{}{}{DMIndex.tex#Linear
programming}, \hyperref{Matrices}{}{}{DMIndex.tex#Matrices}, \hyperref{%
Polynomials}{}{}{DMIndex.tex#Polynomials}, \hyperref{Simplex}{}{}{%
DMIndex.tex#Simplex}, \hyperref{Solve}{}{}{DMIndex.tex#Solve}}

\end{document}
