| | |
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}$
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...
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)$.
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.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}]$$$[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}$$
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 * 49Note 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}$$
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}$$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$.
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$.
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}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}$$