Final Exam Study Guide

Problem 1
Let $a=135762$ and let $b=22091$ . Compute $\gcd(a,b)$ using the Euclidean algorithm and write the greatest common divisor in the form $ua+vb$ for integers $u$ and $v$ .

See The Euclidean Algorithm and Bezout’s Theorem

Problem 2
Let $a,b \in \mathbb{Z}$ , not both equal to $0$ , and let $d:= \gcd(a,b)$ . Show that

$\{ua+vb\mid u,v\in \mathbb{Z}\}=\{qd\mid q \in \mathbb{Z}\}$

Hint 1

You want to show the two sets are equal, so you must show that $\{ua+vb\mid u,v\in \mathbb{Z}\}\subseteq\{qd\mid q \in \mathbb{Z}\}$ and $\{ua+vb\mid u,v\in \mathbb{Z}\}\supseteq\{qd\mid q \in \mathbb{Z}\}$

Hint 2

For showing $\{ua+vb\mid u,v\in \mathbb{Z}\}\subseteq\{qd\mid q \in \mathbb{Z}\}$ , use the fact that $d\mid a$ and $d\mid b$ .

Hint 3

For showing $\{ua+vb\mid u,v\in \mathbb{Z}\}\supseteq\{qd\mid q \in \mathbb{Z}\}$ , apply Bezout’s Theorem for $d$ , then use this on the expression $qd$ .

Problem 3
Let $S$ and $T$ be rings and let $R:=S \times T$ .

Show that $R$ is again a ring if one defines $(s_1,t_1) + (s_2,t_2) := (s_1+s_2, t_1+t_2)$ and $(s_1,t_1)\cdot(s_2,t_2):= \cdot (s_1\cdot s_2, t_1 \cdot t_2)$ for $s_1,s_2 \in S$ and $t_1,t_2 \in T$ . What is the zero-element and what is the one-element of $R$ ?
Show that $R^\times = S^\times \times T^\times$ .

See Rings and Ring Homomorphisms

Problem 4
Let $\omega=e^{2\pi i/3}$ . So, $\omega$ is a primitive complex third root of unity. Let $R$ be the set of complex numbers given by

$R:=\mathbb{Z}[\omega]=\{x+ya\mid x,y \in \mathbb{Z}\}$

Prove that $R$ is a subring of the complex field and find the group of units of $R$ .

Hint 1

To show that $R$ is a subring of $\mathbb{C}$ , you need to show that $R$ is nonempty and for any $a,b \in R$ , $a-b \in R$ and $ab \in R$ .

Hint 2

Think about what the units of $\mathbb{Z}[i]=\{a+bi\mid a,b \in \mathbb{Z}\}$ are (there should be six units in $\mathbb{Z}[\omega]$ ).

Problem 5
Determine the units of the ring $\mathbb{Z}/34\mathbb{Z}$ and find their inverses.

See Finding Units and Inverses

Problem 6
Let $A$ be the matrix:

$A=\begin{pmatrix} 1 & 8 \\ 2 & 3 \end{pmatrix}$

Is $A$ an invertible matrix?

See Invertible Matrices Over Any Ring

Problem 7
Let $A$ be the matrix:

$A=\begin{pmatrix} 1 & 8 \\ 2 & 3 \end{pmatrix}$

Is $A$ an invertible matrix? \item Find an integer $x$ such that:

$\begin{align*} x&\equiv 0 \mod 3 \\ x&\equiv 4 \mod 7 \\ x &\equiv 1 \mod 11 \end{align*}$

See Finding Solutions to a System of Modular Equations

Problem 8
Let $n=n_k10^k + \cdots + n_2\cdot 100 + n_1 \cdot 10 + n_0$ with $n_0, \dots, n_k \in \{0,\dots,9\}$ . Thus, $n_0, \dots, n_k$ are the digits of $n$ as a decimal number. Show that

