The Integers: exercises

Practice (34)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Prove that \[\begin{aligned}\end{aligned}\] for \(n \in {\mathbb N}\).

   i

   Hint:

   The base case, \(S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2\) is true. Assume that \(S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6\) is true. Then \[\begin{aligned}1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2 \\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6\end{aligned}\], and so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\).

2. Prove that \[\begin{aligned}\end{aligned}\] for \(n \in {\mathbb N}\).

3. Prove that \(n! \gt 2^n\) for \(n \geq 4\).

   i

   Hint:

   The base case, \(S(4): 4! = 24 \gt 16 =2^4\) is true. Assume \(S(k): k! \gt 2^k\) is true. Then \((k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\), so \(S(k + 1)\) is true. Thus, \(S(n)\) is true for all positive integers \(n\).

4. Prove that \[\begin{aligned}\end{aligned}\] for \(n \in {\mathbb N}\).

5. Prove that \(10^{n + 1} + 10^n + 1\) is divisible by \(3\) for \(n \in {\mathbb N}\).

6. Prove that \(4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5\) is divisible by \(99\) for \(n \in {\mathbb N}\).

7. Show that \[\begin{aligned}\end{aligned}\].

8. Prove the Leibniz rule for \(f^{(n)} (x)\), where \(f^{(n)}\) is the \(n\)th derivative of \(f\); that is, show that \[\begin{aligned}\end{aligned}\].

   i

   Hint:

   Follow the proof in .

9. Use induction to prove that \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1\) for \(n \in {\mathbb N}\).

10. Prove that \[\begin{aligned}\end{aligned}\] for \(n \in {\mathbb N}\).

