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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License