TEST 2.  Tue, Apr 17, 1998
Math 365. Number Theory.  Spring 1998.

1. List all primes   p<100000   such that,
    for  any  odd  positive  integers  n   and
    any  integer  m,    the equation
              x^n=m  (mod p)
    has  a  solution  x   in   Z.
 Solution.  The condition is equivalent to the requirement
     that  (n,p-1)=1,  for all odd  n.  Thus  p-1   must be
     a power of   2,  i.e.   p  is a  Phermat prime.
LIST:  2, 3, 5, 17, 257,  65537.

2.  (a)  Show that   U(125)   is cyclic  (i.e.,  that  
            there is    x   in   U(125)   whose
            order is   phi(125);   equivalently,
            whose set of powers  coincides with
            the whole  U(125) ).
Solution. 
»ordermod(2,125)
ans =
   100
»phi(125)
ans =
   100
»% The equality proves that  U(125)  is cyclic.
      (b) Find  max(order(x)),  over  x  in   U(97*101).
             Is   U(97*101)   cyclic?  Prove or disprove.
Solution. There is an x  in  U(97*101)   such that
    the orders  of  x  in  U(97)  and  U(101)  are
    96  and  100,  respectively 
    (Chinese Remainder Thm.).  Then the order of  x
    in  U(9797)   is the   lcm(96,100)=2400.
    On the other hand,  it is clear that
        a^2400=1  mod (9797),  for all  a  in  U(9797)
    because the equality holds  mod both  97  and  101
    since  96|2400   and  also  100 |  2400.
    Remark.  The first part of the argument can be replaced
       by the short calculation:
 »ordermod(5,9797)
ans =
        2400

3.  Find the density of the set of positive 
      integers   n    whose decimal representation
      does not include digit    6.

SOLUTION.  Denote by   M(k)   the set of integers
   for which each of the last  k  decimal digits is
   different from   6.  It is clear that  M(k)   is
   a   10^k - periodic set  with  d(M(k))=(9/10)^k.
   The set in the question  M  belongs to each
    M(k),  and  hence  upper density of  M 
   is  less or equal than (9/10)^k,  for all  k.
   Thus it must be  0,  and therefore  d(M)=0.

4.  Find  (without computer !)  the density  of the set   
     K  of positive odd  integers   n    for which
              (5*13*17/n)=1
      (Jacobi symbols  on  left.)
      REMARK.  You are allowed to check your result
         using   MATLAB.
ANSWER.  192/1105.
SOLUTION.  In class.
4/5*12/13*8/17*1/2

5.  Denote by   M(p)   the set of positive 
       integers   x    such that
              (x^2) * (2^x) = 1   (mod  p).
       (a)  Find  d(M(7));  
       (b)  Prove that    M(p)   is not empty for any 
              prime  p>2.
SOLUTION OF (a). M(7)  is clearly   42-periodic.  Computing the 
number of sols 
between  1  and  42  (including).  
»x=1:42;
»sum(mod(x.^2.*2.^x,7)==1)
ans =
    12
One can, of course, list all these sols:
»find(mod(x.^2.*2.^x,7)==1)
ans =
     6    11    15    16    17    19    
     27    32    36    37    38    40

Thus the density is   12/42=2/7.
SOLUTION OF (b).
It is enough to show that   the system
        x^2  = 1   (mod  p)
        2^x = 1   (mod  p)
has a solution.  It is enough to take  x
such that   x=1  (mod p)   and   x=0 (mod p-1)
which is possible since  (p,p-1)=1
(Chinese Remainder Thm).
Alternatively:  Take  x=(p-1)^2.
   or  just x=p-1  
   (as pointed out by one of the students).

6.  Prove or disprove:  the set of solutions to
          x^5 * dist(x^2*sqrt(2), Z)  < 111
     (in positive integers  x)   is finite.

    dist(x,Z)  =  <x>_c    (according to the class notation)
    denotes  the distance from  x   to the closest integer.  

True.  We know that   n*dist(n^2*sqrt(2),Z)>1/3, for all  n 
(proved in class).  Thus, taking  n=x^2,  we get
    x^5 * dist(x^2*sqrt(2), Z) >x^3 /3
which is always  >111   for  x>6.

REMARK.  Defective version of ordermod.m  has been replaced
                 by the correct one.
Each problem  -  25  pts.
GOOD  LUCK.