 4.3.1E: Determine whether each of these integers is prime.a) 21____________...
 4.3.2E: Determine whether each of these integers is prime.a) 19____________...
 4.3.3E: Find the prime factorization of each of these integers.a) 88_______...
 4.3.4E: Find the prime factorization of each of these integers.a) 39_______...
 4.3.5E: Find the prime factorization of 10!.
 4.3.6E: How many zeros are there at the end of 100!?
 4.3.7E: Express in pseudocode the trial division algorithm for determining ...
 4.3.8E: Express in pseudocode the algorithm described in the text for findi...
 4.3.9E: Show that if am + 1 is composite if a and m are integers greater th...
 4.3.10E: Show that if 2m +1 is an odd prime, then m = 2n for some nonnegativ...
 4.3.11E: Show that log2 3 is an irrational number. Recall that an irrational...
 4.3.12E: Prove that for every positive integer n, there are n consecutive c...
 4.3.13E: Prove or disprove that there are three consecutive odd positive int...
 4.3.14E: Which positive integers less than 12 are relatively prime to 12?
 4.3.15E: Which positive integers less than 30 are relatively prime to 30?
 4.3.16E: Determine whether the integers in each of these sets are pairwise r...
 4.3.17E: Determine whether the integers in each of these sets are pairwise r...
 4.3.18E: We call a positive integer perfect if it equals the sum of its posi...
 4.3.19E: Show that if 2n 1 is prime, then n is prime. [Hint: Use the identi...
 4.3.20E: Determine whether each of these integers is prime, verifying some ...
 4.3.21E: Find these values of the Euler ? function.a) ?(4).________________b...
 4.3.22E: Show that n is prime if and only if ?(n) = n  1.
 4.3.23E: What is the value of ?(pk) when p is prime and k is a positive inte...
 4.3.24E: What are the greatest common divisors of these pairs of integers?a)...
 4.3.25E: What are the greatest common divisors of these pairs of integers?a)...
 4.3.26E: What is the least common multiple of each pair in Exercise 24?
 4.3.27E: What is the least common multiple of each pair in Exercise 25?
 4.3.28E: Find gcd(1000, 625) and lcm(1000, 625) and verify that gcd(1000, 62...
 4.3.29E: Find gcd(92928,123552) and lcm(92928, 123552), and verify that gcd(...
 4.3.30E: If the product of two integers is 27 38 52 711 and their greatest ...
 4.3.31E: Show that if a and b are positive integers, then ab = gcd(a , b)· l...
 4.3.32E: Use the Euclidean algorithm to finda) gcd(1, 5).________________b) ...
 4.3.33E: Use the Euclidean algorithm to finda) gcd(12, 18).________________b...
 4.3.34E: How many divisions are required to find gcd(21, 34) using the Eucli...
 4.3.35E: How many divisions are required to find gcd(34, 55) using the Eucli...
 4.3.36E: Show that if a and b are both positive integers, then (2a  1) mod ...
 4.3.37E: Use Exercise 36 to show that if a and b are positive integers, the...
 4.3.38E: Use Exercise 37 to show that the integers 235  1, 234  1, 233  1...
 4.3.39E: Using the method followed in Example 17, express the greatest commo...
 4.3.40E: Using the method followed in Example 17, express the greatest commo...
 4.3.41E: Use the extended Euclidean algorithm to express gcd(26, 91) as a li...
 4.3.42E: Use the extended Euclidean algorithm to express gcd(252, 356) as a ...
 4.3.43E: Use the extended Euclidean algorithm to express gcd( 144, 89) as a ...
 4.3.44E: Use the extended Euclidean algorithm to express gcd(1001, 100001) a...
 4.3.45E: Describe the extended Euclidean algorithm using pseudocode.
 4.3.46E: Find the smallest positive integer with exactly n different positiv...
 4.3.47E: Can you find a formula or rule for the nth term of a sequence rela...
 4.3.48E: Can you find a formula or rule for the nth term of a sequence relat...
 4.3.49E: Prove that the product of any three consecutive integers is divisib...
 4.3.50E: Show that if a, b, and m are integers such that m ? 2 and a ? b (mo...
 4.3.51E: Prove or disprove that n2  79n + 1601 is prime whenever n is a po...
 4.3.52E: Prove or disprove that p1 p2 ···pn+ 1 is prime for every positive i...
 4.3.53E: Show that there is a composite integer in every arithmetic progress...
 4.3.54E: Adapt the proof in the text that there are infinitely many primes t...
 4.3.55E: Adapt the proof in the text that there are infinitely many primes t...
 4.3.56E: Prove that the set of positive rational numbers is countable by set...
 4.3.57E: Prove that the set of positive rational numbers is countable by sho...
Solutions for Chapter 4.3: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 4.3
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 57 problems in chapter 4.3 have been answered, more than 109455 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 4.3 includes 57 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095.

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

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.

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

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Fibonacci numbers
0,1,1,2,3,5, ... satisfy Fn = Fnl + Fn 2 = (A7 A~)I()q A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } 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.

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

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 .

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

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

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

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.

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.

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

Singular matrix A.
A square matrix that has no inverse: det(A) = o.

Stiffness matrix
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.

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

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

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.