MAT 311
Number Theory

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ⁿ.
• Use mathematical induction to show that 1²-2²+ 3²- ... + (-1)^n-1n² = (-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 f₁+f₃+f₅+ ... +f_2n-1.
• 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³+1 other than 2 (=1³+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 n-th 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 prime-power factorization of n! is [n/p]+[n/p²]+[n/p³]+... , 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³⁶-1. Do not use a calculator and do not compute the decimal representation of 2³⁶-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 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(p-3)! when divided by p is -1.
• What is the remainder of 5¹⁰⁰ 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¹⁰⁰⁰.
• Find the last digit of the base 7 expansion of 3¹⁰⁰.
• Show that 42 | (n⁷-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.
  1. Find the six smallest abundant postive integers.
  2. Show that a multiple of an abundant or a perfect number (other than the perfect number itself) is abundant.
  3. Show that if n= 2^m-1(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.
  1. Is Λ(n) a multiplicative function ?
  2. 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 numbers.
  1. Show that λ(n) is a multiplicative function.
  2. ^* Show that the Dirichlet (or convolution) inverse of λ(n) is the characteristic function of the squarefree numbers (that is it is the function μ², where &mu denotes the Moebius function).
• Find a closed form expression for the following sums:
  1. ∑_d|n μ(d)/d
  2. ∑_d|n μ(d)φ(d)
  3. ∑_d|n μ²(d)/φ(d)
  4. ^* ∑_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 x₀=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₀ be a good choice for a sequence of pseudorandom numbers? Explain!
• Use the Pollard ρ-method with x₀=2 and x_n+1= x_n²+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²ⁿ+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)=(x-1)(x-2)...(x-p+1)-x^p-1+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 < p-1, then p-a² is a primitive root modulo p.
• Use index arithmetic to find all the solutions of the congruences
  1. 3x⁵ ≅ 1 (mod 23)
  2. 3x¹⁴ ≅ 2 (mod 23)
  3. 3^x ≅ 2 (mod 23)
• For which positive integers a is the congruence ax⁴ ≅ 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².
• 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²²ⁿ ≅ 1 (mod F_n) and x^2(2n-1)≠ 1 (mod F_n), then the Fermat number F_n=2²ⁿ+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²+x+1 ≅ 0 (mod 7).
• Does the congruence x²-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:
  • 8k+3
  • 8k+5
  • 8k+7
• 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₃=257 and F₄=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⁸⁶⁴ (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² + 5b² then p ≅ 1 or 9 (mod 20).
• HW 12 (due 05/04 in class, for extra credit)
• ^* Find the solutions of x² ≅ 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, 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 x⁴ ≅ 2070 (mod 3149). Find the least nonnegative residue of x² 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.