From: goddard@NeXTwork.Rose-Hulman.Edu (Bart Goddard)
Newsgroups: sci.math
Subject: Number Theory Problems....
Date: 31 Aug 92 15:37:27 GMT
Organization: Rose-Hulman Institute of Technology


I was right!  I awoke this morning after 13 hours of sleep, feeling  
refreshed and nearly recovered from my cold, and, by gum, I do regret  
posting a tirade.  There should be a law about posting under the  
influence of Nyquil.  Anyway, as I said earlier, I have a few more of  
these problems which I have been too fuzzy-headed to do.  Some are  
hard, and I don't see the trick.  Some are easy and I haven't gotten  
around to them yet.  They are book problems.  I am not doing them for a  
grade.  I am doing them for money.  But not very much money.  So, if  
you solve one of these problems, you would be helping me earn money.   
This rings a bit unethical, perhaps, but I don't have qualms about  
running across the hall and asking colleages for help, so maybe this  
isn't much different...?  In any case, I usually treat helpful  
colleages to lunch, so I guess I could mail helpful netters some  
McDonald gift certificates, but I think I might just send cash instead.  

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!  Further, like I said above, I'm  
in a much cheerier mood, and I don't really care if you flame me now.   
ZIPPEDY-DO-DAH!! ZIPPEDY-AY!!  

I would like to add that this project was a hugh mistake on my part.   
It has swallowed up every second of free time for the last 15 months of  
my life, and the money isn't really too much, and I just want the darn  
thing finished so I can get on with my life.  Hence, I beg for your  
help here, to do the last few problems.

Bart Goddard  goddard@nextwork.rose-hulman.edu

The book is Ken Rosen's Elementary Number Theory and Applications,
(Addison-Wesley) 3rd Ed.

Problems:  (== means congruent to)

5.2.6 Show that if n= (a^{2p}-1)/(a^{2} - 1) where a in an integer,
a>1, and p ia an odd prime not dividing a(a^{2}-1), then n is a
pseudoprime to the base a. (i.e. a^n == a (mod n).)
Hint:  To establish that a^{n-1} ==1 (mod n), show that 2p | (n-1)
and demonstrate that a^{2p} == 2 (mod n).

5.3.4 Show that if a and m are positive integers with (a,m)=1 and
(a-1,m) =1, then 1+a+a^{2}+ ... + a^{\phi(m)-1} ==0 (mod n).

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 (\lambda(n) is the least universal exponent of n) Show that if c
is a positive integer >1, then the integers 1^c, 2^c,..., (m-1)^c form  
a complete system of residues modulo m if and only if m is square-free  
and (c, \lambda(m)) = 1.

8.6.14 Find all Charmicheal numbers of the form 5pq where p and q are  
primes.

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.)

9.4.8 (which was 9.4.8 in the second edition) is too complicated for me  
to type (today). It's a double starred problem, and a reference would  
suffice.

10.4.18 Let k be a positive integer.  Show that there are infinitely  
many positive integers D, such that the simple continued fraction  
expansion of \sqrt{D} has a period of length k.  (hint:  Let a_1 = 2
a_2 = 5 and a_k = 2a_{k-1} + a_{k-2}. Show that if D = (ta_k +1)^2 + 
2a_{k-1} +1, where t is a nonnegative integer, then \sqrt{D} has a  
period of length k+1.)

There are some others, which I list by problem # only, since they a  
parts of a series of problems, and the definitions and notations are
hard to extract in a consise form.  
2.2.12
2.2.16
2.2.18
2.2.22
5.2.11(b)
5.3.10
8.6.16
8.7.6
8.7.8
Enjoy!