NUMBER-THEORY EXERCISES, II

DAVID PIERCE

These exercises are for Elementary Number Theory I (Math 365 at METU). In them, if a statement is given that is not a definition, then the exercise is to prove the statement.

A first set of exercises is the proofs not given in [2]. The exercises below are mostly inspired by exercises in [1, Ch. 2].

Recall that the triangular numbers compose a sequence (t_{n}: n ∈ ℕ), defined recursively by t_{0} = 0 and t_{n+1} = t_{n} + n + 1.

Exercise 1. An integer n is a triangular number if and only if 8n + 1 is a square number.

Exercise 2.

(a) If n is triangular, then so is 9n + 1.

(b) Find infinitely many pairs (k, ℓ) such that, if n is triangular, then so is kn + ℓ.

Exercise 3. If a = n(n + 3)/2, then t_{a} + t_{n+1} = t_{a+1}.

Exercise 4. The pentagonal numbers are 1, 5, 12, …: call these p_{1}, p_{2}, &c. (a) Give a recursive definition of these numbers.

(b) Find a closed expression for p_{n} (that is, an expression not involving p_{n−1}, p_{n−2}, &c.).

(c) Find such an expression involving triangular numbers and square numbers.

Exercise 5.

(a) 7 | 2^{3n} + 6.

(b) Given a in ℤ and k in ℕ, find integers b and c such that b | a^{kn} + c for all n in ℕ.

Exercise 6. gcd(a, a + 1) = 1.

Exercise 7. (k!)^{n} | (kn)! for all k and n in ℕ.

Exercise 8. If a and b are co-prime, and a and c are co-prime, then a and bc are co-prime.

Exercise 9. Let gcd(204, 391) = n.

(a) Compute n.

(b) Find a solution of 204x + 391y = n.

Exercise 10. Let gcd(a, b) = n.

(a) If k | ℓ and ℓ | 2k, then |ℓ| ∈ {|k| , |2k|}.

(b) Show gcd(a + b, a − b) ∈ {n, 2n}.

(c) Find an example for each possibility.

(d) gcd(2a + 3b, 3a + 4b) = n.

(e) Solve gcd(ax + by, az + bw) = n.

Exercise 11. gcd(a, b) | lcm(a, b).

Date: September 28, 2007.

2 DAVID PIERCE

Exercise 12. When are gcd(a, b) and lcm(a, b) the same? Exercise 13. The binary operation (x, y) ↦ gcd(x, y) on ℕ ∖ {0} is commutative and associative. Exercise 14. The co-prime relation on ℕ ∖ {0}, namely

{(x, y) ∈ ℕ ∖ {0}: gcd(x, y) = 1}

—is it reflexive? irreflexive? symmetric? anti-symmetric? transitive? Exercise 15. Give complete solutions, or show that they do not exist, for:

(a) 14x − 56y = 34;

(b) 10x + 11y = 12. Exercise 16. I have some 1-YTL pieces and some 50- and 25-YKr pieces: 16 coins in all. They make 6 YTL. How many coins of each denomination have I got?

References

[1] David M. Burton. Elementary Number Theory. McGraw-Hill, Boston, sixth edition, 2007.

[2] David Pierce. Foundations of number-theory. http://www.math.metu.edu.tr/~dpierce/ courses/365/. 4 pp. Mathematics Dept, Middle East Technical University, Ankara 06531, Turkey E-mail address: dpierce@metu.edu.tr URL: http://www.math.metu.edu.tr/~dpierce