Selected Answers to Problem Set 12

1. For two unknowns we need two equations. For these we will use:

n = pq
ø(n) = ø(p) * ø(q)
We know that p, q are prime numbers, so the number of integers less than p,q that do not divide them must be (p-1),(q-1). Thus:
ø(p) = (p - 1)
ø(q) = (q - 1)
ø(n) = (p - 1)(q - 1)
With these two equations, solving becomes much easier.
ø(n) = pq - p - q + 1
ø(n) = n - p - q + 1
n - ø(n) + 1 = p + q
q = n - ø(n) + 1 - p

pq = n
p(n - ø(n) + 1 - p) = n

This is our equation for p. We can now solve for p. p(39247771 - 39233944 + 1 - p) = 39247771
p(13828 - p) = 39247771
p^2 - 13828p + 39247771 = 0
p = {3989, 9839}