# Math 404/504 homework

## Homework 14, due Friday 29 April

- Silverman, exercise 48.4(a). Let $x$ be the continued fraction $[a,\overline{b,c}]$. Find a formula for $x$.
- Consider the Pell equation $x^2-41y^2=1$. (a) Find the periodic continued fraction for $\sqrt{41}$. (b) State the period $k$ of the continued fraction for $\sqrt{41}$. (c) Find the first $k$ convergents for the continued fraction for $\sqrt{41}$. (d) Plug the $k-1$st convergent into $x^2-41y^2$ to get $\pm1$ on the right-hand side. (e) If you got $-1$ on the right-hand side, use the method of squaring to find a solution to $x^2-41y^2=1$.

### Supplemental problems

- SP42 Silverman, exercise 48.1
- SP43 Silverman, exercise 48.2

## Homework 13, due Friday 22 April

- Silverman, exercise 31.4. Explore the first five pentagonal numbers. Find a formula for the pentagonal numbers and use it to find the 10th and 100th pentagonal numbers.
- (Similar to Silverman, exercise 32.4.) We have studied square triangles, so now study square pentagons. Set $n^2=$ your formula for the $m$th pentagonal number. Use substitution to reduce the problem to solving a Pell equation (it helped me to multiply both sides by 24). Then use computational methods to find three solutions to the Pell equation, and finally, three square pentagonal numbers.
- Silverman, exercise 32.1. Show that if $D$ is a perfect square, then $x^2-Dy^2=1$ has no nontrivial solutions.
- Consider the Pell equation $x^2-21y^2=1$. Suppose you know that $(110,24)$ and $(12098,2640)$ are solutions to $x^2-21y^2=4$. Use the quotient method from 4(c) of the Pell equation activity to find a solution to $x^2-21y^2=1$.

### Supplemental problems

- SP39 Study triangular pentagonal numbers and find some examples. What Pell-like equation may be solved in order to find them?
- SP40 Complete the proof that the quotient method works from 4(c) of the Pell equation activity.
- SP41 Silverman, exercise 34.1(a)(b).

## Homework 12, due Friday 15 April

- (Similar to Silverman, exercise 28.7.) (a) Suppose $p$ is an odd prime and $a$ is a square modulo $p$. Show that $a$ cannot be a primitive root modulo $p$. (b) More generally suppose $n\mid p-1$ and $a$ is an $n$th power modulo $p$. Show that $a$ cannot be a primitive root modulo $p$.
- Find all primitive $(p-1)$th roots for the primes: $p=23,29,31$.
- Silverman, exercise 29.3(a)(b). If $ab\equiv1\pmod{p}$, then how are $\mathrm{Ind}(a)$ and $\mathrm{Ind}(b)$ related? If $a+b\equiv0\pmod{p}$, how are $\mathrm{Ind}(a)$ and $\mathrm{Ind}(b)$ related? For each question, collect some data, make a conjecture, and then prove that your conjecture is true.
- Silverman, exercise 29.7(c). (Or in other words, complete page 3 of the ElGamal activity.)

### Supplemental problems

- SP35 Silverman, exercise 28.1
- SP36 Silverman, exercise 28.8(a)(c)
- SP37 Silverman, exercise 29.1
- SP38 Silverman, exercise 29.6

## Homework 11, due Friday 8 April

- Silverman, exercise 24.2. Show that if $p$ is a prime and $p\neq5$ and $p=a^2+5b^2$ then $p\equiv1$ or $p\equiv9\pmod{20}$. [Hint: Consider the possibilities for $p$ modulo $4$ and modulo $5$.]
- Use the descent procedure from class to write $p=1553$ as a sum of two squares.
- Suppose $p\equiv5\pmod{8}$ and $p-1=4s$. Show that $x=a^{(s+1)/2}$ is a solution to $x^2\equiv\pm a\pmod{p}$. Show that $z=2^s$ is a solution to $z^2\equiv-1\pmod{p}$.
- Use the method from class to solve $x^2\equiv 7\pmod{197}$. [Note: $p\equiv5\pmod{8}$.]

### Supplemental problems

