- 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=p^{2}+a, hence p^{2}-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 x^{2}-cx+d=0 are r and s, then x^{2}-cx+d = (x-r)(x-s) = x^{2}-(r+s)x+rs, so c=r+s and d=rs. From the identity we get (r-s)^{2}= (r+s)^{2}-4rs = c^{2}-4d, so r-s = sqrt(c^{2}-4d), so r = ((r-s) + (r+s))/2 = (c + sqrt(c^{2}-4d))/2 and s = ((r+s) - (r-s))/2 = (c - sqrt(c^{2}-4d))/2.

- Consider the cubic equation x
^{3}-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)-(u^{3}+v^{3}) = 0. If you can find u and v such that uv = a and u^{3}+v^{3}= b, then x=u+v is a solution to the cubic.- Show that from the two equations
uv = a u

you can obtain a single equation (u^{3}+v^{3}= b^{3})^{2}+c(u^{3})+d=0. What values do you get for the coefficients c and d?
Answer: v=a/u so u - Solve (u
^{3})^{2}+c(u^{3})+d=0 for u^{3}, 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 x^{3}-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 (u

^{3}+(a/u)^{3}= b, hence u^{6}+a^{3}= bu^{3}, or (u^{3})^{2}-b(u^{3})+a^{3}=0. Thus c = -b = -6 and d = a^{3}= 8.^{3})^{2}-6(u^{3})+8=0 are u^{3}= 2 and u^{3}= 4, so u is either 2^{1/3}(in which case v = a/u = 2/2^{1/3}= 2^{2/3}= 4^{1/3}), or u is 4^{1/3}(in which case v = a/u = 2/4^{1/3}= 2/2^{2/3}= 2^{1/3}). Either way, x = u+v = 2^{1/3}+ 4^{1/3}. Plugging this on my calculator into x^{3}-6x-6 gives -5.6810^{-11}, which is pretty close to 0. - Show that from the two equations
- Cardano's solution for x
^{3}-3ax-b=0 using the identity (u+v)^{3}-3uv(u+v)-(u^{3}+v^{3}) = 0 can be used to solve*any*cubic. Consider the cubic x^{3}+cx^{2}+dx+e=0. If you substitute x=y-c/3 in for x and simplify, you get an equation of the form y^{3}+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 y^{3}+fy+g=0, then from x = y - c/3 we get that x = n - c/3 is a solution to the original equation, x^{3}+cx^{2}+dx+e=0.- In the case of
x
^{3}+3x^{2}-3x-11=0, what should you substitute in for x, as described above, to eliminate the x^{2}term?
Answer: Substitute x = y - 3/3 = y - 1.
- After making your substitution, you should have a polynomial
in y with no y
^{2}term. What is your polynomial? [Hint: It should look familiar!]
Answer: We get x - Give a solution to x
^{3}+3x^{2}-3x-11=0.
Answer: If we substitute y-1 in for x, from x

^{3}+3x^{2}-3x-11 = (y - 1)^{3}+ 3(y - 1)^{2}- 3(y - 1) - 11 = (y^{3}- 3y^{2}+ 3y - 1) + 3(y^{2}- 2y + 1) - 3(y - 1) - 11, which simplifies to y^{3}- 6y - 6.^{3}+3x^{2}-3x-11=0 we get y^{3}- 6y - 6 = 0, which from the previous problem has the solution y = 2^{1/3}+ 4^{1/3}. Thus x = (2^{1/3}+ 4^{1/3}) - 1 is a solution for x^{3}+3x^{2}-3x-11=0. - In the case of
x
- 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

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...)