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<2n.
Use mathematical induction to show that 12-22+
32- ... + (-1)n-1n2 = (-1)n-1n(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 f1+f3+f5+
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"
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 N3+1 other than 2 (=13+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 fn denotes the n-th Fibonacci
number show that (fn, fm) = f(n,m).
- Let n be a positive integer and let p be a prime.
Show that the power of p appearing in the prime-power
factorization of n! is
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 236-1. Do not use a
calculator and do not compute the decimal representation of 236-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
Boston-NYC. 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
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(p-3)! when divided by p is -1.
- What is the remainder of 5100 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 71000.
- Find the last digit of the base 7 expansion of 3100.
- Show that 42 | (n7-n) for all positive integers
- 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
- *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
- 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=
m is a postive integer and 2m-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
Λ(pm)=log p for any prime power
- Is Λ(n) a multiplicative function ?
- Show that
∑d|n Λ(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
- 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:
- ∑d|n μ(d)/d
- ∑d|n μ(d)φ(d)
- ∑d|n μ2(d)/φ(d)
- * ∑d|n μ(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
xn+1≅ 4xn+7 (mod 25).
- Would the numbers generated by the linear congruential method
xn+1≅ xn+c (mod n)
for given (fixed) n, c and x0 be a
good choice for a sequence of pseudorandom numbers? Explain!
- Use the Pollard ρ-method with x0=2 and
xn+1= xn2+1 to factor
the number 133.
- * Explain why the choice of a linear function
to generate the xn is a poor choice for Pollard ρ-method.
- Show that every composite Fermat number
Fn=22n+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
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 < p-1, then p-a2 is a
primitive root modulo p.
- Use index arithmetic to find all the solutions of the congruences
- 3x5 ≅ 1 (mod 23)
- 3x14 ≅ 2 (mod 23)
- 3x ≅ 2 (mod 23)
- For which positive integers a is the congruence
ax4 ≅ 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 172.
- 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
x22n ≅ 1 (mod
and x2(2n-1)≠ 1 (mod
Fn), then the Fermat number
- * 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
x2+x+1 ≅ 0 (mod 7).
- Does the congruence x2-3x-1 ≅ 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),
- 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 F3=257 and
F4=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
- 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
- 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 11864 (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 = a2 + 5b2 then p ≅ 1 or 9
HW 12 (due 05/04 in class, for extra credit)
- * Find the solutions of x2 ≅ 482 (mod 2773)
- * Let p be an odd prime, and let C ≅
Pe (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, p-1)=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
x4 ≅ 2070 (mod 3149). Find the least
nonnegative residue of x2 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.