Homework:
Problems marked with an asterisk (*) are for extra credit.

HW 1 (due 02/02 in class) [solutions]

Davenport p.215/216: Ex 1.01, 1.02, 1.03

Use mathematical induction to show that n<2^{n}.

Use mathematical induction to show that 1^{2}2^{2}+
3^{2} ... + (1)^{n1}n^{2} = (1)^{n1}n(n+1)/2, for all positive n.

Find and prove a simple formula for the sum of the first n
Fibonacci numbers with odd indices when n is a positive integer.
That is find a simple formula for f_{1}+f_{3}+f_{5}+
... +f_{2n1}.

HW 2 (due 02/08 in class) [solutions]

Davenport p.215/216: Ex 1.04, 1.05, 1.11, 1.12

Find a simple function of x that approximates the counting function
sq(x) := number of square numbers less than x. Use this
estimate to explain why the statement "most numbers are not perfect square"
makes sense.

Show that there are no prime triplets, that is primes p, p+2, p+4, other than 3,5, and 7.
 Show that every integer greater than 11 is the sum of two composite integers.
 Show that there are no primes of the form N^{3}+1 other than 2 (=1^{3}+1)
 Find the smallest five consecutive composite integers.

HW 3 (due 02/15 in class) [solutions]
 Davenport p.217 Ex 1.20, 1.23^{*}, 1.24, 2.01
 Find the greatest common divisor of 34709 and 100313 and express
it as a linear combination of these integers.
 Find the greatest common divisor of 15, 35 and 90 and express
it as a linear combination of these integers.
 ^{*} If f_{n} denotes the nth Fibonacci
number show that (f_{n}, f_{m}) = f_{(n,m)}.
 Let n be a positive integer and let p be a prime.
Show that the power of p appearing in the primepower
factorization of n! is
[n/p]+[n/p^{2}]+[n/p^{3}]+... ,
where [..] denotes the integral part of a number.
 How many zeroes are at the end of 1000! in decimal notation?
 Find the prime factorization of 2^{36}1. Do not use a
calculator and do not compute the decimal representation of 2^{36}1...
 A shopper spends a total of $5.49 for oranges which cost 18c each
and grapefruit which cost 33c each. What is the minimum number of
fruit that the shopper could have bought?
 Which combinations of pennies, dimes and quarters have a total
value of 99c?
 NoFrills Airlines offers three types of tickets on the route
BostonNYC. Business class tickets are $140, economy tickets are $110
and standby tickets are $78. If 69 passengers pay a total of $6548 for
their tickets on a particular flight, how many of each type of ticket
were sold?

HW 4 (due 02/23 in class) [solutions]
 Davenport p.217 Ex 2.03, 2.04
 Using the Chinese remainder theorem, explain (only) how to add and how
to multiply 784 and 813 on a computer with word size 100.

HW 5 (due 03/02 in class) [solutions]
 Davenport p.218 Ex 2.05, 2.07, 2.12
 ^{*} Show that if p is an odd prime then the remainder of
2(p3)! when divided by p is 1.
 What is the remainder of 5^{100} when divided by 7?
 What is the remainder of 18! when divided by 437?
 Use Euler's theorem to find the last digit of the decimal
expansion of 7^{1000}.
 Find the last digit of the base 7 expansion of 3^{100}.
 Show that 42  (n^{7}n) for all positive integers
n.
 Show that φ(n)φ(m)=φ((n,m))φ([n,m]).
 ^{*}Find the smallest positive integer n with
τ(n)=3. Find also the smallest positive integer n with
τ(n)=13*31.
 ^{*}Which positive integers have exactly four positive divisors?

HW 6 (due 03/09 in class) [solutions]
 Davenport p.219 Ex 2.21, 2.22.
 Show that τ(n) is odd if and only if n is a
perfect square. Also show that σ(n) is odd if and only if n is a
perfect square or twice a perfect square.
 A number n is called "abundant" if
σ(n)>2n.
 Find the six smallest abundant postive integers.
 Show that a multiple of an abundant or a perfect number (other
than the perfect number itself) is abundant.
 Show that if n=
2^{m1}(2^{m}1), where
m is a postive integer and 2^{m}1 is composite
(i.e. not a prime), then n is abundant.
 Let Λ(n) be the Von Magoldt function:
Λ(n)=0 if n is not a prime power, and
Λ(p^{m})=log p for any prime power
p^{m}.
 Is Λ(n) a multiplicative function ?
 Show that
∑_{dn} Λ(d) = log n
for all natural numbers n >0.
 Let λ(n) be the Liouville function:
λ(1)=1 and λ(n)=(1)^{r} if
n is a product of r (not necessarily distinct) prime
numbers.
 Show that λ(n) is a multiplicative function.
 ^{*} Show that the Dirichlet (or convolution) inverse of
λ(n) is the characteristic function of the squarefree
numbers (that is it is the function μ^{2}, where &mu
denotes the Moebius function).
 Find a closed form expression for the following sums:
 ∑_{dn} μ(d)/d
 ∑_{dn} μ(d)φ(d)
 ∑_{dn} μ^{2}(d)/φ(d)
 ^{*} ∑_{dn} μ(n/d) log d

HW 7 (due 03/16 in class) [solutions]
 Davenport p.225 Ex 8.06 and 8.07.
 Find the period length of the sequence of pseudorandom numbers
