20171004

Please Login to access more options.

Today

Problem 26 (Powers With Modular Arithmetic)

1. We know that $481\mod {483} =(-2)\mod {483}$. Use this fact to quickly compute $481^2\mod{483}$ without a calculator. [How can you use the $-2$ to simplify this?]
2. Using the same idea, what is $481^{3}\mod{483}$ and $481^4\mod{483}$? You should be giving a positive integer less than 483 for all your answers.
3. Explain why $12\cdot 16 \mod 17$ is the same as $(-5)(-1)\mod 17$.
4. Now compute $14^k \pmod {17}$ without a calculator for as many values of $k$ as needed until you find a repeating pattern. See the hint below.

Let me give you a suggestion. Rather than trying to compute $14^4$, instead first compute $14^2$ by considering $(-3)^2$. To compute $(14)^3$, instead use the product $(14)^2(14)=(9)(-3)=(-8)(-3)$. Use your work from the previous power to figure out the next power. If you try to do this with brute force, it gets outrageously large really fast. If you swap from positive to negative values when the numbers get large (above 8), you should be able to do this without ever needing long division. You should find that no product ever gets above 24.

The following Sage code will compute powers with modular arithmetic. You are welcome to check your answers with this, but the whole point to the problem is to learn how to simplify the computations by hand. To compute $a^m\mod n$ you would write "power_mod($a$,$m$,$n$)."

power_mod(481, 4, 483)

Problem 27 (Matrix Encryption Mod 5)

In the Problem (Simple Matrix Encryption), we took a plain text message written in columns of a matrix $M$ and a matrix $A$ and used the product $AM$ to encode a message. Let's now combine matrix encryption with modular arithmetic to obtain a new encryption scheme. Once we have done this, we'll be one step closer to understanding modern encryption techniques. To simplify our work, let's use a small alphabet consisting of 5 letters. Instead of using the set $S=\{a,b,c,d,e\}$, let's just use numbers for our letters and we'll consider the alphabet $S=\{0,1,2,3,4\}=\mathbb{Z}_5$. Given the plain text "bad bed" or "10 31 43", we can encode it in the columns of the matrix $$M=\begin{bmatrix}1&3&4\\0&1&3\end{bmatrix}.$$ An 2 by 2 encryption key using coefficients mod 5 is a 2 by 2 matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ where $a,b,c,d\in \mathbb{Z}_5$. Here are the steps to our encryption scheme.

• First convert the plain text to a matrix $M$ where the letters are place in the matrix top to bottom, column by column.
• Take the encryption key $A$ and compute the product $AM$.
• Reduce all the entries in $AM$ mod 5. So the cipher text only consists of the numbers in $\mathbb{Z}_5$.

Answer the following questions.

1. Suppose we let $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$. Why is this matrix not suitable as an encryption key? (Hint: what is the determinant, and why is that a problem?)
2. Suppose we let $A=\begin{bmatrix}2&1\\4&3\end{bmatrix}$. The inverse of $A$ if we ignore modular arithmetic is $\frac{1}{2}\begin{bmatrix}3&-1\\-4&2\end{bmatrix}$. We know that we can replace $-4$ with $1$ when working modular 5. Similarly we can replace $-1$ with a positive number. We need to find the multiplicative inverse of 2 when working modular 5. Find a value $b\in \mathbb{Z}_5$ so that $2b\mod 5=1$. This number $b$ is the inverse of $2$ modular 5.
3. State a matrix $B$ with coefficients in $\mathbb{Z}_5$ so that $AB$ is the identity matrix after reducing each entry mod 5. Actually perform the product by hand, and show how this matrix product reduces to the identity.

Definition (Modular Multiplicative Inverse and $U(n)$)

Let $n$ be a positive integer, and let $a\in \mathbb{Z}_n$. Then the modular multiplicative inverse of $a \mod n$ is an integer $b\in \mathbb{Z}_n$ such that $(ab)\mod n=1$. If such an integer exists, then we'll write $a^{-1}\mod n$ to represent the modular multiplicative inverse. If the context is clear, we may just refer to this as the inverse instead of the modular multiplicative inverse. We'll use the notation $U(n)$ to represent the set of elements in $\mathbb{Z}$ that have a modular multiplicative inverse. Notationaly, we write $$U(n)=\{a\in\mathbb{Z}_n\mid \text{ there exists } b\in \mathbb{Z}_n \text{ such that } (ab)\mod n=1\}.$$

