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

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Cyclic shift
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.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

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.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b  Ax is orthogonal to all columns of A.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

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.

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Nullspace N (A)
= All solutions to Ax = O. Dimension n  r = (# columns)  rank.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

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

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).