Conference rusure::math

    There was a generalization of Fermat's Last Theorem that held that
    
          n     n                 n
    (1)  a  +  b              =  x 	only for n <= 2;
    
          n     n     n           n
    (2)  a  +  b  +  c        =  x	only for n <= 3;
    
          n     n     n     n     n
    (3)  a  +  b  +  c  +  d  =  x	only for n <= 4, etc.
    
    However this was shown to be false for case (3) above...there is a set
    of 4 numbers whose 5th power adds up to an integral 5th power.  I have
    not heard of a counterexample to (2), so if you've got some spare CPU
    time and a clever algorithm, you can make history.
    
      John

     (2) What about numbers that can be expressed as the sum of
     two squares in two distinct ways?
     
     50 = 25 + 25 = 49 + 1 is the least such integer.  Unless you
     allow 0 to be one of the squares, when it is 25 = 25 + 0 =
     16 + 9.
     
     For powers higher than squares, it won't help to allow 0 as
     one of the powers; but the proof is too long to fit in this
     reply.
     
     Dan

    (2)  What about numbers that can be expressed as the sum of two
    squares in two distinct ways?
    
    It may be of interest to note that a number can be expressed as the
    *difference* of two squares in two different ways only if it is
    composite, and in fact those squares identify the factors. This
    can be used to factor large numbers. Let n = a^2-b^2 = (a-b)(a+b).
    If a-b <> 1 you need look no further; otherwise you need to find
    the other difference. Nobody said it was easy!

    Let k be an integer >1 and n=k^2+k+1. Now
    n^2-(n-2)^2 = 4n-4 = 4(n-1) = 4k^2+4k = (2k+1)^2-1
    
    so n^2 + 1 = (2k+1)^2 + (n-2)^2.
    k	n	sum
    2	7	49+1=25+25
    3	13	169+1=49+121
    4	21	441+1=81+361
    etc.

(2)  What about numbers that can be expressed as the sum of two squares
     in two distinct ways?

