Problems for Number Theory September 9, 1998

1. Prepare a table with 400 rows listing the following information for the positive integers 1 through 400:

(a) Prime factorization.

(b) Sum of divisors

(c) Express as sum of squares, minimize number of terms.

(d) Express as sum of primes, minimize number of terms.

(e) Number of primes less than n.

(f) Leave room for more columns.

2. The n^{th} triangular number, t_{n}, is the sum of the first n positive integers, t_{n} = 1+2+3+ … + n. So, for example, t_{1} = 1, t_{2} = 3 = 1 + 2, t_{3} = 6 = 1 + 2 + 3, and t_{341} = 41, 311.

(a) Prove that N is triangular if and only if N = n(n + 1)/2 for some positive integer n.

(b) Prove N is triangular iff 8N + 1 is a perfect square.

(c) Prove that the sum of two consecutive triangular numbers is a perfect square.

(d) Prove that if N is triangular, then 9N + 1 and 25N + 3 are triangular.

(e) Generalize the previous result.

(f) Find a simple formula for the sum of the first M triangular numbers.

(g) Are there any squares that are also triangular numbers?

3. Show that 7|2^{3n} − 1, for all n.

4. Show that 8|3^{2n} + 7, for all n.

5. Show that 2^{n} + (−1)^{n+1} is always divisible by 3.

6. Show that the sum of the squares of 2 odd integers cannot be itself a square.

7. Find gcd(7469, 2464), gcd(2689, 4001), gcd(2947, 3997), and gcd(1109, 4999).

8. Solve 43x + 64y = 1 and 1819x + 3587y = gcd(1819, 3587).

9. Prove that n^{5} − n is always divisible by 30.

10. Prove that the only prime one less than a cube is 7.

11. Find all primes, p, such that 3p + 1 is a square.

12. Prove that every positive integer of the form 4k + 3 has a prime factor of that same form.

13. Prove there exist infinitely primes of the form 4k + 3.

14. Prove there exist infinitely primes of the form 6k + 5.

15. Prove there exist infinitely primes of the form 4k + 1.

16. Every integer greater than 11 can be written as the sum of two composite numbers.

17. A perfect number is equal to the sum of its divisors (not including itself). Find some perfect numbers.

18. Characterize the even perfect numbers. Hint: factor. (No one knows if there are any odd perfect numbers.)

19. Find the primes that are one less than a power of two. (Hint: what must be true of the exponent?)

20. Find the primes that are one more than a power of two.

21. Every odd positive integer is the sum of a prime and a power of two.

22. Find all the possible pairs of digits that can appear at the end of a perfect square.

23. Find all positive integers that can be expressed as the sum of some number of consecutive positive integers.

24. There are arbitrarily long strings of consecutive composite numbers.

25. On the other hand, there are at least n + 1 primes less than 2^{2^{n}}, for all n ≥ 1.

26. Even better, there is always a prime between n and 2n, for n ≥ 2.

27. What is the smallest positive integer n such that n^{2} ± n + 41 is not prime? How about n^{2} − 79n + 1601?

28. Prove that no polynomial with integer coefficients can take only prime values on the integers. That is, the minima in the above problem were guaranteed to exist!

29. Find the primes that are one more than a square.