Math 404/504 homework

Homework 14, due Friday 29 April

  1. Silverman, exercise 48.4(a). Let $x$ be the continued fraction $[a,\overline{b,c}]$. Find a formula for $x$.
  2. 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

Homework 13, due Friday 22 April

  1. 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.
  2. (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.
  3. Silverman, exercise 32.1. Show that if $D$ is a perfect square, then $x^2-Dy^2=1$ has no nontrivial solutions.
  4. 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

Homework 12, due Friday 15 April

  1. (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$.
  2. Find all primitive $(p-1)$th roots for the primes: $p=23,29,31$.
  3. 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.
  4. Silverman, exercise 29.7(c). (Or in other words, complete page 3 of the ElGamal activity.)

Supplemental problems

Homework 11, due Friday 8 April

  1. 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$.]
  2. Use the descent procedure from class to write $p=1553$ as a sum of two squares.
  3. 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}$.
  4. Use the method from class to solve $x^2\equiv 7\pmod{197}$. [Note: $p\equiv5\pmod{8}$.]

Supplemental problems

Homework 9, due Friday 18 March

  1. (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.]
  2. 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}$.]
  3. Silverman, exercise 21.1.
  4. Calculate the Legendre symbols using factoring and quadratic reciprocity: $(\frac{85}{101})$, $(\frac{29}{541})$, $(\frac{101}{1987})$

Supplemental problems

Homework 8, due Friday 11 March

  1. Silverman, exercise 18.4 (see math.brown.edu/johsilve/frint.html#exercise18.4)
  2. 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?
  3. Silverman, exercise 19.3
  4. Silverman, exercise 19.7

Supplemental problems

Homework 7, due Friday 4 March

  1. 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.
  2. 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.
  3. 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?
  4. 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

Homework 6, due Thursday 24 February

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

Supplemental problems

Homework 4, due Thursday 10 February

  1. (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}$
  2. (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}$.
  3. Silverman, exercise 10.3(a)
  4. Silverman, exercises 11.5 and 11.6

Supplemental problems

Homework 3, due Thursday 3 February

  1. 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)$.
  2. 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.)
  3. 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.)
  4. Silverman, exercise 8.4

Supplemental problems

Homework 2, due Thursday 27 January

  1. 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.
  2. Silverman, exercise 3.2
  3. 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.)
  4. 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

Homework 1, due Thursday 20 January

  1. 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.
  2. 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.
  3. Show that if $(a,b,c)$ is a primitive Pythagorean triple, then exactly one of $a,b$ is odd.
  4. Show how to generate a primitive Pythagorean triple from two odd numbers $s,t$. Verify that it is a Pythagorean triple.
  5. Silverman, exercise 1.6.

Supplemental problems