Beiler's "Recreations in the Theory of Numbers" has a chapter entirely
devoted to squares. One of the formulae is:

	(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2
			   = (ac-bd)^2 + (ad+bc)^2

so the product of the sum of two squares by another such product can always be
composed as the sum of two squares in two different ways.

There's a lot more there. One exercise is to write as the sum of two 
squares (in 4 different ways) the number factored as 
	2^7*3^4*5*7^2*13^3.

Have fun!

>There's a lot more there. One exercise is to write as the sum of two
>squares (in 4 different ways) the number factored as 
>	2^7*3^4*5*7^2*13^3.

	Yeesh!  Why so large a number?  The number 801125, for example,
	can be written as the sum of two squares in 16 distinct ways!

> One of the formulae is:
>	(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2
>			   = (ac-bd)^2 + (ad+bc)^2

Interesting!  This seems to be a general formula for generating numbers that
can be written as the sum of two squares in two different ways (for c <> d,
and none of a, b, c, or d = 0).  Is it?

     re .5
     
>>   There's a lot more there. One exercise is to write as the sum of two 
>>   squares (in 4 different ways) the number factored as 
>>   	     2^7*3^4*5*7^2*13^3.
     
     2^7 * 3^4 * 5 * 7^2 * 13^3 = 5580731520
          =  9576^2 + 74088^2
          = 19656^2 + 72072^2
          = 36792^2 + 65016^2
          = 45864^2 + 58968^2
     
     Dan

Here are the two smallest numbers that can be written as the sum of two
fourth powers in two distinct ways.

	                4     4      4      4
	 635318657 = 158  + 59  = 133  + 134

	                4      4      4    4
	3262811042 = 227  + 157  = 239  + 7

I've tried this for fifth powers, but with no success.  Suggestions, anyone?

     re .9
     
>>     Suggestions, anyone?
     
     Keep looking. :-)
     
     Dan

     My search found no examples of
     
           5    5    5    5
          x  + y  = z  + w
     
     with {x,y} ~= {z,w} and all four variables positive integers
     in {1, ..., 1000}.
     
     Dan

Then there's

70^3+560^3 = 198^3+552^3 = 315^3+525^3 = 175959000, probably the smallest 
sum of two cubes in three different ways. That's also from Beiler.

     1729 is also the third Carmichael number.
     
     Dan

    What's the second?

     1105.

     Dan

     The most amazing coincidence happenned today.  I used enotes
     to extract the unseen notes from my DECwindows related conferences.
     I read all but the BULOVA::DECWINDOWS ones, deleted the rest ...
     and that left the file with 1729 lines!

     Anyway, about those Carmichael numbers.  By Fermat's little theorem,

           p-1
          a     = 1 mod p       p prime, a /= 0 mod p

     (sometimes stated as a^p = a mod p for p prime).  So a quick test to
     see if some n is prime is to pick a random a and check whether
     a^(n-1) = 1 mod n.  If not, n is composite.

     Now if you select an a such that a and n are not relatively prime,
     then you are very fortunate; gcd(a,n) will be a factor of n.  But
     that's not too likely.
                           n-1
     However, for some n, a    = 1 mod n for every a that is relatively
     prime to n.  These n are called Carmichael numbers.  The first (well,
     in the usual ordering) few are  561, 1105, 1729, 2465, 2821.

     So 1729 shows up again.

     Dan

    Are there any prime Carmichael numbers?
    
    It seems ironic that only composite numbers pass this test for
    primality with such ease.

     Primes numbers will always pass tests of primality.  If you care
     about these things you are probably only concerned about the times
     when composite numbers "slip through" probabilistic primality tests.

     I think Carmichael numbers are mentioned a bit in Knuth; a list
     (factored) of the first many of them shows numbers with three or
     four prime factors.  This seems right; perhaps a number needs
     at least three factors in order to be a Carmichael number.

     Dan

     I have a list of the first 666 Carmichael numbers (in the
     standard ordering of the nonnegative integers, it goes
     without saying) and a list of the factorizations of the
     first 43 Carmichael numbers (in the same ordering).
     
     Dan

    It may be of interest to note that Lagrange proved that every
    positive integer can be expressed as the sum of four squares,
    or the sum of five cubes, or the sum of six 4th powers and so
    on. In certain cases they can be expressed in less than the
    default quantity, in other words some terms can be zero, so
    for example...
    
    		11 = 3^2 + 1^2 + 1^2 + 0^2
    
    

    I have a short LISP routine to test an integer using Fermat's
    congruence. It passes primes and Carmichael numbers and fails
    everything else.
    
    (DEFUN PRI  (N)
     (COND ((EQ (MOD (- (EXPT 2 (- N 1)) 1) N) 0) 'PASS)
       (T 'FAIL)))
    
    This is rather a nice routine to use when testing the limits
    of a LISP system. Numbers greater than nine digits tend to
    make even a Cray sit down. This is because the intermediate
    value 2^N is so enormous.
    
    I have thought of a way of doing it which does not involve
    generating a gigantic intermediate value. Looking at the
    congruence written in the form n^(p-1)-1 = 0(mod p) and using
    2 as n, the left hand side expressed in binary consists of
    a continuous string of binary ones (p-1) bits long. Also,
    division of this number by p is not necessary if the remainder
    is all that is desired and this can be generated some other
    way. 
     So, munch away the binary string from the top using continuous
    subtraction, left-shifting what remains each time and feeding
    ones in at the right hand end until (p-1) bits have been fed.
    Then check what's left. If it's zero, the number passes and if
    not it fails.
     I intend to try writing this in C sometime, but if anybody
    would like to try it, be my guest!
    
     There is another theorem to identify primes (with no others
    slipping through) called Wilson's Theorem.
    
          (p-1)! = -1(mod p)
    
     This would make a nice little LISP program, with recursion
    of course, and would generate even more monstruous intermediate
    values than Fermat's congruence.
    

     re .22

     You should check your references about Lagrange's theorem.  It is not
     true that every integer can be expressed as the sum of six fourth powers,
     for example.  Consider, the fourth powers are positive, 0^4 = 0, 1^4 = 1,
     and 2^4 = 16.  So how do you express 15 as a sum of six fourth powers?
     Five cubes is also not enough if you are restricted to cubes of
     nonnegative integers.

     It is true that for every positive integer k there is a positive integer n
     such that every nonnegative integer can be expressed as a sum of n
     terms each of which is the k-th power of a nonnegative integer.  It's just
     that the numbers you quoted as "n" in .22 are not high enough for the
     given "k".

     Finally, yes it was Langrange who proved that n = 4 is sufficient for
     k = 2.  I don't know that he was the one who proved there existed an
     n for k = 3 or k = 4, though.

     re .23

     The way you rewrite the first test you are taking p-1 steps to get an
     answer.  Likewise, a straightforward computation of (p-1)! mod p would
     take p-1 steps.  But you can compute n^(p-1) mod p in about log  p steps
     instead.  This gives a much faster algorithm.                   2

     Dan

    Re .23:
    
>    (DEFUN PRI  (N)
>     (COND ((EQ (MOD (- (EXPT 2 (- N 1)) 1) N) 0) 'PASS)
>       (T 'FAIL)))
    
    Not being LISP literate, could someone provide a pseudocode translation
    of this?
    
    I can geuss, but I'd rather be sure.
    
    --  Barry

    On Lagrange's theorem, I stand corrected. I was quoting from memory.
    The point of interest was that numbers that are sums of two squares
    in two different ways are special cases of Lagrange decomposition,
    where there happen to be two cases where there are two zeroes. Numbers
    can often be expressed in more than one way as the sum of four
    squares. Try 100 for example.
    
    The procedure I was suggesting for Fermat testing would indeed be
    slow, but it would enable computation to be done on large numbers
    without running out of memory.
    
    
    The LISP routine might be expressed in more conventional type
    programming as something like...
    
    IF MOD(2^(P-1)-1,P)=0 THEN PRINT "PASS" ELSE PRINT "FAIL"

    Further to notes .25 & .26, implimentation of this routine in a
    language other than LISP is likely to have less spectacular
    consequences. This is because most computer languages utilise
    the machine's floating point hardware and calculations are bounded
    size of the registers available. LISP is unique in that it manipulates
    numbers as character strings, so that the maximum digit-length that
    can be generated in bounded by the amount of memory available.
    

>    size of the registers available. LISP is unique in that it manipulates
>    numbers as character strings, so that the maximum digit-length that
    
    I'm not sure the adjective "unique" can be correctly applied here.
    
    In any event, what you really want to do is reduce mod p for every
    iteration, not just after raising 2^N.  That has the desirable property
    of making the exponentiation work much faster, and is less likely to
    be limited by page file space.  IXP$POWXN (q.v.) works precisely this way.
    
      John

RE: .27, .28
    
    Just to clear up any confusion --
    
    I don't know of any "real", modern implementation of LISP which represents
    numbers as character strings.  The only "modern" language I know of
    which does approximately that (as an option) is COBOL.  Most
    implementations of LISP (including all implementations of Common LISP)
    contain the necessary data structures to transparently represent large
    magnitude integers using multiprecision representations.  Other
    languages widely available within DEC which do the same are APL, MAPLE,
    and Trellis (nee Trellis/Owl and Owl).  There are probably more.
    
    					Topher

     re .23

>>    I have a short LISP routine to test an integer using Fermat's
>>    congruence. It passes primes and Carmichael numbers and fails
>>    everything else.

     Composite numbers that pass the "test" of Fermat's theorem (no,
     not his "last" theorem), i.e., composite n with 2^(n-1) = 1 mod n,
     are called pseudoprimes.  Carmichael numbers are pseudoprimes,
     but the reverse isn't true.  To be a Carmichael number, the composite
     number n must satisy a^(n-1) = 1 mod n for all a relatively prime
     to n; to be a pseudoprime the compiste number n only needs to satify
     that test for a = 2.

     The least Carmichael number was given earlier.  What's the smallest
     pseudoprime?

     Dan

    SOME COMMENTS....
    
    .28   Yes, I shouldn't have said 'unique'. In fact VAX BASIC has
    a 'string arithmetic' feature, though it must be explicitly called.
    
    .29   I don't claim to be an expert on LISP, I just play about
    with it during lunch breaks. As far as I know VAX LISP uses the
    facilities of the arithmetic unit whenever the numbers are small
    enough to fit. The nice thing about LISP is that you can create
    any type of arithmetic in it, starting from CAR and CDR if you
    have to. Recently I discovered that the EXPT function uses a
    register ('fixnum') to hold the exponent, so I wrote my own
    exponent function that didn't.
    
    Dan, I wasn't aware that there were non-primes other than
    Carmichael numbers that slip through the Fermat test. I seem
    to recall vaguely reading about this somewhere. (I don't
    suppose you want to know about my troubles, but my entire
    collection of mathematical books was looted recently when
    my house was turned over by burglars). I must admit I have
    no idea how to set about finding these psuedo-primes....no
    doubt Gauss or somebody has shown how to do it.
    
    Well, this has all been very interesting.....thanks for the
    contributions, everybody!
    

     Re .30:
    
>     Carmichael numbers are pseudoprimes,
>     but the reverse isn't true.  

    Interesting.  This implies that Carmichael numbers must be odd.
    Is this known to be true?
    
>     The least Carmichael number was given earlier.  What's the smallest
>     pseudoprime?

    The first few Pseudoprimes are:
    
    	 341
    	 561
    	 645
    	1105
    	1387
    	1729
    	1905

    --  Barry

	Below is a FORTRAN-77 standard conforming function to test for
    Pseudoprimality.  Well, its nearly conforming, you would have to
    take out all of the TABs and uppercase everything.  But most modern
    FORTRAN compilers will accept this relaxed source form.
    
    I could also provide, on request, a similar function for general
    Carmicheal tests (ie. using any base, not just 2), and either of
    these in C (which I am still learning).
    
    --  Barry
    

C---------------------------------- cut here ---------------------------


	INTEGER FUNCTION Psprim (P)
	
C 
C FUNCTIONAL DESCRIPTION:	
C 
C    Uses Fermats test for primality to determine if the argument P 
C    is a Psuedoprime (or maybe even a real prime).
C    The algorithim used is based in part on an idea by J.Crean (Digital).
C    This function should be valid for values of P up to and including
C    6 digits (2**20).  Larger values will return incorrect results.
C
C   --  B.Young, March 9, 1989
C 
C FUNCTION VALUE:
C 
C    Returns a 1 if true, and a 0 if false.
C 
	INTEGER P, Iterat, Leftov, Residu, Quotnt, I
	 
	Iterat  =  (P-1) / 10

	Leftov  =  (P-1) - (Iterat*10)

	Residu  =  2**Leftov

	Quotnt  =  Residu / P
	Residu  =  Residu - (Quotnt*P)
	DO 100 I=1, Iterat
	    Residu  =  Residu * (2**10)
	    Quotnt  =  Residu / P
	    Residu  =  Residu - (Quotnt*P)
100	CONTINUE

	Psprim  =  0
	IF (Residu.eq.1)  Psprim  =  1

	END

    My performance tests on the routine in .33 indicate that, assuming
    an 8250 to be a 1.5 mips machine, then 
    
    	Number of Instructions  =  2.4 * P

    where P is the 'pseudoprime' to be tested.  I could alter these
    routines to handle much larger values of P, but the result would
    probably be much slower (about 6x).  By using double precision floating
    point values instead of longword integers, it could support values
    of P up to about 10 digits (2**34).  By my estimates this would
    be the equivilant of at least a 10**11 instruction calculation that
    would take at least 6 hours on an 8810 class CPU.
    
    --  Barry

     Barry,
     
     You should compute the exponentials like this.  Suppose you
     have positive integers base, exp, and m and you want to compute:
     
                            exp
               "answer" = base      (modulo m)
     
     Use variables A, B, and E and initialize them to
     
               A = 1     B = base     E = exponent
     
     There will be a loop here with a loop invariant of
     
               "answer" = A * (B ** E) (modulo m)
     
     There is no variable "answer", that is the "mythical" :-)
     answer that you are trying to compute, while A, B, E, and
     base, exp, and m are variables, the latter three being
     inputs to the program.
     
     The invariant is true for the starting values of A, B, and
     E.  Each pass through the loop will maintain the invariant
     while reducing E roughly in half.  Eventually you exit the
     loop with E = 0; at this point, B ** E = 1 and so by the
     loop invariant, answer = A (modulo m).
     
     The loop is just
     
               If E is even: let B = B * B (modulo m)
                             let E = E / 2
     
               If E is odd:  let A = A * B (modulo m)
                             let B = B * B (modulo m)
                             let E = [E / 2] ! i.e. divide with truncate
     
     The order of the assignments to A and B is important in the
     case of odd E.
     
     At each point, the numbers A and B can be stored modulo m,
     so their values are in 0, ..., m-1.  However, the
     intermediate values B * B or A * B before reduction modulo m
     can be as large as (m-1)**2.
     
     The advantage here is that the number of times through the
     loop is proportional to the number of bits in E, as opposed
     to being proportional to E itself.  So this approach is much
     faster.
     
     Dan

    I had this laying around - it may be of some interest.

    - Jim


	.TITLE	POWER
	.IDENT	/JR/

NARG =	0.
A =	4.
M =	8.
N =	12.
P =	16.

	.PSECT	$CODE,PIC,CON,REL,LCL,SHR,EXE,RD,NOWRT,LONG
;+
; POWER(A, M, N, P) - Raise an integer to a power mod another integer
;
; P = A**M MOD N
;-
	.ENTRY	POWER,^M<IV,R2,R3,R4,R5>

	MOVL	#1,R2			; R2 = P = 1
	MOVL	@N(AP),R3		; R3 = N
	MOVL	@M(AP),R4		; R4 = K = M
	MOVL	@A(AP),R5		; R5 = T = A
100$:
	BLBC	R4,200$			; Br if K even
	EMUL	R2,R5,#0,R0		; R0,R1 = P*T
	EDIV	R3,R0,R0,R2		; P = P*T MOD N
200$:
	EMUL	R5,R5,#0,R0		; R0,R1 = T*T
	EDIV	R3,R0,R0,R5		; T = T**2 MOD N	
	ASHL	#-1,R4,R4		; K = K/2
	BNEQ	100$			; Go again if K not reduced to 0

	MOVL	R2,@P(AP)		; Store P

	RET

	.END

    Re .36:
    
    (embarassed) Right you are Dan.  I have even developed Binary encoded
    power series algorithims like this before, I don't know where my
    head is these days.  I could recode this routine, except that now
    its so much faster that I do not have a good excuse for not
    implementing multi-precision arithmetic.  Hmm, what are the highest
    known primes these days?
    
    Re .37:
    
    Sorry about that.  I sometimes glaze over when reading long proofs
    (my downfall in college).  I did some back-of-the-napkin figuring
    last night and came up with some tentative results for Pseudoprimes
    and Carmicheal numbers:
    
    	1)  Pseudoprimes must be odd (no suprise here).
    
    	2)  Psprimes must also be the product of distinct primes.
    				 N
    	3)  Numbers of the form 2 - 1 that pass the Psprime test, 
    	appear to be prime (ie. not pseudoprime).
    
    	4)  In fact all numbers of the form 4N+3 that pass the Psprime
    	test appear to be prime.
    
    I am about 90% sure of (3) and about 80% sure of (4).  I am about
    99% sure of both (3) and (4) for numbers that pass the Carmicheal
    tests.
    
    Can anybody confirm these?
    
    --  Barry

                     -< not rivetting reading, perhaps... >-

>>     Carmichael numbers are pseudoprimes,
>>     but the reverse isn't true.  
>
>    Interesting.  This implies that Carmichael numbers must be odd.
>    Is this known to be true?

	I proved it in .21

	Perhaps I should summarize what else is proved in that reply:

Let n be Carmichael (and composite !)

	(1) n is a product of *distinct* primes (say there are I of them).

	(2) I is greater than 2

	(3) n is odd

Now suppose further that I is 3, n = pqr

	(4) gcf(p-1,q-1) = gcf(p-1,r-1) = gcf(q-1,r-1) = D say.

	(5) There a finite number of Carmichael numbers with given D.

	(6) A fortiori, there are a finite number of Carmichael numbers with 
I=3, and with a given factor p.


	Incidentally, the group theoretic assertion that I made, is correct,
see the next reply.   Thank you, Dan, for pointing out that I was misquoting
myself!

Andrew

    Sigh.  I am ashamed to admit it, but my grasp of Abstract Algebra
    and Group Theory have faded to the extent that I can no longer follow
    all of the steps and implications in .41.
    
    I do have some questions (and conjectures) which seem to be strongly
    related to the results of .41, so maybe someone can translate for
    me.
    
    Lets take the Psuedoprime 341.  It is equal to (11^1 * 31^1).  Now
    I observed many years ago, and later found confirmation in Number
    Theory texts that for any number N:
    		   e1    e2      en
    	If  N = (P1  * P2  *...Pn  )	where Pk are prime and Ek are
    					integers greater than 0
	            e1-1              e2-1                 en-1
    	Then M = (P1    *(P1-1)) * (P2    *(P2-1)) * ...(Pn    *(Pn-1))
    
    Where M is the number of integers less than N that are relatively
    prime to N.  Further I have observed that the Power series
         i
    	K  mod N		where K is realtively prime to N
    
    Seems to be a cycle of M numbers including all of the numbers less
    than N that are relatively prime to N.  Now N if N is a prime then
    
    	M = N - 1
    
    and consequently tests to see if
         N-1
    	K   = 1  mod N		Where K is relativley prime to N
    
    are a 'good' test of primality.
    
    However, this rule I have observed does not alway seem to be true,
    as in the case of 341:
    
    	341  =  11 * 31
    
    	        10 * 30  = 300  = total numbers relatively prime to
    					N and less than N.
    	 i
    But	2	forms a cycle * 20 * long and consequently

         340
    	2    = 1  mod 341
    
    Can anyone shed some light on this for me?  I have noticed that
    (coinidentally?) GCD( 300, 340 ) = 20, does this have anything to
    do with it?
    
    --  Barry

    Re .39:
    
>>    				 N
>>    	3)  Numbers of the form 2 - 1 that pass the Psprime test, 
>>    	appear to be prime (ie. not pseudoprime).
    
>>    I am about 90% sure of (3) and about 80% sure of (4).  I am about
>>    99% sure of both (3) and (4) for numbers that pass the Carmicheal
>>    tests.
                                                             N
     I don't believe that (3) is true.  Numbers of the form 2  - 1
     where N is composite are themselves composite:  if N = rs
     then 2^N - 1 is divisible by 2^r - 1 and also by 2^s - 1.
                          p
     Numbers of the form 2  - 1 for prime p are called Mersenne
     numbers; those which are prime are Mersenne primes.  I
     believe that the composite Mersenne numbers are all
     pseudoprimes, in contradiction with (3).
     
     Dan

     Re: .42
     
     No, the group of numbers relatively prime to N under
     multiplication modulo N is not generally cyclic.  I believe
     it is only cyclic for N = 2, 4, a power of an odd prime, or
     twice the power of an odd prime.  Furthermore, even when the
     group is cyclic not every element will generate the entire
     group.  Examples follow with N=10 and N=15.
     
     For N=10, the group is {1,3,7,9} under multiplication modulo
     10.  The sequences of powers starting with each element are:
     
          1, 1, 1, 1, ...
          3, 9, 7, 1, ...
          7, 9, 3, 1, ...
          9, 1, 9, 1, ...
                                               2   3
     The group is cyclic, and the sequence K, K , K , ...
     generate the entire group for K=3 and K=7.
     
     For N=15, the group is {1,2,4,7,8,11,13,14} under
     multiplication modulo 15.  The sequences of powers of
     elements are
     
          1, ...              8, 4, 2, 1, ...
          2, 4, 8, 1, ...     11, 1, ...
          4, 1, ...           13, 4, 7, 1, ...
          7, 4, 13, 1, ...    14, 1, ...
     
     This group is not cyclic; no element generates the entire
     group.
     
     Re your example of N = 341 = 11 * 31.  The "order" of the
     element 2 is actually 10 and not 20.  There are as you say
     10 * 30 = 300 elements in the group of relative prime
     residues modulo 341.  Let K be a member of this group.
     Now K^10 = 1 mod 11 because 11 is prime.  Also K^30 = 1 mod 31
     because 31 is prime.  But note that K^30 must also be 1 mod
     11. because it is the cube of K^10 mod 11 which is already
     known to be 1.  There is only one number modulo 341 which is
     both 1 mod 11 and 1 mod 31, and that is 1 mod 341.  So for
     every K relatively prime to 341, K^30 = 1 mod 341.  If K=2,
     then K^10 = 2^10 = 1024 = 3 * 341 + 1 = 1 mod 341, so the
     "order" of 2 is 10.  Since 10 divides N-1 = 340, it will
     also be true that 2^340 = 1 mod 341, because 2^340 =
     (2^10)^34 = 1^34 = 1 mod 341.  So 341 is a pseudoprime. 
     However, there are K with an order of 30, which does not
     divide N-1 = 340; therefore 341 is not a Carmichael number.
     
     Consider instead 561 = 3 * 11 * 17.  It's corresponding
     group has M = 2 * 10 * 16 = 320 elements.  Let K be such an
     element.  Then K^2 = 1 mod 3, K^10 = 1 mod 11, and K^16 = 1
     mod 17.  Now the least common multiple of 2, 10, and 16 is
     80, so K^80 = 1 mod 3, K^80 = 1 mod 11, and K^80 = 1 mod 17.
     The only number modulo 561 that is 1 mod 3, 1 mod 11, and 1
     mod 17 is 1 mod 561, so K^80 = 1 mod 561 for every K
     relatively prime to 561.  But now 80 does divide N-1 = 560,
     and so K^560 = (K^80)^7 = 1^7 = 1 mod 561 for every K that
     is rel. pr. to 561.  Therefore 561 is a Carmichael number.
     
     Dan
      

    Dan:  (Or anyone else)
    
    In note 2.5 you describe the Lucas-Lehmer test for Meserenne(sp?)
    Primes (2^P - 1).  At first glances this appears to be the Pseudoprime
    test, more or less using the approach you mentioned earlier.
    
    Can you confirm this?  And if so does this mean that the Pseudoprime
    test is an absolute for Mersenne numbers?
    
    --  Barry

     The test in 2.5 is this:  Let q be an odd prime and let n be
     the Mersenne number 2^q - 1.  Test n for primality by doing
     the following:
     
          Compute L(0),...,L(q-2) mod n using the recurrence
          L(0) = 4 mod n and L(n+1) = (L(n)^2 - 2) mod n.
          Then n is prime if and only if L(q-2) = 0 mod n.
     
     The pseudoprime test would be to compute 2^(n-1) mod n, and
     if that is not = 1 mod n then n is composite, otherwise it
     may or may not be prime.
     
     Like I said earlier, I believe the composite Mersenne
     numbers are pseudoprimes, which would make that particular
     test useless.  I'll check a book at home tonight on this.
     
     Here is a comparison of the relative time it takes to
     run the two tests.  Computing 2^(n-1) mod n in the manner
     described earlier involves roughly 2log n operations of
                                            2
     multiplying two numbers < n and reducing the product mod n.
     Since n = 2^q - 1, log n is about q, so this is about 2q
                           2
     such operations.  The factor of 2 comes from all of the bits
     but the last in n-1 being 1's.  Compute 2^(n+1) mod n and
     you only use roughly log n i.e., roughly q such operations.
                             2
     
     The L.L. test involves almost q operations of squaring mod
     n, but with an extra subtraction thrown in.  So it is just
     as fast as the pseudoprime test *and* gives a definitive
     yes or no answer, so use it instead for testing Mersenne
     numbers.
     
     Dan

     Re: composite Mersenne numbers and pseudoprimes.
     
     The precise (or should I say correct) statement is this:
     
          If n is odd and satisfies 2^(n-1) = 1 mod n,
          then N = 2^n - 1 is odd and satisfies 2^(N-1) = 1 mod N.
     
     Now, if n is composite then 2^n - 1 is composite.  So if n
     is an odd [composite] pseudoprime then 2^n - 1 is an odd
     [composite] pseudoprime.
     
     But if n is an odd prime, then of course 2^(n-1) = 1 mod n,
     and so N = 2^n - 1 satifies 2^(N-1) = 1 mod N.  So the
     Mersenne number N = 2^n - 1 for odd primes n is either a
     prime itself or, if composite, is a pseudoprime.
     
     However, there are "obviously" composite Mersenne numbers
     2^n - 1, [obviously composite because n is composite] that
     are not pseudoprimes; in these cases if n is odd then it
     isn't a pseudoprime, either.
     
     Finally, here is some more pseudoprime trivia:  every
     composite Fermat number 2^(2^n) + 1 for n >= 0 is a
     pseudoprime; and not all pseudoprimes are odd!  161038
     is a pseudoprime.
     
     Dan

     re: even pseudoprimes
     
     If 2^(n-1) = 1 mod n, then doubling both sides gives
     2^n = 2 mod n, which can also be expressed as n divides
     2^n - 2.  If you define a pseudoprime as a composite n that
     divides 2^n - 2, then 161,038 is a pseudoprime.  However,
     2^161037 is even and so will be even mod 161038, and thus
     not 1 mod 161038.  (In fact it must be 80520, so that
     doubling it gives 2 mod 161038.)
     
     So you need the n divides 2^n - 2 definition to consider
     even pseudoprimes.
     
     If you think of pseudoprimes as "possible primes" then you
     don't really care about the even ones.  However, Fermat's
     result that for primes p, a^(p-1) = 1 mod p contains the
     restriction that a is not zero mod p.  So the result is
     often stated as "for primes p, a^p = a mod p, for all
     integral a."  Pseudoprimes then are composite numbers that
     also have "this property" for a=2, and how you state
     Fermat's property about primes determines which definition
     of pseudoprime you get.  
     
     Dan

re .38 (computing P = A**M MOD N)

	The algorithm is in error if M <= 1.

     re .50
     
>>	re .38 (computing P = A**M MOD N)
>>
>>		The algorithm is in error if M <= 1.
     
     If M <= 1, then M = 0 or M = 1, because we are only dealing
     with nonnegative integers.  For those cases, you already
     know the answer, so you don't need to call the routine. :-)
     
     Dan

    On a recent trip I ended up in hotel room 658.  What an ugly number.

        Oh, I don't know about that.  If you compute gcd(n, [n^pi])
        for all of the nonnegative integers less than 1,000, then
        the largest result that appears more than once first
        appears at, you guessed it, n = 658.
        
        Dan

In spite of the apparent contradiction, I think you've finally discovered 
the first truly non-interesting number.  ;-)

Lynn 

Our Number of Honor is also the sum of FOUR cubes:

	1729 = 1^3+6^3+8^3+10^3

and, of course, both 
	9^3 = 729 
and
	12^3 = 1728 
are the sum of three cubes.

Lynn Yarbrough