The Sage code "inverse_mod(a,n)" will compute the modular multiplicative inverse of $a\mod n$ or return an error.

inverse_mod(7, 11)

Problem 28 (Computing Multiplicative Inverses For Small N)

To use modular arithmetic in matrix encryption, we must be able to find the modular multiplicative inverse of $a \mod n$. For each $n\leq 13$ and $a\in \mathbb{Z}_n$, we now compute the inverse of $a\mod n$ or explain why it does not have one.

1. Why does $0\mod n$ never have an inverse?
2. What is the multiplicative inverse of $1\mod n$?
3. For $n=3$, what is the multiplicative inverse of $a=2$.
4. For $n=4$, show that 2 does not have an inverse by computing $2\cdot 0$, $2\cdot 1$, $2\cdot 2$, and $2\cdot 3$ all modulo $4$. What is $3^{-1}\mod 4$?
5. For each $n$ between 5 and 13, create a table that shows the inverse of each $a\in \mathbb{Z}_n$. List the elements of $\mathbb{Z}_n$ along the top row, and beneath each element list the multiplicative inverse, or cross off the number if there is no multiplicative inverse.

When you are done you should have a list of the elements of $U(n)$ for each $n$ up to 13, as well as the inverse of each element in $U(n)$. Do you see any patterns?

For $n=9$, you should obtain a table somewhat similar to the following table.

Definition (Cayley Graph Of A Span Of Permutations)

Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.

Problem 29 (Cayley Graph Patterns)

In each scenario below, you should draw a Cayley graph.

1. Let $X=\mathbb{Z}$, an infinite set. Consider the permutation $\phi_1:\mathbb{Z}\to \mathbb{Z}$ defined by $\phi_1(x)=x+1$. This permutation shifts elements in $\mathbb{Z}$ right one, with no wrap around. If we let $S=\{\phi_1\}$, give a rough sketch of the Cayley graph of $\text{span}(S)$. It's a rough sketch of the graph because there are infinitely many vertices.
2. How would you change your graph in part 1 if instead you used $S=\{\phi_2,\phi_3\}$, where these are shifts right 2 and 3 respectively?
3. Suppose that $X$ is a set, and that $S$ contains a single automorphism $s$ of $X$. Suppose also that we know $s^6$ is the identity (so following the arrow colored $c_s$ 6 times will return us to where we started). Construct a Cayley graph of $\text{span}(S)$. Is there more than one right answer to this?
4. Suppose that we know $S$ contains two elements $a$ and $b$. We also know that $a^2$ and $b^4$ are both the identity. In addition, we know that $a\circ b=b\circ a$, so if we start somewhere and follow the arrows colored $c_a$ and then $c_b$, then we should end up at the same place if we followed the arrows colored $c_b$ and then $c_a$. Construct a graph that satisfies these relationships. We'll often write this as $$\left<a,b\mid a^2=id, b^4=id, a\circ b=b\circ a\right>.$$

If $X$ is a set, and $S$ is a set of permutations of $X$, then we can create a Caley graph for the span of $S$. Here's a formal definition.

Definition (Cayley Graph Of A Span Of Permutations)

Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.

We've done this with several automorphism groups of graphs, as well as simple shift permutation groups.

Problem 30 (Cayley Graphs Of Two Automorphism Groups)

Consider the two graphs below. Let $L$ be the automorphism group of the graph on the left, and let $R$ be the automorphism group of the graph on the right.

We listed the automorphisms of the graph in Problem (Automorphisms On Several Graphs With 4 Vertices).

1. For the graph on the left, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in L$ so that $\text{span}(\{\alpha,\beta\})=L$. Then draw the Cayley graph of $L$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(L,\{\alpha,\beta\})$.
2. For the graph on the right, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in R$ so that $\text{span}(\{\alpha,\beta\})=R$. Then draw the Cayley graph of $R$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(R,\{\alpha,\beta\})$.

If $X$ is a set, and $S$ is a set of permutations of $X$, then we already know how to create the span of $S$. In general, the span of $S$ will include more permutations than what we started with. However, sometimes we won't be able to obtain any new permutations by spanning $S$. When this happens, we say that the set of permutations is closed (under function composition). Here's a formal definition.

Definition (A Closed Set Of Permutations)