$n\equiv n_0 + n_1 + n_2 + \cdots + n_k \mod 9$
$3 \mid n \Leftrightarrow 3 \mid n_0 + n_1 + \cdots + n_k$ .
$9 \mid n \Leftrightarrow 9 \mid n_0 + n_1 + \cdots + n_k$ .
$n\equiv n_0-n_1+n_2-\cdots +(-1)^kn_k \mod 11$ .
$11 \mid n \Leftrightarrow 11 \mid n_0-n_1+n_2- \cdots +(-1)^kn_k$

Hint for (a)

What is $10^k \mod 9$ ? See Reducing Large Powers Using Modular Relations.

Hint for (b)

By (a), $n \equiv n_0+n_1+ \cdots +n_k \mod 9$ . If $3\mid n$ , then $n \equiv d\mod 9$ for what values of $d$ ?

Hint for (c)

By (a), $n \equiv n_0+n_1+ \cdots +n_k \mod 9$ . If $9\mid n$ , then $n \equiv d\mod 9$ for what values of $d$ ?

Hint for (d)

What is $10^k \mod 11$ ? Consider cases when $k$ is even or odd. See Reducing Large Powers Using Modular Relations.

Hint for (e)

By (d), $n \equiv n_0-n_1+ \cdots +(-1)^kn_k \mod 9$ . If $11\mid n$ , then $n \equiv d\mod 11$ for what values of $d$ ?

Problem 9
Compute $289^{3812} \mod 121$ .

See Reducing Large Powers Using Modular Relations

Problem 10

Assume the letters A-Z are labeled by 0, … , 25 and the blank is labeled by 26. Encipher the message “everything is ok” using the affine cryptosystem for $R=\mathbb{Z}/27\mathbb{Z}$ with the key $(a,b)=(8,13)$ .
Assume that the following message is enciphered with the labeling of letters and the blank as in part (a) using the an affine cryptosystem for $R=\mathbb{Z}/27\mathbb{Z}$ . Try to find the key $(a,b)$ using frequency analysis and decipher the message. The message is:
15 8 1 17 13 9 17 10 11 1 9 10 22 2 7 17 21 1 24 22 7 12 17 10 1 21 25 24 11 1 2 17 1 17 8 3 22 26 17 3 1 26 19 11 5 1 11 26 22 1 19 8 16 22 21 9 15 11 19 2 7 17 1 23 25 15 7 19 11 19 17 24 1 1 15 1 10 17 24 11 7 17 24 24 1 19 21 15 18 19 8 15 11 19 22 8 1 15 8 3 1 15 1 9 15 11 19 17 8 11 1 9 17 10 11 19 8 15 16 19 11 0 1 1 5 22 26 15 10 3 1 26 1 17 12 17 24
Assume you intercept the message “PSQIUF” and you know it has been enciphered using the affine digraph cryptosystem for the ring $R=\mathbb{Z}/729\mathbb{Z}$ and the labeling AA, AB, AC, … by the elements $0+729\mathbb{Z}$ , $1+729\mathbb{Z}$ , $2+729\mathbb{Z}$ , … with the key $(a,b)=(320,155)$ . Decipher the message.

See Affine Cryptosystem

Problem 11
Let $N=30$ and use the labeling of the alphabet A-Z (0-25), the blank (26), the comma ‘,’ (27), the period ‘.’ (28), and the question mark ‘?’ (29). Use the affine matrix crypto system with key $(A,B)$ , where

$A=\begin{pmatrix} 1+30\mathbb{Z} & -1 + 30\mathbb{Z} \\ 3 + 30\mathbb{Z} & -2 +30\mathbb{Z} \end{pmatrix} \text{ and } B = \begin{pmatrix} 4+ 30\mathbb{Z} \\ 1+30\mathbb{Z}\end{pmatrix}$

to encipher the message “WATERGATE”.

Affine Matrix Cryptosystem

Problem 12
You intercepted the message:

