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

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

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.

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.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Network.
A directed graph that has constants Cl, ... , Cm associated with the edges.

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

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

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Solvable system Ax = b.
The right side b is in the column space of A.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.

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.

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.