We say that a set of permutations is closed if the set $S$ is equal to its span, so notionally we write $$S=\text{span}{(S)}.$$ In other words, we say that $S$ is closed if the set $S$ already contains every composition combination of permutations of elements in $S$.

The next problem has you prove some relationships between a set of permutations $S$ and its span.

Problem 32 (Relationship Between S And Its Span)

Let $S$ be a set of permutations of $X$.

1. Prove that $S\subseteq \text{span}(S)$. In other words, we know that $S$ is always contained in its span; the span might be larger.
2. Prove that if $\text{span}(S)\subseteq S$, then $S$ is closed.
3. If $T\subseteq S$, then show that $\text{span}(T)\subseteq\text{span}(S)$.

Definition (Integer Linear Combination Of Integers)

Let $a_1, a_2, \ldots, a_k$ be $k$ integers.

• An integer linear combination of these integers is an expression of the form $$c_1a_1+c_2 a_2+ \cdots+c_k a_k$$ where each coefficient $c_i$ is an integer.
• The span of the set of integers $\{a_1, a_2, \ldots, a_k\}$ is the set of all possible integer linear combinations of these integers, namely $$\text{span}(\{a_1, a_2, \ldots, a_k\})=\text{span}(a_1, a_2, \ldots, a_k)=\{c_1a_1+c_2 a_2+ \cdots+c_k a_k\mid c_i\in \mathbb{Z} \text{ for }1\leq i\leq k\}.$$ For ease of notation, we'll often leave off the set notation when spanning a set of integers.
• If the set $S$ of integers is infinite, then we still define the span of $S$ to be the set of all integer linear combinations of integers in $S$. Hence we know $x\in S$ if and only if there exists a natural number $k$ such that $x=c_1a_1+c_2 a_2+ \cdots+c_k a_k$ where $a_i\in S$ and $c_i\in \mathbb{Z}$ for $1\leq i\leq k$.
• When there are only two integers, we'll often use $a$ and $b$ as the integers, and $s$ and $t$ as the coefficients. So the set of all integer linear combinations of $a$ and $b$ is $$\text{span}(a,b) = \{sa+tb\mid s,t\in\mathbb{Z}\}.$$

Problem 33 (Integer Linear Combination Practice)

Complete the following.

1. Compute the span of $3$, i.e. make a list of the elements in this set. In general, what is the span of a single integer $a$? (We know it by a different name.)
2. What is $\text{span}(4,6)$? List the elements. Find a single number $a$ so that $\text{span}(a)=\text{span}(4,6)$.
3. What is $\text{span}(4,5)$?
4. Let $S=\{a_1,a_2,\ldots,a_k\}$ be a set of integers. Show that if $c\in \text{span}(S)$, then so is every multiple of $c$.

We've seen a lot of relationships in class about modular arithmetic, inverses mod n, simple shift encryption schemes, and more. The next problem makes a connection between some of these. We'll connect it to even more next time.

Problem 34 (When Does An Integer Have A Modular Multiplicative Inverse)

Let $a$ and $n$ be integers, with $n>1$. Show that the following are equivalent.

1. The integer $a$ has a multiplicative inverse mod $n$
2. We have $1\in \text{span}(a,n)$. In other words, we can write 1 as a linear combination of $a$ and $n$.
3. We have $\text{span}(a,n)=\mathbb{Z}$. Remember that $\text{span}(a,n) = \{sa+tn\mid s,t\in\mathbb{Z}\}.$

Remember, to show that three things are equivalent you must show that each implies the other. One way to do this is show that 1 implies 2, then show that 2 implies 3, and then show that 3 implies 1. Then each implies the other.

The two problems above, together with much of our work from the previous weeks, leads us to one of the biggest theorems in number theory. We'll prove this theorem later in the semester.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

Corollary (When Are Two Numbers Relatively Prime)

Two nonzero numbers $a$ and $b$ are relatively prime (i.e. their greatest common divisor is 1) if and only if there exists $s$ and $t$ such that $sa+tb=1$.

Problem 35 (Connecting Multiples And Spans Of Integers)

Suppose that $a$ and $b$ are integers.

1. Prove that if $a$ is a multiple of $b$, then we must have $\text{span}(a)\subseteq\text{span}(b)$.
2. Is the converse of the statement above true or false? Make sure you prove your result.

Problem 36 (Permutations of $U(n)$)

