From: catalyst-remailer@netcom.com
Date: Mon, 11 Apr 94 15:26:10 PDT
To: cypherpunks@toad.com
Subject: number theorynumber theory
Message-ID: <199404112227.PAA07925@mail2.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

All right, a number theory discussion!

>The integer N is prime if:
>   2^N - 2
>  ---------
>      N              is an integer.

Well, this is false.

The above formula is derived from Fermat's Little Theorem, or Euler's
Generalization of Fermat's Little Theorem.

a^(n-1) = 1 mod n, n prime, gcd(a,n) = 1
==> a^n = n mod n
    a^n - n = kn, for k some integer
    (a^n - n)/n = k, for k some integer

now sub in a = 2.

However, the converse of this is not true (n isn't necessarily prime
if it satifies the formula).  Composities that satisfy this are called
pseudoprimes.  For example, for a = 2, n = 341 satisfies the relation,
so 341 is a pseudoprime base 2.

Now it works "most" of the time, and in fact one method of testing
large integers for primality is to choose a whole bunch of a's and
plug in n.  If a^(n-1) mod n != 1, the number is composite and can be
rejected.  But, if a^(n-1) mod n == 1, you can only be 50% sure n is
prime.  (Roughly speaking; Phil Karn notes that the PGP docs indicate
a 50%, I've seen proofs that this pseudoprime test fails 50% of the
time, etc.  But these are upper bounds; the real percentage seems much
lower and I haven't seen a tighter bound on it).

There is a "strong psuedoprime" test, in which failure occurs for at
least 25% of integers in the range, thus the probability that a
composite will pass is at most 25%.

Even better is Lucas' test, but it runs a bit slow.

However, you can be unlucky and pick a Carmichael number, which will
pass the pseudoprime test for all bases relatively prime to n (for all
a such that gcd(a,n) = 1).  Ray Cromwell advises to choose n = 561,
the smallest Carmichael number (an excellent choice!)  Carmichael
numbers exist, they are relatively rare, formulas exists for
generating some of them...

Eric Hughes mentions that 1729 is the next Carmichael number... not
quite true.  1105 is the next Carmichael number.  (But congrats Eric
for even remembering the third one!) ;)

Now, some other topics:

> For any number n which is prime, (2^n)-1 is also prime (Mersenne's
> theorem).

Hm... some confusion here.  A Mersenne prime is of this form (2^n) - 1
where n is prime, but not all number this formula generates are
primes.  Mersenne primes are related to perfect numbers.

An example of a composite of this form:

for n = 11, 2^11 - 1 = 2047 = 23 * 89

> For any number n (2^(2^n))+1 is prime. (I might have that wrong, I
> don't remember exactly)

Well, no.  These number are Fermat numbers, and while the first 5 (n=0
to n=4) but Euler showed that the Fermat number for n=5 is composite.

As an aside, Fermat numbers satisfy the pseudoprime test.

> For any number n, if the square root of (n!)+1 is an integer, it is
> also prime.  (This is interesting, but rather useless in practice)

A couple of issues here:

I think you may be remembering a different theorem, a consequence of
Wilson's theorem.

Wilson's theorem says: 

  for any prime p, (p-1)! = -1 mod p

The theorem I think you are referring to is:
  if P is the product of the remainders relatively prime to m, then
  P = +/- 1 mod m; +/- = plus or minus

The congruence is +1 except in three cases:
  1) m = 4
  2) m = p^b (m is a power of an odd prime)
  3) m = 2p^b (m is twice the power of an odd prime)

I'm still trying to either prove or disprove your claim!

Two followups relating the the original formula posted:

> For any number a, 1<a<=n, n! mod a == 0; therefore, n!+1 mod a == 1.
> n!+1 is prime.  Prime numbers don't have integral square roots.

Good analysis, except for the "n! + 1 is prime" part.  The only thing
you can say is n!+1 has no factors <= n.

For example, n = 4, n!+1 = 25 = 5 * 5.

> Well, it was quoted from memory, so it's possible that I made an
> error, but it seems to work as stated...
> For example :
> (4!+1)^(1/2)=5
> (5!+1)^(1/2)=11
> (7!+1)^(1/2)=71
> I can't find a value which produces a result that is a non-prime
> integer.  (Of course that doesn't prove that there isn't one.)

Still working on this... ;)


-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLanNNYOA7OpLWtYzAQF10wP9GExbaoloiXqFe7AtXb/UzUHXhW3VDC1b
mfD0RhgK2i0Dr05RW5FCvj/9i7Jxhrd3E26hTe5g4WckvIcvp+GWhE/5fkdtVMA9
THutX1ukGO/5qCxSRT4hVCeXStAz7tunkF3fcEQjPe8pSSvKxN8tw/wIZzclRDRx
JDE4HYRhAz0=
=OW8h
-----END PGP SIGNATURE-----