\newfam\bbold
\def\bb#1{{\fam\bbold #1}}
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv

\newcount\indentlevel
\newcount\itno
\def\reset{\itno=1}\reset
\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
\aftergroup\afterstartlist}
\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
    s\or t\or u\or v\or w\or x\or y\or z\fi}
\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
                                  \alph\itno)\else
                                  (\number\itno)\fi
                           }%
         #1\smallskip\advance\itno by 1\relax}
\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
\let\endul\egroup
\def\hline{\noalign{\hrule}}
\let\impl\rightarrow
\newskip\tableskip
\tableskip=10pt plus 10pt
\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
\def\lcm{\mathop{\rm lcm}}

\li Find the prime factorization of each of these integers.

{\startlist

\li 9072

$9072 = 2^4\cdot 3^4\cdot 7.$

\li 324

$324 = 2^2\cdot 3^4.$

\li 6!

$6! = 2^4\cdot 3^2\cdot 5.$

}

\li Approximate the number of prime numbers not exceeding 50000. Show
your work.

The approximate number of primes less than $N$ is $N/\ln(N)$
$${50000\over\ln(50000)} \approx {50000\over 10.82} \approx 4621.$$

\li Determine whether the integers 2, 51, 101, and 119 are pairwise
relatively prime. Show your work for full credit.

These are the prime factorizations of the above numbers:

$2 = 2.$

$51 = 3\cdot 17.$

$101 = 101.$

$119 = 7\cdot 17.$

$51$ and $119$ are not coprime because they share the factor 17.
Every other pair is relatively prime.

\li What is the greatest common divisors of these pairs of integers?

{\startlist

\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$

$2^4*3^3*5^2.$

\li 19 and $19^1 8.$

19.
}

\li What is the least common multiple of these pairs of integers?

{\startlist

\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$

$2^5*3^3*5^6*7^2.$

\li $2^4*7$ and $5^5*13.$

$2^4*5^5*7*13.$

}

\li Find the least integer with $n$ distinct positive factors where $n$
is below. For example, if $n=4,$ then the solution is $6$ because
$1,2,3,6$ are distinct positive factors of $6$ and there are $n=4$ of
them.

{\startlist

\li 3

$4$ has factors $1,2,4.$

\li 5

$16$ has factors $1,2,4,8,16.$

\li 6

$12$ has factors $1,2,3,4,6,12.$

}

\li Use the Euclidean algorithm to find the following values. You must
clearly show all steps of your work using the Euclidean algorithm taught
in class.

{\startlist

\li $\gcd(100,101)$

$(100,101)\to (100, 1)\to (1, 0),$ giving $\gcd(100,101) = 1.$

\li $\gcd(64, 12)$

$(64, 12)\to (12, 4)\to (4, 0),$ giving $\gcd(64,12) = 4.$

}

\li Show your work by using the Chinese Remainder Theorem, find all
values $x$ such that

$x \equiv 1 \pmod{5}.$

$x \equiv 2 \pmod{6}.$

$x \equiv 3 \pmod{7}.$

\smallskip
5, 6, and 7 are pairwise coprime, so these congruences specify a unique
integer $n$ such that $x\equiv n \pmod{210}.$

$y_1 = 42,$ and $a_1 = 1,$ so $z_1 = 3.$

$y_2 = 35,$ and $a_2 = 2,$ so $z_2 = 5.$

$y_3 = 30,$ and $a_3 = 3,$ so $z_3 = 4.$

$a_1y_1z_1 + a_2y_2z_2 + a_3y_3z_3 \equiv 206 \bmod{210}.$

\li Decrypt the following ciphertext message: $HJUXDW,$ which was
encrypted first using a shift cipher, then using a transposition cipher.
The key of the shift cipher was $k=3,$ and the transposition cipher was
based on the permutation $\sigma$ of the set 1, 2, 3 with $\sigma(1) =
2$ and $\sigma(2) = 3$ and $\sigma(3) = 1.$

We start by computing a transposition $\sigma^{-1}(3) = 2$ and
$\sigma^{-1}(2) = 1$ and $\sigma^{-1}(1) = 3.$
The ciphertext becomes $JUHDWX.$
We then convert the ciphertext to numbers
$(9, 20, 7, 3, 22, 23)$ and subtract three to get
$(6, 17, 4, 0, 19, 20),$ and finally convert numbers to letters,
obtaining $GREATU.$

\li Suppose you intercept the message ``57 04 00 59 50 57 04 14 52 50 57
42 00 54'' that has been encrypted using the RSA algorithm. You know
that the public key used for encryption is $(65,7).$ Decrypt the message
to determine what was said. Use the process shown in lecture to complete
this problem. You must show all work. (If your calculator is unable to
calculate $a^d\bmod{n}$ where a is one of the numbers in the message above and
$d$ is the decryption key, then you can just show $a^d\bmod{n}$ for each value of
a. Note that this is the final step in decryption so you won't show what
the message actually was. You must still show the work for calculating
the decryption key $d$).

$n = 13\cdot 5 = p\cdot q.$
$\lcm(p-1,q-1) = 12.$
$7\cdot 7 \equiv 1 \pmod{12},$
so $d = 7$ (the multiplicative inverse of 7 mod 12)

We then compute $a^d\bmod{n}$ for each number in the message, obtaining
$(8,4,0,19,15,8,4,14,13,15,8,3,0,24)$ or $IEATPIEONPIDAY.$

\bye