Problem 1. (Short answer; 5 pts each) Unless asked
otherwise, you are not required
to show detailed work for these questions, and need only give a brief
explanation.
(a) List all of the primitive elements modulo 13.
Solution. Since it can easily be shown that 2 is a
primitive root mod 13, and has order
13−1 = 12, the primitive roots are therefore 
which
are 2, 6, 7, 11
(b) Are there any solutions to the congruence
(mod 17)?
Solution. There are solutions if and only if
(mod 17).But
(mod 17),
so there are No solutions .
(c) How many solutions are there to the congruence
(mod 19)?
Solution. Since (8, 18) = 2, there are 2 solutions
.
(d) De termine whether 
(mod 79) is solvable .
Solution. Using generalized quadratic reciprocity , calculate
Thus 35 is a quadratic nonresidue modulo 79, and there are
No solutions .
(e) If n is odd, evaluate the Jacobi symbol
Solution. It’s easiest to begin by removing the square
factor (note that (n, n−2) = 1)
(f) If 
(mod 12),
calculate
Solution. Using quadratic reciprocity,
(g) Calculate the continued fraction expansion of 78/31
Solution.
Problem 2. (15 pts: 5+5+5) (a) Find the solutions
to 
(mod 7) and
determine whether they are singular or nonsingular.
Solution. Write 
Checking all values
of x gives the roots 1 and 3. Furthermore, 
(mod 7) and 
(mod 7). Thus the roots are x = 1; singular and x = 3; nonsingular .
(b) Given that 2 is a primitive root modulo 29 and that
(mod 29), find all
solutions to 
(mod 29).
Solution. The solutions all have the form
for 0≤k≤6. Specifically, they are
(in order of k ) 3, 19, 14, 21, 17, 11, 2 .
(c) Given that 22 is a primitive root modulo 25, find a
primitive root modulo 250.
Solution. Since 22 is primitive modulo 5^2, it is automatically a primitive root
modulo
5^3. Finally, a primitive root modulo 250 = 2 ยท (5^3) must be odd, which is
accomplished
by adding 125 to 22, giving 147 .
Problem 3. (20 pts: 5+10+5) Suppose that
(mod 4) is prime. (a) Show that
a is a quadratic residue modulo p if and only if p − a is a quadratic residue
modulo p.
Solution. Using Legendre symbols,
since (mod 4) and a is
known to be a quadratic residue.
(Bonus) (3 pts) Show that a is a quadratic residue modulo p if and only
if 
is.
Solution.
(b) Calculate the sum of all of the quadratic residues
modulo p (find the sum as an
integer – do not reduce it mod p!).
Solution. Since there are an equal number of quadratic
residues and nonresiduces, there
are exactly 
quadratic residues. Furthermore,
these occur in pairs a and p−a. There
are
such pairs, so the total sum is
(c) Calculate the sum of the quadratic nonresidues modulo
p
Solution. The total sum of residues and nonresidues is
Thus the sum of the quadratic residues is exactly half the total, and the
nonresidues
is the other half, and is also equal to
Problem 4. (15 pts: 7+8) (a) Calculate
Solution.
(b) Determine whether 
(mod 107) is solvable.
Solution. Multiply by 3 and then complete the square:
This has solutions if and only if
(mod 107). By part (a), the equation is solvable .
Problem 5. (15 pts: 10+5) Define the periodic
continued fractions 
(a) Evaluate 
Solution. From the book,
For the second, expand the continued fraction and solve.
Now the quadratic formula gives
(b) Prove the following inequalities:
Solution. Note that 
whereas
In
other words,
In particular, x < y, and thus the result from the
homework gives the claimed inequalities
(the result was that if d < c, then
when n is odd, with the opposite inequality for n even ).
(Bonus) (2 pts) Does
exist? If so, what is it?
Solution. Yes, the limit is the non-periodic continued
fraction [1, 2, 3, 4, . . . ] .
