 36.36.1: Please calculate: a. gcd.20; 25/. b. gcd.0; 10/. c. gcd.123; 123/.d...
 36.36.2: For each pair of integers a; b in the previous problem, find intege...
 36.36.3: Write a computer program that calculates the greatest common diviso...
 36.36.4: Find integers a and b that do not have a greatest common divisor. P...
 36.36.5: Let a and b be positive integers. Find the sum of all the common di...
 36.36.6: Prove that if a and b have a greatest common divisor, it is unique ...
 36.36.7: In Proposition 36.3, we did not require that c 6D 0. Is Proposition...
 36.36.8: Suppose a b and running Euclids Algorithm yields the numbers (in li...
 36.36.9: Suppose we want to compute the greatest common divisor of two 1000...
 36.36.10: We can extend the definition of the gcd of two numbers to the gcd o...
 36.36.11: Prove that consecutive integers must be relatively prime
 36.36.12: Let a be an integer. Prove that 2a C 1 and 4a2 C 1 are relatively p...
 36.36.13: Let a and b be positive integers. Prove that 2 a and 2 b1 are relat...
 36.36.14: Suppose n and m are relatively prime integers. Prove that n and m C...
 36.36.15: Suppose that a and b are relatively prime integers and that ajc and...
 36.36.16: Suppose a; b; n 2 Z with n > 1. Suppose that ab 1 .mod n/. Prove th...
 36.36.17: Suppose a; n 2 Z with n > 1. Suppose that a and n are relatively pr...
 36.36.18: Suppose a; b 2 Z are relatively prime. Corollary 36.9 implies that ...
 36.36.19: Let x be a rational number. This means there are integers a and b 6...
 36.36.20: A class of n children sit in a circle. The teacher walks around the...
 36.36.21: You have two measuring cups. One holds 8 ounces and the other holds...
 36.36.22: In Exercise 35.12, we considered polynomial division. In this probl...
Solutions for Chapter 36: Greatest Common Divisor
Full solutions for Mathematics: A Discrete Introduction  3rd Edition
ISBN: 9780840049421
Solutions for Chapter 36: Greatest Common Divisor
Get Full SolutionsMathematics: A Discrete Introduction was written by and is associated to the ISBN: 9780840049421. Chapter 36: Greatest Common Divisor includes 22 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. Since 22 problems in chapter 36: Greatest Common Divisor have been answered, more than 9701 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Mathematics: A Discrete Introduction, edition: 3.

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

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

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.

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

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

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

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

Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Ql. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

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

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

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

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

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.

Tridiagonal matrix T: tij = 0 if Ii  j I > 1.
T 1 has rank 1 above and below diagonal.

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

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