 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) Suppo...
 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 tha...
 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 \(M_{11}=2^{11}1= 2047\) and...
 4.4.44E: ?Show that if \(n\) is prime and \(b\) is a positive integer with \...
 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 \((p1)...
 4.4.61E: ?Show that if \(p\) is an odd prime and \(a\) and \(b\) are integer...
 4.4.62E: ?Prove Euler's criterion, which states that if \(p\) is an odd prim...
 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: Solving Congruences
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 4.4: Solving Congruences
Get Full SolutionsSummary of Chapter 4.4: Solving Congruences
Simultaneous systems of linear congruence have been studied since ancient times. For example, the Chinese mathematician SunTsu studied them in the first century.
Chapter 4.4: Solving Congruences 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: Solving Congruences have been answered, more than 802733 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.

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

Column space C (A) =
space of all combinations of the columns of 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).

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

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

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.

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

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

Inverse matrix AI.
Square matrix with AI A = I and AAl = I. No inverse if det A = 0 and rank(A) < n and Ax = 0 for a nonzero vector x. The inverses of AB and AT are B1 AI and (AI)T. Cofactor formula (Al)ij = Cji! detA.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Outer product uv T
= column times row = rank one matrix.

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

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

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.

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

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.