NUMBER THEORY AND CRYPTOGRAPHY 2023: ASSIGNMENT 5
DUE: 6PM FRIDAY THE 27TH OCTOBER 2023
You may use a calculator or an Excel spreadsheet for numerical computations, but your
answer must explain the method of the computations you have made.
(1) (10 marks) Find all rational numbers pq such that |pq − 1712 | < 1q2 .
(2) (10 marks) Let α be a real number represented by the following infinite continued
fraction
α = [1; 1, 2, 3, 5, 8, 13, 21, 34, . . .]
where the pattern is defined by the recurrence relation an+2 = an+1+ an for all n ≥ 0.
Use this continued fraction expansion to find the best rational approximation to α with
a denominator less than or equal to 120029.
(3) (24 marks)
(a) Let α = [3; 4] := [3; 4, 3, 4, 3, 4, . . .]. Find α.
Hint: α is a root of some quadratic equation.
(b) Let a and b be some positive integers, and let α = [a; b] := [a; b, a, b, a, b, . . .]. Show
that α is a root of a quadratic equation px2 + qx + r = 0 with integer p, q, r to
be found. Prove that the second root of this equation is always negative.
(c) Prove that the second root of the equation from part (b) is equal − 1
[b;a]
.
Hint. The denominator [b; a] is a root of a similar quadratic equation.
(4) (10 marks) Find continued fraction expansions for
√
55 and
√
57.
(5) (10 marks) The decimal 6.12921348 was computed by rounding to 8 decimal places
the decimal expansion of a rational number pq with a denominator less than 200. Use
continued fractions to work out the original rational pq .
(6) (10 marks) Find all positive integer solutions to x2 − 57y2 = 1 that are less than 1010
(to clarify this means that both x and y must be < 1010).
(7) (16 marks) Which of the following are quadratic residues modulo 1069: 345, 571, 834,
and 1111?
Hint: use the theorems given in the lectures to compute their respective Legendre
symbols modulo 1069.
(8) (10 marks) Suppose that p is an odd prime, determine a condition on p that is both
necessary and sufficient to ensure that 19 is a quadratic residue modulo p.
Hint: use quadratic reciprocity to compute the Legendre symbol
(
19
p
)