 39.39.1: Suppose you wish to factor a positive integer n. You could write a ...
 39.39.2: Factor the following positive integers into primes. a. 25. b. 4200....
 39.39.3: Let x be an integer. Prove that 2jx and 3jx if and only if 6jx. Gen...
 39.39.4: Suppose a is a positive integer and p is a prime. Prove that pja if...
 39.39.5: Prove Lemma 39.2 using Theorem 39.1.
 39.39.6: Prove Lemma 39.3 by induction (or WellOrdering Principle) using Le...
 39.39.7: Suppose we wish to compute the greatest common divisor of two 1000...
 39.39.8: Let a and b be positive integers. Prove that a and b are relatively...
 39.39.9: Let a and b be positive integers. Prove that 2 a and 2 b 1 are rela...
 39.39.10: Let a and b be integers. A common multiple of a and b is an integer...
 39.39.11: Let a 2 Z and suppose a 2 is even. Prove that a is even.
 39.39.12: Generalize the previous exercise. Prove that if a; p 2 Z with p a p...
 39.39.13: Prove that consecutive perfect squares are relatively prime
 39.39.14: Let n be a positive integer and suppose we factor n into primes as ...
 39.39.15: Recall (see Exercise 3.13) that an integer n is called perfect if i...
 39.39.16: In this problem we consider the question: How many integers, from 1...
 39.39.17: Eulers totient, continued. Suppose p and q are unequal primes. Prov...
 39.39.18: Eulers totient, continued further. Suppose n D p1p2 pt where the pi...
 39.39.19: Again with Eulers totient. Now suppose n is any positive integer. F...
 39.39.20: Rewrite the second proof of Proposition 39.6 to show the following:...
 39.39.21: Explain why we may assume a and b are both positive in the third pr...
 39.39.22: Prove that log2 3 is irrational.
 39.39.23: Sieve of Erasothenes. Here is a method for finding many prime numbe...
 39.39.24: In this and the subsequent problems, you will be working in a diffe...
 39.39.25: Let w D a C b p 3 2 Z p 3. Define the norm of w to be N.w/ D a 2 C ...
 39.39.26: Let w; z 2 Z p 3. We say that w divides z provided there is a q 2 Z...
 39.39.27: Let w 2 Z p 3 with w 6D 0; 1. Prove that w can be factored into irr...
 39.39.28: We have reached the main point of this series of problems about Z p...
Solutions for Chapter 39: Factoring
Full solutions for Mathematics: A Discrete Introduction  3rd Edition
ISBN: 9780840049421
Solutions for Chapter 39: Factoring
Get Full SolutionsThis textbook survival guide was created for the textbook: Mathematics: A Discrete Introduction, edition: 3. This expansive textbook survival guide covers the following chapters and their solutions. Since 28 problems in chapter 39: Factoring have been answered, more than 8950 students have viewed full stepbystep solutions from this chapter. Chapter 39: Factoring includes 28 full stepbystep solutions. Mathematics: A Discrete Introduction was written by and is associated to the ISBN: 9780840049421.

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

Column space C (A) =
space of all combinations of the columns of A.

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

Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

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.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

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

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

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

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

Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.

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

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.