- 7.1: Calculate <f>(lOOl), </>(5040), and </>(36,000).
- 7.2: Verify that the equality <f>(n) = <f>(n + 1) = <f>(n + 2) holds whe...
- 7.3: Show that the integers m = 3k 568 and n = 3k 638, where k 0, satisf...
- 7.4: Establish each of the assertions below:(a) If n is an odd integer, ...
- 7.5: Prove that the equation <f>(n) = <f>(n + 2) is satisfied by n = 2(2...
- 7.6: Show that there are infinitely many integers n for which <f>(n) is ...
- 7.7: Verify the following:(a) For any positive integer n, ,Jn:::; <f>(n)...
- 7.8: Prove that if the integer n has r distinct odd prime factors, then ...
- 7.9: Prove the following:(a) If n and n + 2 are a pair of twin primes, t...
- 7.10: If every prime that divides n also divides m, establish that <f>(nm...
- 7.11: (a) If <f>(n) In -1, prove that n is a square-free integer.[Hint: A...
- 7.12: If n = p1 p2 pr, derive the following inequalities:(a) cr(n)<f>(n) ...
- 7.13: Assuming that d I n, prove that (d) I (n ).[Hint: Work with the pri...
- 7.14: Obtain the following two generalizations of Theorem 7.2:(a) For pos...
- 7.15: Prove the following:(a) There are infinitely many integers n for wh...
- 7.16: Show that the Goldbach conjecture implies that for each even intege...
- 7.17: Given a positive integer k, show the following: (a) There are at mo...
- 7.18: Find all solutions of <f>(n) = 16 and (n) = 24.[Hint: If n = p1 p2 ...
- 7.19: (a) Prove that the equation (n) = 2p, where pis a prime number and ...
- 7.20: If p is a prime and k 2:: 2, show that ((pk)) = pk-2</J((p - 1)2).
- 7.21: Verify that </J(n)a(n) is a perfect square when n = 63457 = 23 31 89.
Solutions for Chapter 7: EULER'S PHI-FUNCTION
Full solutions for Elementary Number Theory | 7th Edition
Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.
Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x - x) (x - x) T is positive (semi)definite; :E is diagonal if the Xi are independent.
Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then S-I AS = A = eigenvalue matrix.
Gram-Schmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.
Hilbert matrix hilb(n).
Entries HU = 1/(i + j -1) = Jd X i- 1 xj-1dx. Positive definite but extremely small Amin and large condition number: H is ill-conditioned.
Incidence matrix of a directed graph.
The m by n edge-node incidence matrix has a row for each edge (node i to node j), with entries -1 and 1 in columns i and j .
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.
Left inverse A+.
If A has full column rank n, then A+ = (AT A)-I AT has A+ A = In.
Length II x II.
Square root of x T x (Pythagoras in n dimensions).
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.
A directed graph that has constants Cl, ... , Cm associated with the edges.
Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Q-l. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).
Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.
Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.
Similar matrices A and B.
Every B = M-I AM has the same eigenvalues as A.
Special solutions to As = O.
One free variable is Si = 1, other free variables = o.
Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.
Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.