 4.SE.1E: The odometer on a car goes to up 100,000 miles. The present owner o...
 4.SE.2E: a) Explain why n div 7 equals the number of complete weeks in n day...
 4.SE.3E: Find four numbers congruent to 5 modulo 17.
 4.SE.4E: Show that if a and d are positive integers, then there are integers...
 4.SE.5E: Show that if ac ? bc (mod m), where a.b.c, and m are integers with ...
 4.SE.6E: Show that the sum of the squares of two odd integers cannot be the ...
 4.SE.7E: Show that if n2 + 1 is a perfect square, where n is an integer, the...
 4.SE.8E: Prove that there are no solutions in integers x and y to the equati...
 4.SE.9E: Develop a test for divisibility of a positive integer n by 8 based ...
 4.SE.10E: Develop a test for divisibility of a positive integer n by 3 based ...
 4.SE.11E: Devise an algorithm for guessing a number between 1 and 2n – 1 by s...
 4.SE.12E: Determine the complexity, in terms of the number of guesses, needed...
 4.SE.13E: Show that an integer is divisible by 9 if and only if the sum of it...
 4.SE.14E: Show that if a and b are positive irrational numbers such that 1/a ...
 4.SE.15E: Prove there are infinitely many primes by showing that Qn = n! + 1 ...
 4.SE.16E: Find a positive integer n for which Qn =n! + 1 is not prime.
 4.SE.17E: Use Dirichlet’s theorem, which states there are infinitely many pri...
 4.SE.18E: Prove that if n is a positive integer such that the sum of the divi...
 4.SE.19E: Show that every integer greater than 11 is the sum of two composite...
 4.SE.20E: Find the five smallest consecutive composite integers.
 4.SE.21E: Show that Goldbach’s conjecture, which states that every even integ...
 4.SE.22E: Find an arithmetic progression of length six beginning with 7 that ...
 4.SE.23E: Prove that if f(x) is a nonconstant polynomial with integer coeffic...
 4.SE.24E: How many zeros are at the end of the binary expansion of 10010!?
 4.SE.25E: Use the Euclidean algorithm to find the greatest common divisor of ...
 4.SE.26E: How many divisions are required to find gcd(l44, 233) using the Euc...
 4.SE.27E: Find gcd(2n +1.3n + 2), where n is a positive integer. [Hint: Use t...
 4.SE.28E: a) Show that if a and b are positive integers with a ? b, then gcd(...
 4.SE.29E: Adapt the proof that there are infinitely many primes (Theorem 3 in...
 4.SE.30E: Explain why you cannot directly adapt the proof that there are infi...
 4.SE.31E: Explain why you cannot directly adapt the proof that there are infi...
 4.SE.32E: Show that if the smallest prime factor p of the positive integer n ...
 4.SE.33E: Determine whether the integers in each of these sets are mutually r...
 4.SE.34E: Find a set of four mutually relatively prime integers such that no ...
 4.SE.35E: For which positive integers n is n4 + 4n prime?
 4.SE.36E: Show that the system of congruences x ? 2 (mod 6) and x ? 3 (mod 9)...
 4.SE.37E: Find all solutions of the system of congruences x ? 4 (mod 6) and x...
 4.SE.38E: a) Show that the system of congruences.x: ? a2(modm1) and x ? a2 (m...
 4.SE.39E: Prove that 30 divides n9 – n for every nonnegative integer n.
 4.SE.40E: Prove that n12 – 1 is divisible by 35 for every integer n for which...
 4.SE.41E: Show that if p and q are distinct prime numbers, then pq1 + qpl =...
 4.SE.42E: Determine whether each of these 13digit numbers is a valid ISBN13...
 4.SE.43E: Show that the check digit of an ISBN –13 can always delect a single...
 4.SE.44E: Show that there are transpositions of two digits that are not detec...
 4.SE.45E: Show that if d1d2 ... d9) is a valid RTN, then d9 = 7(d1 + d4 + d7)...
 4.SE.46E: Show that the check digit of an RTN can detect all single errors an...
 4.SE.47E: The encrypted version of a message is LJMKG MGMXF QEXMW. If it was ...
 4.SE.48E: Use Algorithm 5 to find 11644 mod 645.
 4.SE.49E: Use the autokey cipher to encrypt the message THE DREAM OF REASON (...
Solutions for Chapter 4.SE: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 4.SE
Get Full SolutionsChapter 4.SE includes 49 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. Since 49 problems in chapter 4.SE have been answered, more than 245608 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

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.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

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 subspaces.
Every v in V is orthogonal to every w in W.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).