 16.1: Use Pollard's rhomethod to factor the following integers:(a) 299.(...
 16.2: Find a nontrivial factor of 4087 by the rhomethod employing the in...
 16.3: By applying Pollard's p  1 method, obtain a factorization of(a) 17...
 16.4: Use the continued fraction factorization algorithm to factor each o...
 16.5: Factor 1189 by applying the continued fraction factorization algori...
 16.6: Use the quadratic sieve method to factor each of the following inte...
 16.7: Use Lucas's primality test to the base a to deduce that the integer...
 16.8: Verify the primality of the following integers by means of Poclding...
 16.9: Show that Pocklington's theorem leads to the following result of E....
 16.10: Use Proth's result to establish the primality of the following:(a) ...
 16.11: An odd composite integer that passes the MillerRabin test to the b...
 16.12: Establish that there are infinitely many strong pseudoprimes to the...
 16.13: For any composite Fermat number Fn = 22" + 1, prove that Fn is a st...
 16.14: Find the last digit of 19991999 and the last two digits of 34321
 16.15: The three children in a family have feet that are 5, 7, and 9 inche...
 16.16: In the sequence of triangular numbers, suppose thattn(tn1 + tn+l) ...
 16.17: Prove that a repunit prime Rn cannot be expressed as the sum of two...
 16.18: Find the remainder when 70!/18 is divided by 71.
 16.19: State and prove the general result illustrated by42 = 16 342 = 1156...
 16.20: If p is a prime, show that p I (r(p)</>(p) + 2) and p I (r(p)a(p) ...
 16.21: Establish the formula Ld In (d)2w(n/d) = I (n) 1.
 16.22: Prove that n is an even integer if and only if Ld 1 n </>(d)(d) = 0.
 16.23: If r(n) is divisible by an odd prime, show that (n) = 0.
 16.24: Determine whether 97 divides n2  85 for some choice of n 1.
 16.25: Find all integers n that satisfy the equation(n  1)3 + n3 + (n + 1...
 16.26: Prove that the Fermat numbers are such thatFn + Fn+l = 1 (mod 7)
 16.27: Verify that 6 is the only squarefree even perfect number.
 16.28: Given any four consecutive positive integers, show that at least on...
 16.29: Prove that the terms of the Lucas sequence satisfy the congruence2n...
 16.30: Show that infinitely many Fibonacci numbers are divisible by 5, but...
 16.31: For the Fibonacci numbers, establish that 18 divides
 16.32: Prove that there exist infinitely many positive integers n such tha...
 16.33: If n = 5 (mod 10), show that 11 divides the sum12n + 9n + sn + 6n
 16.34: Establish the following:(a) 7 divides no number of the form 2n + 1,...
 16.35: For n = 4 (mod 9), show that the equation n = a3 + b3 + c3 has no i...
 16.36: Prove that if the odd prime p divides a2 + b2, where gcd(a, b) = 1,...
 16.37: Find an integer n for which the product 9999 n is a repunit.[Hint: ...
 16.38: Verify that 10 is the only triangular number that can be written as...
 16.39: Determine whether there exists a Euclidean numberp# + 1 = 2 . 3 . 5...
 16.40: Consider a prime p = 1 (mod 60). Show that there exist positive int...
 16.41: Prove that the sum299 + 2999 + 29999 + ... + 29999999999999is divis...
 16.42: Use Pell's equation to show that there are infinitely many integers...
 16.43: Given n > 0, show that there exist infinitely many k for which the ...
 16.44: Show that each term of the sequence16, 1156, 111556, 11115556, 1111...
 16.45: Find all primes of the form p2 + 2P, where p is a prime.
 16.46: The primes 37,67,73,79, ... are of the form p = 36ab + 6a  6b + 1,...
 16.47: Prove that n ! is not a perfect square for n > 1.[Hint: Use Bertran...
 16.48: A nearrepunit is an integer kRn that has n  1 digits equal to 1, ...
 16.49: Let p1, p2, , Pn be the first n primes in the natural order. Show t...
 16.50: Verify that there exist no primes p and q that satisfy the conditio...
Solutions for Chapter 16: PRIMALITY TESTING AND FACTORIZATION
Full solutions for Elementary Number Theory  7th Edition
ISBN: 9780073383149
Solutions for Chapter 16: PRIMALITY TESTING AND FACTORIZATION
Get Full SolutionsChapter 16: PRIMALITY TESTING AND FACTORIZATION includes 50 full stepbystep solutions. Since 50 problems in chapter 16: PRIMALITY TESTING AND FACTORIZATION have been answered, more than 5437 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Elementary Number Theory, edition: 7. Elementary Number Theory was written by and is associated to the ISBN: 9780073383149. This expansive textbook survival guide covers the following chapters and their solutions.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

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.

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

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.

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

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.

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

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

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

Permutation matrix P.
There are n! orders of 1, ... , n. The n! P 's have the rows of I in those orders. P A puts the rows of A in the same order. P is even or odd (det P = 1 or 1) based on the number of row exchanges to reach I.

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

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.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

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

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

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