 4.4.1E: Show that 15 is an inverse of 7 modulo 26.
 4.4.2E: Show that 937 is an inverse of 13 modulo 2436.
 4.4.3E: By inspection (as discussed prior to Example 1), find an inverse of...
 4.4.4E: By inspection (as discussed prior to Example 1), find an inverse of...
 4.4.5E: Find an inverse of a modulo m for each of these pairs of relatively...
 4.4.6E: Find an inverse of a modulo m for each of these pairs of relatively...
 4.4.7E: Show that if a and m are relatively prime positive integers, then t...
 4.4.8E: Show that an inverse of a modulo m. where a is an integer and m > 2...
 4.4.9E: Solve the congruence 4x ? 5 (mod 9) using the inverse of 4 modulo 9...
 4.4.10E: Solve the congruence 2x ? 7 (mod 17) using the inverse of 2 modulo ...
 4.4.11E: Solve each of these congruences using the modular inverses found in...
 4.4.12E: Solve each of these congruences using the modular inverses found in...
 4.4.13E: Find the solutions of the congruence 15 x 2 + 19 x ? 5 (mod 11). [H...
 4.4.14E: Find the solutions of the congruence 12 x2 + 25 x = 10 (mod 11). [H...
 4.4.15E: Show that if m is an integer greater than 1 and ac ? bc (mod m), th...
 4.4.16E: a) Show that the positive integers less than 11, except 1 and 10, c...
 4.4.17E: Show that if p is prime, the only solutions of x2 ? 1 (mod p) are i...
 4.4.18E: a) Generalize the result in part (a) of Exercise 16; that is, show ...
 4.4.19E: This exercise outlines a proof of Fermat's little theorem.a) Suppos...
 4.4.20E: Use the construction in the proof of the Chinese remainder theorem ...
 4.4.21E: Use the construction in the proof of the Chinese remainder theorem ...
 4.4.22E: Solve the system of congruence x ? 3 (mod 6) and x ? 4 (mod 7) usin...
 4.4.23E: Solve the system of congruences in Exercise 20 using the method of ...
 4.4.24E: Solve the system of congruences in Exercise 21 using the method of ...
 4.4.25E: Write out in pseudocode an algorithm for solving a simultaneous sys...
 4.4.26E: Find all solutions, if any, to the system of congruences x ? 5 (mod...
 4.4.27E: Find all solutions, if any, to the system of congruences a ? 7 (mod...
 4.4.28E: Use the Chinese remainder theorem to show that an integer a, with 0...
 4.4.29E: Let m1, m2,….. mn be pairwise relatively prime integers greater tha...
 4.4.30E: Complete the proof of the Chinese remainder theorem by showing that...
 4.4.31E: Which integers leave a remainder of 1 when divided by 2 and also le...
 4.4.32E: Which integers are divisible by 5 but leave a remainder of 1 when d...
 4.4.33E: Use Fermat's little theorem lo find 7121 mod 13.
 4.4.34E: Use Fermat's little theorem to find 231002 mod 41.
 4.4.35E: Use Fermat's little theorem to show that if p is prime and then ap?...
 4.4.36E: Use Exercise 35 to find an inverse of 5 modulo 41.
 4.4.37E: a) Show that 2340 = 1 (mod 11) by Fermat's little theorem and notin...
 4.4.38E: a) Use Fermat's little theorem to compute 3302 mod 5, 3302 mod 7, a...
 4.4.39E: a) Use Fermat's little theorem to compute 52003 mod 7, 52003 mod 11...
 4.4.40E: Show with the help of Fermat's little theorem that if n is a positi...
 4.4.41E: Show that if p is an odd prime, then every divisor of the Mcrsenne ...
 4.4.42E: Use Exercise 41 to determine whether M13 = 213 ? 1 = 8191 and M23= ...
 4.4.43E: Use Exercise 41 to determine whether M11 =211 ? 11 = 2047 and M17 =...
 4.4.44E: Show that if n is prime and b is a positive integer with then n pas...
 4.4.45E: Show that 2047 is a strong pseudoprime to the base 2 by showing tha...
 4.4.46E: Show that 1729 is a Carmichael number.
 4.4.47E: Show that 2821 is a Carmichael number.
 4.4.48E: Show that if n = p1p2?pk where p1p2?pkarc distinct primes that sati...
 4.4.49E: a) Use Exercise 48 to show that every integer of the form (6m + 1)(...
 4.4.50E: Find the nonnegative integer a less than 28 represented by each of ...
 4.4.51E: Express each nonnegative integer a less than 15 as a pair (a mod 3,...
 4.4.52E: Explain how to use the pairs found in Exercise 51 to add 4 and 7.
 4.4.53E: Solve the system of congruences that arises in Example 8.
 4.4.54E: Show that 2 is a primitive root of 19.
 4.4.55E: Find the discrete logarithms of 5 and 6 to the base 2 modulo 19.
 4.4.56E: Let p be an odd prime and r a primitive root of p. Show that if a a...
 4.4.57E: Write out a table of discrete logarithms modulo 17 with respect to ...
 4.4.58E: Which integers are quadratic residues of 11?
 4.4.59E: Show that if p is an odd prime and a is an integer not divisible by...
 4.4.60E: Show that if p is an odd prime, then there are exactly (p ? l)/2 qu...
 4.4.61E: Show that if p is an odd prime and a and b arc integers with a ? b ...
 4.4.62E: Prove Euler's criterion, which states that if p is ail odd prime an...
 4.4.63E: Use Exercise 62 to show that if p is an odd prime and a and b are i...
 4.4.64E: Show that if p is an odd prime, then ? 1 is a quadratic residue of ...
 4.4.65E: Find all solutions of the congruence x2 ? 29 (mod 35). [Hint: Find ...
 4.4.66E: Find all solutions of the congruence, x2 = 16 (mod 105). [Hint: Fin...
 4.4.67E: Describe a brute force algorithm for solving the discrete logarithm...
Solutions for Chapter 4.4: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 4.4
Get Full SolutionsChapter 4.4 includes 67 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 67 problems in chapter 4.4 have been answered, more than 153109 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 expansive textbook survival guide covers the following chapters and their solutions.

Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (A).

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].

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

Diagonal matrix D.
dij = 0 if i # j. Blockdiagonal: zero outside square blocks Du.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

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.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Iterative method.
A sequence of steps intended to approach the desired solution.

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Ql. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Schwarz inequality
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).