Web hosting india - 4.5.4 ANSWERS TO EXERCISES 611 15. U,, =
4.5.4 ANSWERS TO EXERCISES 611 15. U,, = (a*–b )/a, w h ere a = i(P+&?), b = *(P-a), D = P2-4Q. Then 2n-1U,, = c, (2kyI)Pn-2k- Dk; so U, = D(p-1) 2 (modulo p) if p is an odd prime. Similarly, if V, = an + bn = Un+l -QU,-1, then ZnmlVn = c, ($)Pn-2kDk, and V, = P = P. Thus if U, = -1, we find that Upfl modp = 0. If U, E 1, we find that (QU,-I) modp = 0; here if Q is a multiple of p, U, = Pnwl (modulo p) for n > 0, so U,, is never a multiple of p; if Q is not a multiple of p, U,-l modp = 0. Therefore as in Theorem L, Ut mod N = 0 if N = p; . . . p: , gcd(N, Q) = 1, and t = lcmlsjs7(pe3-1 (p, + Ed)). Under the assumptions of this exercise, the rank of apparition of N ;s N + 1; hence N is prime to Q and t is a multiple of N + 1. Also, the assumptions of this exercise imply that each p, is odd and each Ed is fl, so t 5 2l- npT- (pJ + ip3) = 2(3) N; hence r = 1 and t = pi + ~lpE~-~. Finally, therefore, el = 1 and tl = 1. Note: If this test for primality is to be any good, we must choose P and Q in such a way that the test will probably work. Lehmer suggests taking P = 1 so that D = 1 -4Q, and choosing Q so that gcd(N, QD) = 1. (If the latter condition fails, we know already that N is not prime, unless I&D1 2 N.) Furthermore, the derivation above shows that we will want ~1 = 1, that is, D(N- )/2 = -1 (modulo N). This is another condition that determines the choice of Q. Furthermore, if D satisfies this condition, and if UN+I mod N # 0, we know that N is not prime. Example: If P = 1 and Q = -1, we have the Fibonacci sequence, with D = 5. Since 511 = -1 (modulo 23), we might attempt to prove that 23 is prime by using the Fibonacci sequence: (F, mod 23) = 0, 1, 1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0, . . , so 24 is the rank of apparition of 23 and the test works. However, the Fibonacci sequence cannot be used in this way to prove the primality of 13 or 17, since F7 mod 13 = 0 and Fg mod 17 = 0. When p = fl (modulo lo), we have 5(p-1)/2 modp = 1, so Fp-l (not Fp+l) is divisible by p. 17. Let f(q) = 2 lg q -1. When q = 2 or 3, the tree has at most f(q) nodes. When q > 3 is prime, let q = 1 + 41.. . qt where t 2 2 and 41, , qt are prime. The size of the tree is 5 1 + c f(qk) = 2 + f(q -1) -t < f(q). [SIAM J. Computing 7 (1975), 214-220.1 18. z(G(a) -F(a)) is th e number of 7~ 5 z whose second-largest prime factor is 5 xoL and whose largest prime factor is > !I?. Hence xG (t)dt = (T(x~+~~) -T(x )) . x1-t(G(t/(l -t)) -F(t/(l -t))) The probability that ptpl 5 fi is so1 F(t/2(1 -t))t- dt. [Curiously, it can be shown that this also equals JO1 F(t/(l -t)) dt, the average value of logptllogz, and it also equals Golomb s constant X of exercises 1.3.3-23 and 3.1-13. The derivative G (0) can be shown to equal so1 F(t/(l -t))tm2 dt = F(1) + 2F(i) + 3F(i) + = ey. The third-largest prime factor has H(a) = Joa(H(t/(l -t)) -G(t/(l -t)))t- dt and H (0) = co. See P. Billingsley, Period. Math. Hungar. 2 (1972), 283-289; J. Galambos, Acta Arith. 31 (1976), 213-218; D. E. Knuth and L. Trabb Pardo, Theoretical Camp. Sci. 3 (1976), 321-348.1