home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11041 < prev    next >
Encoding:
Text File  |  1992-09-07  |  6.6 KB  |  171 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!wupost!usc!sol.ctr.columbia.edu!usenet.ucs.indiana.edu!newshost.cs.rose-hulman.edu!news
  3. From: goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard)
  4. Subject: More number theory problems (complete)
  5. Message-ID: <1992Sep5.144920.5797@cs.rose-hulman.edu>
  6. Sender: news@cs.rose-hulman.edu (The News Administrator)
  7. Nntp-Posting-Host: g214-1.nextwork.rose-hulman.edu
  8. Organization: Rose-Hulman Institute of Technology
  9. Date: Sat, 5 Sep 1992 14:49:20 GMT
  10. Lines: 159
  11.  
  12.  
  13. Thanks to those who have sent solutions.  This is a long post, 
  14. wherein I update the problem list.  Last time I referred to some
  15. problems only by number.  This time, "everything is here". Please
  16. email solutions.  To refresh your memory:
  17.  
  18. >So here's the deal.  If you send me a solution to one of the problems  
  19. >below, and I like, it I might send you 2 bucks.  Also, I'll post nice  
  20. >solutions for the benefit of your ego!  
  21.  
  22. 5.2.6 Is solved.  It had a typo (change the last 2 to a 1).
  23.  
  24. 5.3.4 is solved.  (It was trivial, <blush>.)
  25.  
  26. 2.2.24 Let a and b be positive integers and let r_j and q_j be the
  27. remainders and quotients of the steps of the Euclidean algorithm as  
  28. defined in "this section".
  29. a)   find the value of \sum_{j=1}^{n} r_j q_j.
  30.  
  31. b)   find the value of \sum_{j=1}^{n} (r_j)^{2} q_j.
  32.  
  33. 8.6.10 is solved.
  34.  
  35. 8.6.14 Find all Charmicheal numbers of the form 5pq where p and q are  
  36. primes. (I have an ugly solution,  maybe the casework could be cut  
  37. down?)
  38.  
  39. 8.6.18  Show that if (a,n) = 1 then q_n(a+nc)==
  40. q_n(a + \lambda(n) c a^{-1} (mod n).  (We define q_n(a) ==   
  41. (a^{\lambda(n)}-1/n modulo n, with 0 <= q_n(a) < n.)
  42. (\lambda(n) is the minimal universal exponent.)
  43.  
  44. HERE'S THAT DOUBLE STARRED PROBLEM YOU'VE BEEN ASKING FOR!:
  45. 9.4.8  Let the composite positive integer n have prime factorization
  46. n= p_{1}^{a_1}...p_{m}^{a_m}, where p_j = 1+2^{k_j}q_{j} for j = 1, 2,  
  47. .. m, where k_1 <= k_2 <= ... <= k_m, and where n=1+2^{k}q.  Show that
  48. n is an Euler pseudoprime to exactly
  49.  
  50. \delta_n \prod_{j=1}^{m}  gcd((n-1)/2, p_{j}-1)
  51.  
  52. different bases b, with 1<= b < n , where 
  53.  
  54.            ( 2     if k_1 = k
  55.        (
  56. \delta_n = (1/2    if k_j < k and a_j is odd for some j
  57.            (
  58.        ( 1     otherwise.
  59.        
  60. (An Euler pseudoprime to the base b in an odd composite which satisfies
  61.  
  62. b^{(n-1)/2} == (b/n)  (mod n)  
  63.  
  64. (b/n) is the Jacobi symbol. 
  65.  
  66. Whew!  That's probably a result from someones paper.  A reference would 
  67. be sufficient for my needs.
  68.  
  69. 10.4.18 Is solved.  It should have read "D = (ta_k +1)^2 + 
  70. 2ta_{k-1} +1".
  71.  
  72. A PREAMBLE:
  73. The greatest common divisor of two integers can be found using only 
  74. subtractions, parity checks, and shifts of binary expansions, without
  75. using any divisions.  The algorithm proceeds recursively using the
  76. following reduction:
  77.  
  78.         (  a          if a=b
  79.     (
  80.     ( 2(a/2,b/2)  if a and b are even
  81. (a,b) = (
  82.         ( (a/2,b)     if a is even and b is odd
  83.     (
  84.     ( (a-b,b)     if a and b are odd and a>b.
  85.  
  86. Reverse the roles of a and b when necessary.
  87.  
  88. 2.2.12  Show that to find (a,b) this algorithm uses the subtraction  
  89. step in the reduction no more than 1 + [log_{2} ( max(a,b) )] times.
  90.  
  91. ANOTHER PREAMBLE:
  92. Briefly, we want to consider the "least-remainder algorithm". It is 
  93. analogous to the Euclidean algorithm, but each remainder is chosen
  94. to have the smallest absolute value instead of the smallest nonnegative 
  95. value.  Let r_0 = a and r_1 = b.  Then we have
  96.  
  97. r_0 = r_1 q_1 + e_2 r_2,       -r_1/2 < e_2 r_2 <= r_1/2
  98.        .
  99.        .
  100.        .
  101. r_{n-2} = r_{n-1} q_{n-1} + e_n r_n,     -r_{n-1}/2 < e_n r_n <=  
  102. r_{n-1}/2
  103. r_{n-1} = r_n q_n
  104.  
  105. and (a,b) = r_n.  Note that r_j is always positive; we let e_j = +-1 be  
  106. the sign.
  107.  
  108. 2.2.16 (double starred!) Show that the least-remainder algorithm is  
  109. always faster or as fast as the Euclidean algorithm. (Hint:  First show  
  110. that if a and b are positive integers with 2b<a, than the least  
  111. remainder algorithm can find (a,b) in no more steps than it uses to  
  112. find (a, a-b).)
  113.  
  114. 2.2.18  Show that the number of divisions needed to find the gcd of two 
  115. positive integers using the least remainder algorithm is less than
  116. 8/3 times the number of digits in the smaller of the two numbers, plus  
  117. 4/3.
  118.  
  119. YET ANOTHER PREAMBLE:
  120.  
  121. The game of Euclid: Two players begin with a pair of positive integers  
  122. and take turns making moves of the following type.  A player can move  
  123. from the pair {x,y}, with x>=y, to any of the pairs {x-ty,y}, where t  
  124. is a positive integer and x-ty >=0.  A winning move consists of moving  
  125. to a pair with one element equal to 0.
  126.  
  127. For reference, 2.2.21 (which is solved) states: Every sequence of moves
  128. starting at {a,b}, must end with {0,(a,b)}.
  129.  
  130. 2.2.22  Show that ina game beginning with the pair {a,b}, the first  
  131. player may play a winning strategy if a=b or if  a > b(1 + \sqrt{5})/2;  
  132. otherwise, the second player may play a winning strategy.  (Hint:   
  133. First show that if y<x<=y(1 + \sqrt{5})/2 then there is a unique move  
  134. from {x,y} that goes to a pair {z,y} with y>z(1 + \sqrt{5})/2.)
  135.  
  136. In the next problem, part (a) is solved but part (b) is stubborn.  It's 
  137. not a starred problem, so I'm starting to suspect a typo...
  138.  
  139. 5.2.11.a (Solved) Show that if n is a pseudoprime to the base a but not
  140. a pseudoprime to the base b, where (a,n)=(b,n)=1, then n is not a 
  141. pseudoprime to the base ab.
  142.  
  143. 5.2.11.b Show that if there is an integer b with (b,n)=1 such that n is
  144. not a pseudoprime to the base b, then n is a pseudoprime to <= \phi(n)
  145. different bases a, with 1<=a<n.  (Hint: Show that the sets a_1, a_2,  
  146. .., a_r, and ba_1, ba_2,...,ba_r have no common elements, where a_1,  
  147. a_2, ..., a_r, are the bases less than n to which n is a pseudoprime.)
  148.  
  149. 8.6.16 (Should be easy if one knows all the notation and terminology)  
  150. Show that the deciphering exponent d for an RSA cipher with enciphering  
  151. key (e,n) can be taken to be an inverse of e mod \lambda(n) (minimal  
  152. universal exponent).  (n = pq is the modulus, and e in the enciphering  
  153. exponent.)
  154.  
  155. THE NEXT TWO PROBLEMS ARE FROM THE "PSEUDO-RANDOM NUMBER" SECTION
  156.  
  157. 8.7.6 Show that every linear congruential pseudo-random number  
  158. generator can be simply expressed in terms of a linear congruential  
  159. generator with increment c=1 and seed 0, by showing that the terms  
  160. generated by the linear congruential generator x_{n+1} == ax_{n} + c  
  161. (mod m), with seed x_0, can be expressed as x_n == b y_{n} + x_0 (mod  
  162. m), where b == (a-1)x_0 + c (mod m), y_0 = 0 and y_{n+1} == ay_n +1  
  163. (mod m).
  164.  
  165. 8.7.8 Show that the maximal possible period length for a pure  
  166. multiplicative generator of the form x_{n+1} == ax_n (mod 2^e), e>=3,  
  167. is 2^{e-2}.  Show that this is obtained when a == +-3 (mod 8).
  168.  
  169. Bart Goddard
  170. goddard@nextwork.rose-hulman.edu
  171.