- SP31 Silverman, exercise 24.6
- SP32 Use the descent procedure from class to write $p=54133$ as a sum of two squares.
- SP33 (Similar to Silverman, exercise 25.4.) Show that if $p,q\equiv3\pmod{4}$ then $pq$ is not a sum of two squares. [Hints: If $pq=a^2+b^2$, reduce modulo $p$ to get $a^2+b^2\equiv0\pmod{p}$. Show this implies that either $a,b\equiv0\pmod{p}$ or else $-1$ is a square modulo $p$. Then get a contradiction.]
- SP34 Use the method from class to solve $x^2\equiv11\pmod{353}$. [Note: $p\equiv1\pmod{8}$ so you have to use the full procedure.]

## Homework 9, due Friday 18 March

- (Similar to Silverman, exercise 20.3.) Make a list of the cubes modulo $p=17$. Show that if $p\equiv2\pmod{3}$, then every number is a cubic residue modulo $p$. [Hint: Show that in this case it is possible to find an exponent that performs cube roots.]
- Prove that $(\frac{-1}{p})=1$ if $p\equiv1\pmod{4}$ and that $(\frac{-1}{p})=-1$ if $p\equiv3\pmod{4}$. [You may use Euler’s Criterion which states that $(\frac{a}{p})\equiv a^{(p-1)/2}\pmod{p}$.]
- Silverman, exercise 21.1.
- Calculate the Legendre symbols using factoring and quadratic reciprocity: $(\frac{85}{101})$, $(\frac{29}{541})$, $(\frac{101}{1987})$

### Supplemental problems

- SP27 Silverman, exercise 22.2
- SP28 Silverman, exercise 22.3
- SP29 Silverman, exercise 22.4
- SP30 Calculate the Legendre symbols using Jacobi reciprocity (no factoring except $2$ and $-1$): $(\frac{85}{101})$, $(\frac{29}{541})$, $(\frac{101}{1987})$

## Homework 8, due Friday 11 March

