Math 310: Problem set 10
Instructions: This problem set is due
Tuesday, November 28, 2006.
Your goal is not only
to give correct answers but to communicate
your ideas well. Make sure you use good English.
- The number 708714834137 is the product pq of two primes p and q,
with phi(pq)=(p-1)(q-1)=708713126820.
- Given pq and (p-1)(q-1), show how to find p+q, and determine
p+q if pq and (p-1)(q-1) are as given above.
Answer: Since pq-(p-1)(q-1)+1=p+q, we see p+q = 708714834137 - 708713126820 + 1 = 1707318.
- Given pq and p+q, show how to find p and q, and thereby find a factorization of 708714834137.
Answer: Since (p-q)2 = (p+q)2-4pq =
1707318^2 - 4*708714834137 = 80075416576, taking the square root
we have p-q = 282976, hence p = ((p+q)+(p-q))/2 = 995147 and q = ((p+q)-(p-q))/2 = 712171.
Thus 708714834137 factors as 995147*712171. [Alternatively, if pq=a and p+q=b,
then q=a/p so b=p+a/p or bp=p2+a, hence p2-bp+a=0, which can be solved
using the quadratic formula.]
Note: The identity (p-q)2 = (p+q)2-4pq allows you to solve any quadratic equation.
If the solutions of x2-cx+d=0 are r and s, then x2-cx+d =
(x-r)(x-s) = x2-(r+s)x+rs, so c=r+s and d=rs.
From the identity we get (r-s)2 = (r+s)2-4rs = c2-4d,
so r-s = sqrt(c2-4d), so r = ((r-s) + (r+s))/2 = (c + sqrt(c2-4d))/2
and s = ((r+s) - (r-s))/2 = (c - sqrt(c2-4d))/2.
- Consider the cubic equation x3-3ax-b=0 in the case that
a=2 and b=6. Cardano's solution is to use the identity
(u+v)3-3uv(u+v)-(u3+v3) = 0.
If you can find u and v such that uv = a and
u3+v3 = b, then x=u+v is a solution to the cubic.
- Show that from the two equations
uv = a
u3+v3 = b
you can obtain a single equation
(u3)2+c(u3)+d=0. What values
do you get for the coefficients c and d?
Answer: v=a/u so u3+(a/u)3 = b, hence
u6+a3 = bu3, or
(u3)2-b(u3)+a3=0.
Thus c = -b = -6 and d = a3 = 8.
- Solve (u3)2+c(u3)+d=0
for u3, then get u by taking cube roots, and get
v from uv = a. What solution x=u+v does this give you?
Verify your solution by plugging it into x3-6x-6.
What value do you get? (Due to round-off error, it shouldn't be zero,
but it should be close.)
Answer: The solutions to (u3)2-6(u3)+8=0
are u3 = 2 and u3 = 4, so u is either
21/3 (in which case v = a/u = 2/21/3 = 22/3 = 41/3),
or u is 41/3 (in which case v = a/u = 2/41/3 = 2/22/3 = 21/3).
Either way, x = u+v = 21/3 + 41/3. Plugging this on my calculator into
x3-6x-6 gives -5.6810-11, which is pretty close to 0.
- Cardano's solution for x3-3ax-b=0 using the identity
(u+v)3-3uv(u+v)-(u3+v3) = 0 can be used to
solve any cubic. Consider the cubic
x3+cx2+dx+e=0. If you substitute
x=y-c/3 in for x and simplify, you get an equation of the form
y3+fy+g=0 in which the squared term has been eliminated,
and which you can thus solve using Cardano's method. If y = n
is a solution to y3+fy+g=0, then from x = y - c/3 we get
that x = n - c/3 is a solution to the original equation,
x3+cx2+dx+e=0.
- In the case of
x3+3x2-3x-11=0, what should you substitute in for x,
as described above, to eliminate the x2 term?
Answer: Substitute x = y - 3/3 = y - 1.
- After making your substitution, you should have a polynomial
in y with no y2 term. What is your polynomial?
[Hint: It should look familiar!]
Answer: We get x3+3x2-3x-11 =
(y - 1)3 + 3(y - 1)2 - 3(y - 1) - 11
= (y3 - 3y2 + 3y - 1) + 3(y2 - 2y + 1) - 3(y - 1) - 11,
which simplifies to y3 - 6y - 6.
- Give a solution to x3+3x2-3x-11=0.
Answer: If we substitute y-1 in for x, from x3+3x2-3x-11=0
we get y3 - 6y - 6 = 0, which from the previous problem has the solution
y = 21/3 + 41/3. Thus x = (21/3 + 41/3) - 1 is a
solution for x3+3x2-3x-11=0.
- Here is a message encrypted using the RSA method with
a modulus of m = 10 and an encryption exponent of e = 3.
Find the decryption exponent d (explain and show how you find it),
and decipher the message:
020116168500800201141019030988091403.
(Hint: Letters were converted into strings of digits by
converting A to 01, B to 02, etc.
However, I'm not telling you the block size.
What is the biggest possible block size if m = 10?
What block size must have been used?)
Answer: Since m=10 and blocks must give distinct elements of Z/mZ,
we can't take blocks giving numbers bigger than 9. Thus the block size must be 1.
Since phi(10) = phi(2)phi(5) = 1*4 = 4, and since de == 1 (mod phi(m)),
we find that d = 3. Thus the string decrypts as follows:
ciphertext 020116168500800201141019030988091403
plaintext 080116162500200801141019070922091407, giving numeral encoded letters
08 01 16 16 25 00 20 08 01 14 10 19 07 09 22 09 14 07 or
H A P P Y T H A N J S G I V I N G
(The J instead of a K is a typo on my part...)