- 2.1: Each of the numbers1=1, 3 = 1+2, 6 = 1+2 + 3, 10 = 1+2 + 3 + 4, ......
- 2.2: If tn denotes the nth triangular number, prove that in terms of the...
- 2.3: Derive the following formula for the sum of triangular numbers, att...
- 2.4: Prove that the square of any odd multiple of 3 is the difference of...
- 2.5: In the sequence of triangular numbers, find the following:(a) Two t...
- 2.6: (a) If the triangular number tn is a perfect square, prove that t4n...
- 2.7: Show that the difference between the squares of two consecutive tri...
- 2.8: Prove that the sum of the reciprocals of the first n triangular num...
- 2.9: (a) Establish the identity tx = ty + tz, wheren(n + 3)x = + 12y=n +...
- 2.10: Each of the numbers1, 5 = 1 + 4, 12 = 1 + 4 + 7, 22 = 1 + 4 + 7 + 1...
- 2.11: For n 2:: 2, verify the following relations between the pentagonal,...
- 2.12: Prove that, for a positive integer n and any integer a, gcd(a, a+ n...
- 2.13: Given integers a and b, prove the following:(a) There exist integer...
- 2.14: For any integer a, show the following:(a) gcd(2a + 1, 9a + 4) = 1.(...
- 2.15: If a and b are integers, not both of which are zero, prove that gcd...
- 2.16: Given an odd integer a, establish thata2 +(a+ 2)2 +(a+ 4)2 + 1is di...
- 2.17: Prove that the expression (3n)!/(3!)n is an integer for all n =:::: 0.
- 2.18: Prove: The product of any three consecutive integers is divisible b...
- 2.19: Establish each of the assertions below:(a) If a is an arbitrary int...
- 2.20: Confirm the following properties of the greatest common divisor:(a)...
- 2.21: (a) Prove that if d I n, then 2d - 1 12n- 1.[Hint: Use the identity...
- 2.22: Let tn denote the nth triangular number. For what values of n does ...
- 2.23: If a I be, show that a I gcd(a, b) gcd(a, c)
Solutions for Chapter 2: EARLY NUMBER THEORY
Full solutions for Elementary Number Theory | 7th Edition
A = CTC = (L.J]))(L.J]))T for positive definite A.
Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn - l . Cx = convolution c * x. Eigenvectors in F.
z = a - ib for any complex number z = a + ib. Then zz = Iz12.
Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.
Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then S-I AS = A = eigenvalue matrix.
Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.
Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.
Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , Aj-Ib. Numerical methods approximate A -I b by x j with residual b - Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.
Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.
A directed graph that has constants Cl, ... , Cm associated with the edges.
Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.
Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Q-l. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.
Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.
R = [~ CS ] rotates the plane by () and R- 1 = RT rotates back by -(). Eigenvalues are eiO and e-iO , eigenvectors are (1, ±i). c, s = cos (), sin ().
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!
Symmetric matrix A.
The transpose is AT = A, and aU = a ji. A-I is also symmetric.
Tridiagonal matrix T: tij = 0 if Ii - j I > 1.
T- 1 has rank 1 above and below diagonal.
Unitary matrix UH = U T = U-I.
Orthonormal columns (complex analog of Q).