Math453: Homework 11

Homework 11

This assignment is due by the beginning of class on Wednesday, May 6^th. 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.)