- Silverman, exercise 18.4 (see math.brown.edu/johsilve/frint.html#exercise18.4)
- How long does it take to find $\phi(n)$? Use
`from sympy import totient`

and time the`totient()`

function on at least 30 different integers with 5-50+ digits. Make a table of number of digits and the run time. What does your data suggest about how many digits you should use to be secure? - Silverman, exercise 19.3
- Silverman, exercise 19.7

### Supplemental problems

- SP23 Silverman, exercise 18.5
- SP24 Silverman, exercise 19.2
- SP25 SIlverman, exercise 19.4
- SP26 SIlverman, exercise 19.5

## Homework 7, due Friday 4 March

- Use
`powermod`

and`binaryexpand`

(or similar calculator methods) to calculate the powers: $28^{749}\pmod{1147}$, and $208^{1\,010\,101}\pmod{101}$. Show your work with enough calculator output to understand your process. - Use
`euler`

,`inverse`

, and`pow`

(or similar calculator methods) to solve the roots: $x^{113}\equiv347\pmod{463}$, and $x^{275}\equiv139\pmod{588}$. Show your work with enough calculator output to understand your process. - Let $n=13$. Find an exponent $k$ such that $x^k\pmod{13}$ has exactly one solution. Find an example of an exponent $k$ such that $x^k\pmod{13}$ has more than one solution. How many solutions are there? Find a second example of an exponent $k$ such that $x^k\pmod{11}$ has more than one solution. How many are there?
- Let $n=pq$ be a product of distinct primes, and let $\lambda(n)=\mathrm{lcm}(p-1,q-1)$. Show that if $\gcd(a,n)=1$, then $a^{\lambda(n)}\equiv 1\pmod{n}$.

### Supplemental problems

- SP20 Silverman, exercise 17.3(a)
- SP21 Silverman, exercise 17.3(c) - give many examples supporting your conjecture.
- SP22 Show that if $\gcd(a,10)=1$, then $a^{2001}$ and $a$ have the same last three digits.

## Homework 6, due Thursday 24 February

- Silverman, exercise 12.2
- Prove that if $t=2^p-1$ and $t$ is prime, then $t(t+1)/2$ is a perfect number.
- Silverman, exercise 15.1. Prove that the divisor sum function $\sigma(n)$ satisfies $\sigma(mn)=\sigma(m)\sigma(n)$ when $\gcd(m,n)=1$.
- Silverman, exercise 15.5

### Supplemental problems

- SP16 Silverman, exercise 12.3
- SP17 Silverman, exercise 13.6
- SP18 Silverman, exercise 14.1
- SP19 Silverman, exercise 15.3

## Homework 4, due Thursday 10 February

- (Similar to Silverman, exercise 9.1.) Use Fermat’s little theorm to help find a solution to each equation.
- $x^{74}\equiv5\pmod{37}$
- $x^{83}\equiv16\pmod{41}$
- $x^{55}\equiv27\pmod{53}$

- (Similar to Silverman, exercise 9.2.)
- Find the value of $(p-2)!\pmod{p}$ for the first five odd primes $p$.
- Show that if $p$ is prime, then the numbers $2\leq a\leq p-2$ can be sorted into pairs that are inverses of one another (in other words, $a^{-1}\neq a$).
- Conclude that $(p-2)!\equiv1\pmod{p}$.

- Silverman, exercise 10.3(a)
- Silverman, exercises 11.5 and 11.6

### Supplemental problems

- SP12 Show that for any $n$, you can find $n$ consecutive composite numbers.
- SP13 Silverman, exercise 10.1
- SP14 Silverman, exercise 11.10
- SP15 Silverman, exercise 11.11

## Homework 3, due Thursday 3 February

- Show that if $(x_0,y_0)$ is a solution to $ax+by=d$, then so is $(x_0+kb/d,y_0-ka/d)$.
- Let $a,b,c$ be three numbers with $\gcd(a,b,c)=1$. Explain how to use the extended Euclidean algorithm to solve the equation $ax+by+cz=1$. Apply your method to solve $155x+341y+385z=1$, and to solve $1234x+3456y+6789z=1$. (You may use calculators/computers, but please show me your process.)
- Solve each of the congruences using the extended Euclidean algorithm. $4x\equiv17\pmod{21}$, $63x-350\equiv500\pmod{730}$, $1234x\equiv5000\pmod{12345}$. (You may use calculators/computers, but please show me your process.)
- Silverman, exercise 8.4

### Supplemental problems

- SP8 Prove that if $s,t$ are odd numbers with no common factors, then the Pythagorean triple $(\frac{s^2-t^2}{2},st,\frac{s^2+t^2}{2})$ is primitive.
- SP9 Silverman, exercise 7.5.
- SP10 Modify the function “gcd2” to always returns a pair $x,y$ with $x>0$. Then use it to write a new function “reciprocal” which takes as input two numbers $a,n$ with $\gcd(a,n)=1$ and returns the value of $a^{-1}$ in $\mathbb Z_n$.
- SP11 Silverman, exercise 8.10

## Homework 2, due Thursday 27 January

- Show that if $u,v$ have no common factors, aren’t both even, and aren’t both odd, then the triple $(u^2-v^2,2uv,u^2+v^2)$ will have no common factors.
- Silverman, exercise 3.2
- Show that if $r_i,r_{i+1},r_{i+2}$ are successive remainders in a run of the Euclidean algorithm, then $r_{i+2}\lt\frac12r_i$. (See Silverman, exercise 5.3.)
- Let $F_n$ denote the Fibonacci sequence. Show that in a run of the Euclidean algorithm on $F_{n+1},F_n$, the quotient $q$ will be $1$ every time. Show that the algorithm terminates in $n-1$ steps.

### Supplemental problems

- SP5 Silverman, exercise 3.5(a)-(d)
- SP6 Find the $\gcd$ of any pair of Fibonacci numbers $F_n$ and $F_m$ in terms of $n$ and $m$, and prove you are correct.
- SP7 Silverman, exercise 5.4

## Homework 1, due Thursday 20 January

- Show how to generate a square triangle number from a pair $p,q$ such that $p^2$ and $2q^2$ are one unit apart. Verify your resulting quantity $n$ is a square triangle.
- Show how, given $p,q$ as above, to generate a new pair $p’,q’$ with the same property. Verify your $p’,q’$ satisfy that $(p’)^2$ and $2(q’)^2$ are one unit apart.
- Show that if $(a,b,c)$ is a primitive Pythagorean triple, then exactly one of $a,b$ is odd.
- Show how to generate a primitive Pythagorean triple from two odd numbers $s,t$. Verify that it is a Pythagorean triple.
- Silverman, exercise 1.6.

### Supplemental problems

- SP1 Silverman, exercise 1.3
- SP2 Silverman, exercise 2.1
- SP3 Silverman, exercise 2.6
- SP4 Silverman, exercise 2.7