 # 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<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+ ... +f2n-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 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 [n/p]+[n/p2]+[n/p3]+... , 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 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 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 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= 2m-1(2m-1), where 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 pm.
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 μ2, 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 μ2(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 x0=0 and xn+1≅ 4xn+7 (mod 25).
• Would the numbers generated by the linear congruential method xn+1xn+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 xn+1= axn+b 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 f(x)=(x-1)(x-2)...(x-p+1)-xp-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-a2 is a primitive root modulo p.
• Use index arithmetic to find all the solutions of the congruences
1. 3x5 ≅ 1 (mod 23)
2. 3x14 ≅ 2 (mod 23)
3. 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 Fn) and x2(2n-1)≠ 1 (mod Fn), then the Fermat number Fn=22n+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 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:
• 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 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 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 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 (mod 20).
• 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.