“U?DIPPWKCKIKFBWZERRXTV AXN,FG.SAYCHY
VTMIMBG.LHTV KCPEAF?.FSGGZ.YOQMZQL.D
WKLHYCHIVT,REEKQMJSLEAFXWWVFMKQQUQEW
OQHI .BOG.UN.JGNIZQYESRMOQGNWMTVZHF,
OKQYZQBLVNQ.MJSLMKQQUQRXKMJEG.ZH WRM
.HYNDV,REE,RGBJR.F?NFHMHGHSFMKTZPDKA
?EVJEM W?T MDOYU.FSFYCKWSHKNGEG.LH?N
FHMHGHSFOQCCESRM?N,RZBE,.HZZQLIHWWCZ
.KHIIJOWIHW..HQQUQUNRMJR.F?TWANUEGSE
GTSHFXWZGHDOOQGNVFMKWE,MBFE,.H,XOQWK
ZBOTRZON.ECJQLWZFXWZQQUQ.GMZCIG.VZKW
V.Q.NXVTG.QQUQ.USFMKBOBFEM WYCHIVTJR
.FJLVZGNMJSL?Z QIOWCESRMSFSWSEYRWK”

Assume you are using an affine matrix cryptosystem as in Problem 10. Assume that you further know that the plaintext message ends with the four letters “LES ” and that $B = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ in the enciphering key $(A,B)$ . Find the matrix $A$ of the enciphering key, compute the deciphering key and decipher the first 8 letters of the message.

See Week 7 Section Video

Problem 13

Find primes $p,q$ for yourself such that $n:=pq$ is in the range between $N^3=27000$ and $N^4=810000$ (where $N=30$ ). Find a possible $e$ for the RSA cryptosystem and compute the deciphering exponent $d$ .
Assume that with RSA cryptosystem somebody’s phone book entry is $(n,e)=(11247661,268729)$ and assume you found out that it is very likely that $a^{7169e}\equiv a \mod n$ for all $a \in \{0, \dots, n-1\}$ . Find the prime decomposition of $n$ using this information and the deciphering key $(n,d)$ from this information.

Check answer for (a)

For (b), see Week 8 Section Video

Problem 14
If $n$ is not prime, is it true that $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic?

Hint

Check the multiplicative group of the ring $\mathbb{Z}/8\mathbb{Z}$ .

Problem 15
Prove that any group of order $4$ is abelian.

Hint 1

Consider the cases (1) if there exists an element of order 4, (2) if there does not exist an element of order 4.

Hint 2

In case (1), we can conclude that the group is generated by a single element. In case (2), then for any $x$ , $x^2=e$ , where $e$ is the identity.

Hint 3

In case (2), then for any $x$ and $y$ , $(xy)^2=e$ , where $e$ is the identity.

Problem 16
Let $G$ and $G'$ be groups and let $f:G \rightarrow G'$ be a group homomorphism.

Show that if $H\leq G$ and $H'\leq G'$ , then $f(H):=\{f(h)\mid h \in H\}\leq G'$ and $f^{-1}(H'):=\{g \in G \mid f(g) \in H'\}\leq G$ .
Show that $\ker(f)\leq G$ and $\text{im}(f)\leq G'$ .

Problem 17
Compute the greatest common divisor of polynomials $\overline{2}X^5+\overline{3}X^4+X^2+\overline{4}$ and $X^4+\overline{2}X^3+X+\overline{3}$ in the polynomial ring $F[X]$ with $F=\mathbb{Z}/5\mathbb{Z}$ , where the `bar’ means taking the class in $\mathbb{Z}/5\mathbb{Z}$ (e.g., $\overline{2}=2+5\mathbb{Z}$ ).

Problem 18
Construct a field of order 25.

Problem 19
Determine all irreducible polynomials over $\mathbb{Z}/3\mathbb{Z}$ of degrees 2,3, and 4.

Problem 20
HW8

Malachi Alexander

UCSC Graduate Student

Final Exam Study Guide