Review Exercises (Set C)

  1. Find all $x$ that satisfy both $x \equiv 8 \pmod{23}$ and $x \equiv 15 \pmod{17}$  

    The first congruence gives us $x = 23k + 8$ for some integer $k$.

    Substituting this into the second congruence, we have $23k + 8 \equiv 15\pmod{17}$, or more simply $23k \equiv 7\pmod{17}$.

    Finding $23^{-1} \equiv 3\pmod{17}$ either by inspection or the Euclidean Algorithm, we solve for $k$ to discover $k \equiv 3 \cdot 7 \equiv 4\pmod{17}$

    So $k = 17m + 4$ for some integer $m$. Substituting this back into the earlier expression given for $x$, we have $$\begin{array}{rcl} x &=& 23(17m + 4) + 8\\ &=& 391m + 100 \end{array}$$

    Thus, $x \equiv 100\pmod{391}$

  2. Consider the function $f: \mathbb{Z} \rightarrow 2\mathbb{Z}$ (that is to say, a function whose inputs are the integers $\mathbb{Z}$, and outputs are in the even integers $2\mathbb{Z}$) defined by $f(x) = 2x^2 - 4$. Is $f(x)$ injective? Is it surjective? Justify your claims.  

    Remember, a function is injective only if no two different inputs produce the same output. In this case, $f(x)$ is not injective as we can find two different values in $\mathbb{Z}$ (the domain) that produce the same output (e.g., $f(-1) = -2 = f(1)$).

    On the other hand a function $f : A \rightarrow B$ is surjective only if every element of $B$ (which is called the "co-domain") actually is an output of $f$. Here,$f(x)$ is not surjective as we can find elements of $2\mathbb{Z}$ (i.e., the even integers) that fail to be output values of $f(x)$. For example, there are no integers $x$ with $f(x) = 0$, $f(x)=2$, $f(x)=6$, etc...

  3. Find or describe a bijection (i.e., a pairing) between the points in the open interval $(0,1)$ and the points in $(-\infty,\infty)$.  

    There are many possibilities here.

    One involves pairing points in $(0,1)$ first with points on a semi-circle, and then points on a line tangent to that semi-circle as suggested by the following image:

    A second (even simpler) pairing is given by the function $f(x) = \tan(\pi x - \pi/2)$.

  4. Prove that the cardinality of the power set of a given set is never equal to the cardinality of the set itself.  


    (For a metaphorical context for the below argument, consult the notes on the cardinality of the power set.)

    We argue indirectly.

    Suppose we assume that the cardinality of a set $S$ and its power set $P(S)$ are equal.

    As such, there must exist some function $f: S \rightarrow P(S)$ which is a bijection.

    Let us define the following subsets of $S$:

    $$C = \{x \in S \;|\; x \in f(x) \}$$ $$H = \{x \in S \;|\; x \not\in f(x) \}$$

    Note, $H$ is a subset of $S$, so it must be an element of the power set $P(S)$.

    Since $f$ is a bijection, there must exist some $a \in S$ such that $f(a) = H$

    Clearly, any element of $S$ must be in either $H$ or $C$, but never both. With this in mind, consider the implications for the aforementioned element $a$...

    If $a \in H$, then $a \not\in f(a)$. As $f(a)=H$, this implies $a \not\in H$. Contradiction.

    If $a \in C$, then $a \in f(a)$. As $f(a) = H$, this implies $a \in H$, which requires $a \not\in C$. Contradiction.

    So $a$ is not an element of $H$ or $C$.

    However, we argued just moments before that every element of $S$ (which includes $a$) must be in one of these two sets.

    This gives us the contradiction needed to reject our original assumption that the cardinality of a set $S$ and its power set $P(S)$ are equal.

    It must then be the case that the cardinality of a set $S$ and its power set $P(S)$ are not equal.

    QED.

  5. Express $\sqrt{17}$ in continued fraction form.  

    First, we separate the integer part and fractional part of $\sqrt{17}$. Since $4^2 \lt 17 \lt 5^2$, it must be the case that $4 \lt \sqrt{17} \lt 5$. Consequently, the integer part of $\sqrt{17}$ is 4, and the fractional part is what is left (i.e., $\sqrt{17}-4$).

    $$\sqrt{17} = 4 + (\sqrt{17} - 4)$$

    Now, to have $\sqrt{17}$ written as a continued fraction, we need the fractional part to be expressed as one over something. Reciprocating things twice produces the desired numerator of one, without changing the overall value:

    $$\sqrt{17} = 4 + \frac{1}{\displaystyle{\frac{1}{\sqrt{17}-4}}}$$ Now, we wish to repeat the process - and write $1/(\sqrt{17}-4)$ as an integer plus some fractional part. However, it is harder to see clearly what the integer part will be. Consequently, we multiply by the conjugate to get rid of the square root in the denominator: $$\sqrt{17} = 4 + \frac{1}{\displaystyle{\frac{1}{\sqrt{17}-4} \cdot \frac{\sqrt{17} + 4}{\sqrt{17}+4}}}$$ This simplifies to $$\begin{array}{rcl} \sqrt{17} &=& 4 + \frac{\displaystyle{1}}{\displaystyle{\frac{\sqrt{17}+4}{1}}}\\\\ &=& 4 + \frac{\displaystyle{1}}{\displaystyle{\sqrt{17}+4}} \end{array}$$ Now, identifying the integer part of the denominator is more easily done. Recalling again that we know $4 \lt \sqrt{17} \lt 5$, the integer part of of $\sqrt{17}$ must be 4, which makes $8$ the integer part of $\sqrt{17}+4$. Noting that $\sqrt{17} + 4 = 8 + (\sqrt{17} - 4)$ means that $(\sqrt{17} - 4)$ must be the fractional part of the denominator. So we have: $$\sqrt{17} = 4 + \frac{\displaystyle{1}}{\displaystyle{8 + (\sqrt{17} - 4)}}$$ Seeing the duplication of $(\sqrt{17}-4)$, we immediately know that further double reciprocations would continue to produce integer parts in the denominators of $8$. Consequently, the continued fraction form we seek is $$\sqrt{17} = 4 + \frac{\displaystyle{1}}{8 + \frac{\displaystyle{1}}{\displaystyle{8} + \frac{\displaystyle{1}}{\displaystyle{8} + \cdots}}}$$ Of course, we can write this more simply, using the conventional way to write continued fractions with repeated values: $$\sqrt{17} = [4;\overline{8}]$$

  6. $[4;\overline{1,3,1,8}]$ is the square root of what value?  

    It will simplify things to focus just on the fractional part of the value in question. Let us denote this by $y= [0;\overline{1,3,1,8}]$.

    The repeated part of the continued fraction above means that we can write $y$ in terms of itself, as shown below:

    $$y = \frac{\displaystyle{1}}{\displaystyle{1+\frac{\displaystyle{1}}{\displaystyle{3+\frac{\displaystyle{1}}{\displaystyle{1 + \frac{\displaystyle{1}}{\displaystyle{8+y}}}}}}}}$$ The fraction on the right, however, can be greatly simplified in the normal way: $$\begin{array}{rcccl} y &=& \frac{\displaystyle{1}}{\displaystyle{1+ \frac{\displaystyle{1}}{\displaystyle{3 + \frac{\displaystyle{1}}{\frac{\displaystyle{9+y}}{\displaystyle{8+y}}}}}}} &=& \frac{\displaystyle{1}}{\displaystyle{1+ \frac{\displaystyle{1}}{\displaystyle{3 + \frac{\displaystyle{8+y}}{\displaystyle{9+y}}}}}}\\\\ &=& \frac{\displaystyle{1}}{\displaystyle{1 + \frac{\displaystyle{1}}{\frac{\displaystyle{4y+35}}{\displaystyle{9+y}}}}} &=& \frac{\displaystyle{1}}{\displaystyle{1}+\frac{\displaystyle{9+y}}{\displaystyle{4y+35}}}\\\\ &=& \frac{\displaystyle{1}}{\frac{\displaystyle{5y+44}}{\displaystyle{4y+35}}} &=& \frac{\displaystyle{4y+35}}{\displaystyle{5y+44}} \end{array}$$

    So then, we know $$y = \frac{4y+35}{5y+44}$$ However, multiplying both sides by $5y+44$ yields a quadratic equation. (This always happens!) $$5y^2+44y = 4y+35$$ which simplifies to $$y^2+8y-7 = 0$$ Using the quadratic formula (and noting that $y \gt 0$) we can solve for $y$: $$y = -4 + \sqrt{23}$$ Finally, adding back in the integer part (i.e., $4$) of the original continued fraction given, we have $$[4;\overline{1,3,1,8}] = 4 + y = \sqrt{23}$$

  7. Suppose a message is RSA-encrypted with modulus $N=323$ and encrypting key $e=49$. Find the decrypting key $d$.  

    Recall that the relationship between the encrypting key $e$, the decrypting key $d$, and the modulus $N$ is given by

    $$ed \equiv 1 \pmod{\phi(N)}$$

    Noting that $\phi(323) = \phi(17 \cdot 19) = \phi(17) \cdot \phi(19) = 16 \cdot 18 = 288$, it remains to solve

    $$49d \equiv 1 \pmod{288}$$

    We can find $d$ from the above in the usual way.

    First we use the Euclidean algorithm to ensure that $49$ and $288$ are indeed relatively prime [so that we know $d = 49^{-1}\pmod{288}$ exists.]

    288 = 5 * 49 + 43
    49 = 1 * 43 + 6
    43 = 7 * 6 + 1    <-- note: the remainder tells us gcd(49,288) = 1, 
                          so the multiplicative inverse of 49 (mod 288) exists
    

    Then, we "back-solve" the calculations above to find a linear combination of 49 and 288 that produces 1. This will reveal the value of $49^{-1}\pmod{288}$:

    1 = 1 * 43 - 7 * 6
    1 = 1 * 43 - 7 * (49 - 1 * 43)
    1 = -7 * 49 + 8 * 43
    1 = -7 * 49 + 8 * (288 - 5 * 49)
    1 = 8 * 288 - 47 * 49
    
    Note the multiplier on $49$ of $(-47)$. This is the value of $49^{-1}\pmod{288}$. Of course, adding the modulus of $288$ won't change its value$\pmod{288}$, but does make it positive (which is always nice). So we have $$d \equiv -47 + 288 \equiv 241 \pmod{288}$$

  8. Find an integer $x$ that satisfies the congruence $x^{169} \equiv 119 \pmod{1452}$  

    Note, we can calculate $\phi(1452)$ from its prime factorization:

    $$\begin{array}{rcl} \phi(1452) &=& \phi(2^2 \cdot 3 \cdot 11^2)\\ &=& \phi(2^2) \cdot \phi(3) \cdot \phi(11^2)\\ &=& (2^2 - 2)(3-1)(11^2 - 11)\\ &=& 2 \cdot 2 \cdot 110\\ &=& 440 \end{array}$$

    With this value in hand, we check if $gcd(1452,119) = gcd(\phi(1452),169) = 1$, using the Euclidean Algorithm.

    1452 = 12 * 119 + 24
    119 = 4 * 24 + 23
    24 = 1 * 23 + 1     <-- so gcd(1452,119) = 1
    
    440 = 2 * 169 + 102
    169 = 1 * 102 + 67
    102 = 1 * 67 + 35
    67 = 1 * 35 + 32
    35 = 1 * 32 + 3
    32 = 10 * 3 + 2
    3 = 1 * 2 + 1       <-- so gcd(440,169) = 1
    

    Finding this to be true, we can use the method of finding $k^{th}$ roots inspired by RSA...

    Suppose that $x = 119^u$ is a solution.

    Substituting, we then have

    $$119^{169u} \equiv 119 \pmod{1452}$$

    Since $\gcd(119,1452) = 1$, we are free to divide both sides by $119$ to obtain

    $$119^{169u-1} \equiv 1 \pmod{1452}$$

    Recall, we know by Euler's Theorem that

    $$119^{\phi(1452)} \equiv 1 \pmod{1452}$$

    Consequently, we know that for any positive integer $c$,

    $$119^{440c} \equiv 1 \pmod{1452}$$

    So we search for a $u$ and $c$ such that

    $$169u-1 = 440c$$

    Equivalently, we solve

    $$169u \equiv 1 \pmod{440}$$

    Solving such congruences should be routine by now -- so we omit the details -- but this leads to

    $$u \equiv 289 \pmod{440}$$

    So $x \equiv 119^{289} \pmod{1452}$ should solve the congruence with which we started. To find this large power, we appeal to the process of successive squaring...

    Breaking the exponent into a sum of powers of two, we find $289 = 256 + 32 + 1$, so we compute $123^n \pmod{1452}$ for all $n$ that are powers of $2$ less than or equal to $256$.

    $$\begin{array}{rcl} 119^{1} &\equiv& \fbox{119} \\ 119^{2} &\equiv& 1093\\ 119^{4} &\equiv& 1105\\ 119^{8} &\equiv& 1345\\ 119^{16} &\equiv& 1285\\ 119^{32} &\equiv& \fbox{301}\\ 119^{64} &\equiv& 577\\ 119^{128} &\equiv& 421\\ 119^{256} &\equiv& \fbox{97} \end{array}$$

    Finally, multiplying the boxed values together, we arrive at the solution we seek

    $$x \equiv 119 \cdot 301 \cdot 97 \equiv 1259 \pmod{1452}$$

  9. Find all solutions to $x^2 \equiv 607\pmod{713}$, noting that $713 = 23 \cdot 31$  

    We note that $x^2 \equiv 607 \equiv 9\pmod{23}$ and $x^2 \equiv 607 \equiv 18\pmod{31}$. In each case, we note the modulus is a prime congruent to $3$ modulo $4$.

    Consequently, we check if $x \equiv \pm 9^{(23+1)/4} \equiv \pm 3 \pmod{23}$ and $x \equiv \pm 18^{(31+1)/4} \equiv \pm7 \pmod{31}$ are the respective solutions to these last two congruences - which they are.

    (Note, we could have reduced these powers with successive squaring as in the previous problem, but $9^{6} = 531441 \equiv 3\pmod{23}$ and $18^{8} = (18^4)^2 = 104976^2 \equiv 10^2 \equiv 7\pmod{31}$ is faster.)

    So one of the following four cases must hold for any $x$ that solves $x^2 = 607\pmod{713}$: $$\begin{array}{c} x \equiv 3\pmod{23}\\ x \equiv 7\pmod{31}\\\\ x \equiv -3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ x \equiv 3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ x \equiv -3\pmod{23}\\ x \equiv 7\pmod{31}\\\\ \end{array}$$

    Let's deal with the first case first -- that is to say, let us solve for the $x$ that satisfies $x \equiv 3\pmod{23}$ and $x \equiv 7\pmod{31}$ by applying the algorithm associated with Chinese Remainder Theorem:

    $x \equiv 3\pmod{23}$ tells us that for some integer $k$, we have $x = 23k+3$.

    Substituting this for $x$ in the second congruence, we have $$23k+3 \equiv 7\pmod{31}$$ Solving for $k$ we subtract 3 from both sides to obtain $$23k \equiv 4\pmod{31}$$ We might solve this by inspection, but it will actually prove advantageous to go ahead and find the multiplicative inverse of $23\pmod{31}$ instead. Doing so, of course involves the Euclidean Algorithm:

    31 = 1 * 23 + 8
    23 = 2 * 8 + 7
    8 = 1 * 7 + 1    <-- so gcd(31,23) = 1 i
                         (as expected, since these are both primes)
    
    1 = 1 * 8 - 1 * 7
    1 = 1 * 8 - 1 * (23 - 2 * 8)
    1 = -1 * 23 + 3 * 8
    1 = -1 * 23 + 3 * (31 - 1 * 23)
    1 = 3 * 31 - 4 * 23   <-- so the multiplicative inverse of 23 is (-4)
    

    Knowing $23^{-1} \equiv -4\pmod{31}$, we multiply both sides of our congruence by this value to find $k$ (and adding the modulus 31 to keep things positive, which doesn't violate the congruence). $$\begin{array}{rcl} (-4) \cdot 23k \equiv (-4) \cdot 4\pmod{31}\\ k \equiv -16\pmod{31}\\ k \equiv 15\pmod{31} \end{array}$$ Written another way, we have $k = 31k_2 + 15$ for some integer $k_2$.

    Recalling that $x = 23k+3$ and replacing this $k$ with $(31k_2 + 15)$, we have $$x = 23(31k_2 + 15) + 3 = 713k_2 + 348$$

    Thus, we have $x \equiv 348\pmod{713}$.

    Of course, now the second case where $$\begin{array}{c} x \equiv -3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ \end{array}$$ is now immediately solved with $x \equiv -348\pmod{713}$.

    So now, we proceed to the third case where $$\begin{array}{c} x \equiv 3\pmod{23}\\ x \equiv -7\pmod{31}\\\\ \end{array}$$ Following the same algorithm, the first note that the top congruence tells us $x = 23k+3$ for some integer $k$.

    Substituting this into the bottom congruence gives $$23k+3 \equiv -7\pmod{31}$$ Subtracting $3$ from both sides yields $$23k \equiv -10\pmod{31}$$ We previously found $23^{-1}\pmod{31} = -4$, so we multiply both sides by this multiplicative inverse to find $k$: $$(-4)\cdot 23k \equiv (-4)(-10)\pmod{31}$$ Which tells us $$k \equiv 40 \equiv 9\pmod{31}$$ Equivalently, $k = 31k_2 + 9$ for some integer $k_2$. Substituting this into $x = 23k+3$ from earlier above, we have $$x = 23(31k_2 + 9)+3$$ Simplifying, we have $$x = 713k_2 + 210$$ and consequently, our third case is solved by $$x \equiv 210\pmod{713}$$ Just as the first case solution led immediately to the second case's solution -- so too does this solution to the third case lead immediately to the solution of the fourth case (i.e., $x \equiv -3\pmod{23}$ and $x \equiv 7\pmod{31}$): $$x \equiv -210\pmod{713}$$

    Putting all of this together, we have $$x \equiv \pm 348, \pm 210\pmod{713}$$

  10. Find $\text{ord}_{19} 8$.  

    We simply compute positive integer powers of $8\pmod{19}$ and look for the least positive exponent that results in a power that is congruent to $1\pmod{19}$.

    $$\begin{array}{rcl} 8^1 &\equiv& 8 \pmod{19}\\ 8^2 &\equiv& 7 \pmod{19}\\ 8^3 &\equiv& 18 \pmod{19}\\ 8^4 &\equiv& 11 \pmod{19}\\ 8^5 &\equiv& 12 \pmod{19}\\ 8^6 &\equiv& 1 \pmod{19} \end{array}$$

    Since $6$ is the first such exponent that works, $\text{ord}_{19} 8 = 6$.

  11. Suppose $\text{ord}_n b = 3$. How many positive integer solutions does $b^x \equiv 1 \pmod{n}$ have for $x$ that are less than $26$?  

    Recall that $b^x \equiv 1 \pmod{n}$ if and only if $\textrm{ord}_n b \mid x$.

    As there are only $8$ positive integers between $1$ and $26$ that $3$ divides evenly (i.e., $3$, $6$, $9$, $12$, $15$, $18$, $21$, and $24$), there must be exactly $8$ solutions for $x$.

  12. Alice and Bob agree to create a secret encryption key for future correspondence according to the Diffie-Hellman Key Exchange Protocol. Over a public communications channel, they agree upon a prime base of $5$ and a modulus of $23$. Alice then sends Bob the value $8$, and Bob sends Alice the value $19$. What is their agreed upon secret encryption key? What could they have done to better protect the secret key they generated?  


    Recall, Alice has secretly chosen an exponent $a$ and sent Bob $5^a$, while Bob has secretly chosen an exponent $b$ and sent Alice $5^b$. Each can then take the other's sent number and raise it to their own secret exponent to obtain $5^{ab}$, the secret agreed-upon key.

    However, Alice and Bob did not choose a modulus near large enough to prevent an eavesdropper like us from solving for $a$ and $b$.

    We know that $5^a \equiv 8 \pmod{23}$ and $5^b \equiv 19 \pmod{23}$.

    We can construct the following table of powers of 5, given that the modulus of 23 is small:

    $$\begin{array}{rclcrcl|rclrcl}
    5^1 &\equiv& 5 && 5^{12} &\equiv& 18\\ 5^2 &\equiv& 2 && 5^{13} &\equiv& 21\\ 5^3 &\equiv& 10 && 5^{14} &\equiv& 13\\ 5^4 &\equiv& 4 && 5^{15} &\equiv& 19\\ 5^5 &\equiv& 20 && 5^{16} &\equiv& 3\\ 5^6 &\equiv& 8 && 5^{17} &\equiv& 15\\ 5^7 &\equiv& 17 && 5^{18} &\equiv& 6\\ 5^8 &\equiv& 16 && 5^{19} &\equiv& 7\\ 5^9 &\equiv& 11 && 5^{20} &\equiv& 12\\ 5^{10} &\equiv& 9 && 5^{21} &\equiv& 14\\ 5^{11} &\equiv& 22 && 5^{22} &\equiv& 1\\ \end{array}$$

    Consulting the table given suggests that $a = 6$ and $b = 15$.

    It remains to calculate the value of the secret key...

    $$5^{ab} = 5^{6 \cdot 15} = 5^{90} = (5^{22})^4 \cdot 5^2 \equiv 5^2 \equiv 2 \pmod{23}$$