From: goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard)
Subject: More number theory problems (complete)
Organization: Rose-Hulman Institute of Technology
Date: Sat, 5 Sep 1992 14:49:20 GMT


Thanks to those who have sent solutions.  This is a long post, 
wherein I update the problem list.  Last time I referred to some
problems only by number.  This time, "everything is here". Please
email solutions.  To refresh your memory:

>So here's the deal.  If you send me a solution to one of the problems  
>below, and I like, it I might send you 2 bucks.  Also, I'll post nice  
>solutions for the benefit of your ego!  

5.2.6 Is solved.  It had a typo (change the last 2 to a 1).

5.3.4 is solved.  (It was trivial, <blush>.)

2.2.24 Let a and b be positive integers and let r_j and q_j be the
remainders and quotients of the steps of the Euclidean algorithm as  
defined in "this section".
a)   find the value of \sum_{j=1}^{n} r_j q_j.

b)   find the value of \sum_{j=1}^{n} (r_j)^{2} q_j.

8.6.10 is solved.

8.6.14 Find all Charmicheal numbers of the form 5pq where p and q are  
primes. (I have an ugly solution,  maybe the casework could be cut  
down?)

8.6.18  Show that if (a,n) = 1 then q_n(a+nc)==
q_n(a + \lambda(n) c a^{-1} (mod n).  (We define q_n(a) ==   
(a^{\lambda(n)}-1/n modulo n, with 0 <= q_n(a) < n.)
(\lambda(n) is the minimal universal exponent.)

HERE'S THAT DOUBLE STARRED PROBLEM YOU'VE BEEN ASKING FOR!:
9.4.8  Let the composite positive integer n have prime factorization
n= p_{1}^{a_1}...p_{m}^{a_m}, where p_j = 1+2^{k_j}q_{j} for j = 1, 2,  
.. m, where k_1 <= k_2 <= ... <= k_m, and where n=1+2^{k}q.  Show that
n is an Euler pseudoprime to exactly

\delta_n \prod_{j=1}^{m}  gcd((n-1)/2, p_{j}-1)

different bases b, with 1<= b < n , where 

           ( 2     if k_1 = k
	   (
\delta_n = (1/2    if k_j < k and a_j is odd for some j
           (
	   ( 1     otherwise.
	   
(An Euler pseudoprime to the base b in an odd composite which satisfies

b^{(n-1)/2} == (b/n)  (mod n)  

(b/n) is the Jacobi symbol. 

Whew!  That's probably a result from someones paper.  A reference would 
be sufficient for my needs.

10.4.18 Is solved.  It should have read "D = (ta_k +1)^2 + 
2ta_{k-1} +1".

A PREAMBLE:
The greatest common divisor of two integers can be found using only 
subtractions, parity checks, and shifts of binary expansions, without
using any divisions.  The algorithm proceeds recursively using the
following reduction:

        (  a          if a=b
	(
	( 2(a/2,b/2)  if a and b are even
(a,b) = (
        ( (a/2,b)     if a is even and b is odd
	(
	( (a-b,b)     if a and b are odd and a>b.

Reverse the roles of a and b when necessary.

2.2.12  Show that to find (a,b) this algorithm uses the subtraction  
step in the reduction no more than 1 + [log_{2} ( max(a,b) )] times.

ANOTHER PREAMBLE:
Briefly, we want to consider the "least-remainder algorithm". It is 
analogous to the Euclidean algorithm, but each remainder is chosen
to have the smallest absolute value instead of the smallest nonnegative 
value.  Let r_0 = a and r_1 = b.  Then we have

r_0 = r_1 q_1 + e_2 r_2,       -r_1/2 < e_2 r_2 <= r_1/2
       .
       .
       .
r_{n-2} = r_{n-1} q_{n-1} + e_n r_n,     -r_{n-1}/2 < e_n r_n <=  
r_{n-1}/2
r_{n-1} = r_n q_n

and (a,b) = r_n.  Note that r_j is always positive; we let e_j = +-1 be  
the sign.

2.2.16 (double starred!) Show that the least-remainder algorithm is  
always faster or as fast as the Euclidean algorithm. (Hint:  First show  
that if a and b are positive integers with 2b<a, than the least  
remainder algorithm can find (a,b) in no more steps than it uses to  
find (a, a-b).)

2.2.18  Show that the number of divisions needed to find the gcd of two 
positive integers using the least remainder algorithm is less than
8/3 times the number of digits in the smaller of the two numbers, plus  
4/3.

YET ANOTHER PREAMBLE:

The game of Euclid: Two players begin with a pair of positive integers  
and take turns making moves of the following type.  A player can move  
from the pair {x,y}, with x>=y, to any of the pairs {x-ty,y}, where t  
is a positive integer and x-ty >=0.  A winning move consists of moving  
to a pair with one element equal to 0.

For reference, 2.2.21 (which is solved) states: Every sequence of moves
starting at {a,b}, must end with {0,(a,b)}.

2.2.22  Show that ina game beginning with the pair {a,b}, the first  
player may play a winning strategy if a=b or if  a > b(1 + \sqrt{5})/2;  
otherwise, the second player may play a winning strategy.  (Hint:   
First show that if y<x<=y(1 + \sqrt{5})/2 then there is a unique move  
from {x,y} that goes to a pair {z,y} with y>z(1 + \sqrt{5})/2.)

In the next problem, part (a) is solved but part (b) is stubborn.  It's 
not a starred problem, so I'm starting to suspect a typo...

5.2.11.a (Solved) Show that if n is a pseudoprime to the base a but not
a pseudoprime to the base b, where (a,n)=(b,n)=1, then n is not a 
pseudoprime to the base ab.

5.2.11.b Show that if there is an integer b with (b,n)=1 such that n is
not a pseudoprime to the base b, then n is a pseudoprime to <= \phi(n)
different bases a, with 1<=a<n.  (Hint: Show that the sets a_1, a_2,  
.., a_r, and ba_1, ba_2,...,ba_r have no common elements, where a_1,  
a_2, ..., a_r, are the bases less than n to which n is a pseudoprime.)

8.6.16 (Should be easy if one knows all the notation and terminology)  
Show that the deciphering exponent d for an RSA cipher with enciphering  
key (e,n) can be taken to be an inverse of e mod \lambda(n) (minimal  
universal exponent).  (n = pq is the modulus, and e in the enciphering  
exponent.)

THE NEXT TWO PROBLEMS ARE FROM THE "PSEUDO-RANDOM NUMBER" SECTION

8.7.6 Show that every linear congruential pseudo-random number  
generator can be simply expressed in terms of a linear congruential  
generator with increment c=1 and seed 0, by showing that the terms  
generated by the linear congruential generator x_{n+1} == ax_{n} + c  
(mod m), with seed x_0, can be expressed as x_n == b y_{n} + x_0 (mod  
m), where b == (a-1)x_0 + c (mod m), y_0 = 0 and y_{n+1} == ay_n +1  
(mod m).

8.7.8 Show that the maximal possible period length for a pure  
multiplicative generator of the form x_{n+1} == ax_n (mod 2^e), e>=3,  
is 2^{e-2}.  Show that this is obtained when a == +-3 (mod 8).

Bart Goddard
goddard@nextwork.rose-hulman.edu
Newsgroups: sci.math,comp.graphics,comp.theory.cell-automata,alt.fractals