 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) \(\operatorname{gcd}(1,5)\)....
 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 sh...
Solutions for Chapter 4.3: Primes and Greatest Common Divisors
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 4.3: Primes and Greatest Common Divisors
Get Full SolutionsSummary of Chapter 4.3: Primes and Greatest Common Divisors
Primes have become essential in modern cryptographic systems, and we will develop some of their properties important in cryptography.
This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 57 problems in chapter 4.3: Primes and Greatest Common Divisors have been answered, more than 700368 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 4.3: Primes and Greatest Common Divisors includes 57 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

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.

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

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

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

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

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

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

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

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

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

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