11. If \(x\) is a nonnegative real number, then show that \((1 + x)^n - 1 \geq nx\) for \(n = 0, 1, 2, \ldots\).

    i

    Hint:

    The base case, \(S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x\) is true. Assume \(S(k): (1 + x)^k -1 \geq kx\) is true. Then \[\begin{aligned}(1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1 \\ & = (1 + x)^k + x(1 + x)^k - 1 \\ & \geq kx + x(1 + x)^k \\ & \geq kx + x \\ & = (k + 1)x\end{aligned}\], so \(S(k + 1)\) is true. Therefore, \(S(n)\) is true for all positive integers \(n\).

12. Let \(X\) be a set. Define the power set of \(X\), denoted \({\mathcal P}(X)\), to be the set of all subsets of \(X\). \(\mathcal P(X)\) power set of \(X\) For example, \[\begin{aligned}\end{aligned}\]. For every positive integer \(n\), show that a set with exactly \(n\) elements has a power set with exactly \(2^n\) elements.

13. Prove that the two principles of mathematical induction stated in are equivalent.

14. Show that the Principle of Well-Ordering for the natural numbers implies that \(1\) is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if \(S \subset {\mathbb N}\) such that \(1 \in S\) and \(n + 1 \in S\) whenever \(n \in S\), then \(S = {\mathbb N}\).

15. For each of the following pairs of numbers \(a\) and \(b\), calculate \(\gcd(a,b)\) and find integers \(r\) and \(s\) such that \(\gcd(a,b) = ra + sb\).

    1. \(14\) and \(39\)

    2. \(234\) and \(165\)

    3. \(1739\) and \(9923\)

    4. \(471\) and \(562\)

    5. \(23771\) and \(19945\)

    6. \(-4357\) and \(3754\)

16. Let \(a\) and \(b\) be nonzero integers. If there exist integers \(r\) and \(s\) such that \(ar + bs =1\), show that \(a\) and \(b\) are relatively prime.

17. The Fibonacci numbers are \[\begin{aligned}\end{aligned}\]. We can define them inductively by \(f_1 = 1\), \(f_2 = 1\), and \(f_{n + 2} = f_{n + 1} + f_n\) for \(n \in {\mathbb N}\).

    1. Prove that \(f_n \lt 2^n\).

    2. Prove that \(f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\), \(n \geq 2\).

    3. Prove that \(f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\).

    4. Show that \(\phi = \lim_{n \rightarrow \infty} f_{n + 1} / f_n = (\sqrt{5} + 1)/2\). The constant \(\phi\) is known as the golden ratio.

    5. Prove that \(f_n\) and \(f_{n + 1}\) are relatively prime.

    i

    Hint:

    For (a) and (b) use mathematical induction. (c) Show that \(f_1 = 1\), \(f_2 = 1\), and \(f_{n + 2} = f_{n + 1} + f_n\). (e) Use part (b) and .

18. Let \(a\) and \(b\) be integers such that \(\gcd(a,b) = 1\). Let \(r\) and \(s\) be integers such that \(ar + bs = 1\). Prove that \[\begin{aligned}\end{aligned}\].

19. Let \(x, y \in {\mathbb N}\) be relatively prime. If \(xy\) is a perfect square, prove that \(x\) and \(y\) must both be perfect squares.

    i

    Hint:

    Use the Fundamental Theorem of Arithmetic.

20. Using the division algorithm, show that every perfect square is of the form \(4k\) or \(4k + 1\) for some nonnegative integer \(k\).

21. Suppose that \(a, b, r, s\) are pairwise relatively prime and that \[\begin{aligned}a^2 + b^2 & = r^2 \\ a^2 - b^2 & = s^2\end{aligned}\]. Prove that \(a\), \(r\), and \(s\) are odd and \(b\) is even.

22. Let \(n \in {\mathbb N}\). Use the division algorithm to prove that every integer is congruent mod \(n\) to precisely one of the integers \(0, 1, \ldots, n-1\). Conclude that if \(r\) is an integer, then there is exactly one \(s\) in \({\mathbb Z}\) such that \(0 \leq s \lt n\) and \([r] = [s]\). Hence, the integers are indeed partitioned by congruence mod \(n\).

23. Define the least common multiple of two nonzero integers \(a\) and \(b\), denoted by \(\lcm(a,b)\), to be the nonnegative integer \(m\) such that both \(a\) and \(b\) divide \(m\), and if \(a\) and \(b\) divide any other integer \(n\), then \(m\) also divides \(n\). \(\lcm(m,n)\) the least common multiple of \(m\) and \(n\) Prove there exists a unique least common multiple for any two integers \(a\) and \(b\).

    i

    Hint:

    Use the Principle of Well-Ordering and the division algorithm.

24. If \(d= \gcd(a, b)\) and \(m = \lcm(a, b)\), prove that \(dm = |ab|\).

25. Show that \(\lcm(a,b) = ab\) if and only if \(\gcd(a,b) = 1\).

26. Prove that \(\gcd(a,c) = \gcd(b,c) =1\) if and only if \(\gcd(ab,c) = 1\) for integers \(a\), \(b\), and \(c\).

27. Let \(a, b, c \in {\mathbb Z}\). Prove that if \(\gcd(a,b) = 1\) and \(a \mid bc\), then \(a \mid c\).

    i

    Hint:

    Since \(\gcd(a,b) = 1\), there exist integers \(r\) and \(s\) such that \(ar + bs = 1\). Thus, \(acr + bcs = c\).

28. Let \(p \geq 2\). Prove that if \(2^p - 1\) is prime, then \(p\) must also be prime.

29. Prove that there are an infinite number of primes of the form \(6n + 5\).

    i

    Hint:

    Every prime must be of the form \(2\), \(3\), \(6n + 1\), or \(6n + 5\). Suppose there are only finitely many primes of the form \(6k + 5\).

30. Prove that there are an infinite number of primes of the form \(4n - 1\).

31. Using the fact that \(2\) is prime, show that there do not exist integers \(p\) and \(q\) such that \(p^2 = 2 q^2\). Demonstrate that therefore \(\sqrt{2}\) cannot be a rational number.

32. One method of computing all of the prime numbers less than a certain fixed positive integer \(N\) is to list all of the numbers \(n\) such that \(1 \lt n \lt N\). Begin by eliminating all of the multiples of \(2\). Next eliminate all of the multiples of \(3\). Now eliminate all of the multiples of \(5\). Notice that \(4\) has already been crossed out. Continue in this manner, noticing that we do not have to go all the way to \(N\); it suffices to stop at \(\sqrt{N}\). Using this method, compute all of the prime numbers less than \(N = 250\). We can also use this method to find all of the integers that are relatively prime to an integer \(N\). Simply eliminate the prime factors of \(N\) and all of their multiples. Using this method, find all of the numbers that are relatively prime to \(N= 120\). Using the Sieve of Eratosthenes, write a program that will compute all of the primes less than an integer \(N\).

33. Let \({\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\). Ackermann's function is the function \(A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0\) defined by the equations \[\begin{aligned}A(0, y) & = y + 1, \\ A(x + 1, 0) & = A(x, 1), \\ A(x + 1, y + 1) & = A(x, A(x + 1, y))\end{aligned}\]. Use this definition to compute \(A(3, 1)\). Write a program to evaluate Ackermann's function. Modify the program to count the number of statements executed in the program when Ackermann's function is evaluated. How many statements are executed in the evaluation of \(A(4, 1)\)? What about \(A(5, 1)\)?

34. Write a computer program that will implement the Euclidean algorithm. The program should accept two positive integers \(a\) and \(b\) as input and should output \(\gcd( a,b)\) as well as integers \(r\) and \(s\) such that \[\begin{aligned}\end{aligned}\].

Symbols used here

\lim_{x \to a} f(x)

limit
The value f(x) approaches as x approaches a.

\sqrt{x},\ \sqrt[n]{x}

square root, n-th root
The non-negative number whose square (n-th power) is x.

\infty

infinity
Not a number: "grows without bound" in limits and intervals.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\sup,\ \inf

supremum, infimum
Least upper bound, greatest lower bound.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Kuri Gukoresha

⌨ Type ✎ Draw

Imibare

Gusiba

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

in Abstract Algebra

GroupsSubgroups, cosets and Lagrange's theoremCyclic groups and permutation groupsHomomorphisms, normal subgroups and quotient groupsRings and fieldsGalois theory: why the quintic has no formula