Homework 11

This assignment is due by the beginning of class on Wednesday, May 6th. Be sure to review the homework guidelines before getting started.

• Find all solution to $44x^2+57x+3 \equiv 0 \mod{5000}$.
• Can 4385745 be expressed as a sum of 2 squares? If so, give such an expression. If not, explain why.
• Can 123760 be expressed as a sum of 3 squares? If so, give such an expression. If not, explain why.
• Use the method of descent to prove that there are no integer solutions to the equation $a^2+b^2 = 3(c^2+d^2)$.
• Suppose you know that $m = pq$ for primes p and q. Express $p+q$ in terms of $m$ and $\phi(m)$. Express $p-q$ in terms of $m$ and $\phi(m)$. Use these results to solve for p and q when $m = 18950167$ and $\phi(m) = 18939856$.
• Why is it important to keep $\phi(m)$ secret for RSA to be effective?
• Encrypt KEEP IT A SECRET using blocks of size 4 and the public key $(13, 50233)$.
• Define $q_3(n)$ as the number of partitions of n where no summand is allowed to be a multiple of 3. What is $q_3(10)$? What is the generating function for $q_3(n)$?
• Use the Euler Product formula for the Riemann Zeta function to prove there are infinitely many primes. (Hint: what happens when $s=1$?)
• Use a product formula to express $\sum_{n=1}^\infty \frac{\sigma(n)}{n^s}$ in terms of the Riemann Zeta function. (Hint: try multiplying together the Euler products for $\zeta(s)$ and $\zeta(s-1)$, where $\zeta(s)$ is the "usual" Riemann Zeta function.)

More problems will likely be added in the next several days, so check back on this page for updates. The homework is now complete.