generated by the linear congruential method with
x_{0}=0 and
x_{n+1}≅ 4x_{n}+7 (mod 25).
 Would the numbers generated by the linear congruential method
x_{n+1}≅ x_{n}+c (mod n)
for given (fixed) n, c and x_{0} be a
good choice for a sequence of pseudorandom numbers? Explain!
 Use the Pollard ρmethod with x_{0}=2 and
x_{n+1}= x_{n}^{2}+1 to factor
the number 133.
 ^{*} Explain why the choice of a linear function
x_{n+1}= ax_{n}+b
to generate the x_{n} is a poor choice for Pollard ρmethod.
 Show that every composite Fermat number
F_{n}=2^{2n}+1 is a pseudoprime to
the base 2.
 Show that 1387 is a pseudoprime, but not a strong pseudoprime, to
the base 2. Is 1387 a Carmichael number?
 Show that 1373653 is a strong pseudoprime to both bases 2 and 3.

HW 8 (due 03/30 in class) [solutions]
 Davenport p.219 Ex. 3.04, 3.05, 3.11, 3.12, 3.13^{*}
 Let p be a prime number. Use Lagrange's theorem to show
that each coefficient of the polynomial
f(x)=(x1)(x2)...(xp+1)x^{p1}+1
is divisible by p. Use this fact to give another proof to Wilson's theorem.
 ^{*}Show that if q is an odd prime and
p=2q+1 is also a prime number, and if a is a positive
integer with 1 < a < p1, then pa^{2} is a
primitive root modulo p.
 Use index arithmetic to find all the solutions of the congruences
 3x^{5} ≅ 1 (mod 23)
 3x^{14} ≅ 2 (mod 23)
 3^{x} ≅ 2 (mod 23)
 For which positive integers a is the congruence
ax^{4} ≅ 2 (mod 13) solvable?

HW 9 (due 04/06 in class) [solutions]
 Davenport p.219 Ex. 3.14, 3.15, 3.18, 3.19
 Find a primitive root modulo 17^{2}.
 Show that 101 is a prime number using Lucas' converse of Fermat's
little theorem with x=2.
 Show that if an integer x exists such that
x^{22n} ≅ 1 (mod
F_{n})
and x^{2(2n1)}≠ 1 (mod
F_{n}), then the Fermat number
F_{n}=2^{2n}+1
is prime.
 ^{*} Let n be a positive integer possessing a
primitive root of unity. Using this primitive root prove that the
product of all positive integers less than n and relatively
prime to n is congruent to 1 modulo n. (When n
is a prime number this is just Wilson's theorem.)
 Find the minimal universal exponent of 884, that is λ(884).
 Find all positive integers n for which λ(n)=2.

HW 10 (due 04/20 in class)
 Davenport p.220 Ex. 3.21, 3.22, 3.23, 3.25, 3.26
 Find all solutions of the quadratic congruence
x^{2}+x+1 ≅ 0 (mod 7).
 Does the congruence x^{2}3x1 ≅ 0
(mod 31957) have any solutions?
 ^{*} Show that if p is an odd prime with p > 5
then there are always two consecutive quadratic residues mod p.
 ^{*} Show that there are infinitely many primes of each
of the following types:
 Evaluate each of the following Legendre symbols: (111/991),
(7/79), (31/641)
 Verify if the following assertion is true: If p is
congruent to 1 modulo 5, then 5 is a quadratic reside mod p

HW 11 (due 04/27 in class) [solutions]
 Davenport p.220 Ex. 3.16, 3.17
 Use Pepin's test to check that the Fermat numbers F_{3}=257 and
F_{4}=65537 are primes.
 ^{*} Use Pepin's test to conclude that 3 is a primitive
root of every Fermat prime.
 Find a congruence describing all primes for which 5 is a
quadratic residue.
 The integer p=1+8*3*5*7*11*13*17*19*23=829371481 is a
prime (e.g this can be checked with the help of Maple or Pari). Show
that all primes q with q < 24 are quadratic residues
mod p. Conclude that there is no quadratic nonresidue of
p less than 29 and that p has no primitive root less
than 29.
 Evaluate the following Jacobi symbol: (1009/2307).
 For which positive integers n that are relatively prime to
15 does the Jacobi symbol (15/n) equal 1?
 Use succesive squaring to compute 11^{864} (mod 1729) and
use quadratic reciprocity to compute (11/1729). What can you conclude
concerning the possible primality of 1729?
 Show that if a prime number p > 5 can be written in the form
p = a^{2} + 5b^{2} then p ≅ 1 or 9
(mod 20).

HW 12 (due 05/04 in class, for extra credit)
 ^{*} Find the solutions of x^{2} ≅ 482 (mod 2773)
 ^{*} Let p be an odd prime, and let C ≅
P^{e} (mod p) be a cyphertext obtained
by modular exponentiation from the plaintext P,
with exponent e and modulus p, where
0< C < p and (e, p1)=1. Show that
C is a quadratic residue mod p if and only if
P is a quadratic residue mod p.
 ^{*} Let n=3149=47*67 and suppose that
x^{4} ≅ 2070 (mod 3149). Find the least
nonnegative residue of x^{2} mod 3149.
 ^{*} Run through the steps used to verify that a user
has the secret information consisting of the factorization of
24617=103*239. (This is a toy example, since in reality primes with
hundreds of digits would be used instead.)
 ^{*} Davenport p.225 Ex 8.11 and 8.12.