Suppose $n$ is an integer greater than 1 and let $X=U(n)$, so the set of integers mod $n$ that have a multiplicative inverse mod $n$. For each $a\in U(n)$, we can define a permutation of $U(n)$ by $f_a(x)=xa\pmod n$ for each $x\in U(n)$. This problem asks you to show that this is indeed a permutation of $U(n)$. This requires that you show the following:

1. For each integer $n\geq 2$, show that if $a\in U(n)$ and $x\in U(n)$, then the product $f_a(x)=xa\pmod n\in U(n)$. This shows that $f_a:U(n)\to U(n)$ is a map from $U(n)$ to $U(n)$.
2. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is one-to-one. (As a reminder, one-to-one means that if $f_a(x)=f_a(y)$, then $x=y$.)
3. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is onto. (As a reminder, onto means that if $y\in U(n)$, then there exists $x\in U(n)$ such that $f_a(x)=y$.)

Problem 37 (Three Similar Cayley Graphs From Different Contexts)

This problem asks you to draw 3 Cayley graphs. Each Cayley graph should only have 4 vertices.

1. Draw a Cayley graph for the set $H_4$ of simple shift permutations of $X=\{1,2,3,4\}$ using the generating set $S=\{\phi_1\}$.
2. Then draw a Cayley graph for the span of the permutation $(1,4,3,2)$, which we wrote in disjoint cycle notation.
3. Then draw a Cayley graph for $\{f_a\mid a\in U(5)\}$ using the generating set $S=\{f_2\}$. Remember that $f_a$ is a permutation of $U(5)$ defined by $f_a(x)=xa\pmod 5$.
4. What do you notice about these Cayley graphs?

The three graphs from the previous problem look very similar, so much so that we could obtain one from the other if we just relabeled the vertex sets. This suggests that in some sense these graphs are the same. We now introduce a formal way to talk about when two graphs are the same.

Definition (Isomorphic Graphs)

Let $G$ and $H$ be two graphs, where we use $V(G)$ and $V(H)$ to denote the vertex sets. A function $f:V(G)\to V(H)$ is called an isomorphism of graphs $G$ and $H$ if $f$ is a bijection and $\{x,y\}$ is an edge of $G$ if and only if $\{f(x),f(y)\}$ is an edge of $H$ (see Wikipedia).

• We call this function $f$ an isomorphism because it "preserves the edge structure" in the graph. In general the word isomorphism refers to a bijection that preserves some kind of structure.
• If there exists an isomorphism of graphs between $G$ and $H$, then we say that $G$ and $H$ are isomorphic.
• If $G$ and $H$ are directed graphs, then an isomorphism of directed graphs would preserve the arrow structure.
• If the directed graphs $G$ and $H$ are colored, then an isomorphism also preserves the color structure, in the sense that $(a,b)$ and $(c,d)$ share the same color if and only if $(f(a),f(b))$ and $(f(c),f(d))$ share the same color.

Problem 38 (Introduction To Cayley Graph Isomorphisms)

Let $H_6 = \{\phi_0,\phi_1,\ldots,\phi_5\}$ be the set of simple shift permutations on an alphabet with 6 letters. Let $K=\{f_a\mid a\in U(7)\}$ be the set of permutations $f_a:U(7)\to U(7)$ defined by $f_a(x)=xa\pmod 7$. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$.

1. Draw the Cayley graph of $H_6$ generated by $\{\phi_1\}$. Then draw the Cayley graph of $K$ generated by $\{f_3\}$. Finally show that the function $g:H_6\to K$ defined by $$ g(\phi_0)=f_1, g(\phi_1)=f_3, g(\phi_2)=f_2, g(\phi_3)=f_6, g(\phi_4)=f_4, g(\phi_5)=f_5, $$ is an isomorphism of Cayley graphs.
2. Draw the Cayley graph of $H_6$ generated by $\{\phi_2, \phi_3\}$. Then draw the Cayley graph of $K$ generated by $\{f_2,f_6\}$. Do you believe these two Cayley graphs are isomorphic? You can just give a heuristic argument, rather than a formal proof.
3. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$. We've already shown this set has 6 permutations. Draw a Cayley graph of $S_3$ generated by the permutations $(1,2,3)$ and $(1,2)$. Do you think that this Cayley graph is isomorphic to any of the Cayley graphs above? Why?

For more problems, see AllProblems