Mersenne: Re: Intro

[David Meyer]

Sorry if this is belated. I sent it a few days ago and it appears to 
have not been received.



One of the main theorems of elementary number theory is the
following:

For all integers "a" and "m" such that gcd(a,m) = 1,
a^(phi(m)) = 1 (mod m)


If you are not familiar with congruence classes, then the last statement
is equivalent to: a^(phi(m)) - 1 is divisible by m.
(In fact, x=y (mod m) can be defined as meaning x-y is divisible by m)

phi(m) is Euler's Totient Function, which is defined as follows:
phi(m) = The number of integers between 1 and m that are relatively
prime to m. (an integer k is relatively prime to m if gcd(m,k) = 1)
As an exercise, prove the following:
phi(m) = m*Prod[(1 - 1/p)] where the product
is taken over all prime factors of m.

It is apparent that for all primes p, phi(p) = p-1,
and a=2 is relatively prime to all primes p greater than 2.
So it follows from the main theorem that 2^(p-1) - 1 is divisible by p 
for all primes p>2.


Proof of the main theorem (without group theory):

Definition 1:
A reduced residue system mod m is a set of integers S such that:
1) gcd(x,m) = 1 for all x in S.
2) S has phi(m) elements
3) No two elements of S are congruent modulo m
(ie, x=y (mod m) implies x=y )


Lemma 1: Let S be a reduced residue system mod m, then
the following is also a reduced residue system mod m:
T = { a*x | x in S }
where a is any fixed element in S.

Lemma 1 proof:
To show T is a reduced residue system we need to show it satisfies
the three conditions in the definition.

Condition 1: Let u be any element of T, so that u=a*x for some
x in S. Since a and x are both elements of S, a reduced residue system,
we know that gcd(a,m) = 1 and gcd(x, m) = 1. It follows
that gcd(a*x, m) = 1, so gcd(u,m) = 1.

Condition 2: This is obvious. There will be no collapsing since
a is nonzero. a*x = a*y implies x=y.

Condition 3:
Consider any two elements u and v of T which are congruent,
By definition, u = a*x_1 and v = a*x_2
for some elements x_1 and x_2 of S. But
if a*x_1 = a*x_2 (mod m), then it follows that
x_1 = x_2 (mod m) since gcd(a,m) = 1.
So it must be that x_1 = x_2 (since S is a reduced residue system)
thus u=v.
QED.

Moving on:

Lemma 2: Let S, and T be any two reduced residue systems.
Then Prod[over x in T, x] = Prod[over x in S, x]  (mod m)
Lemma 2 Proof:
Note that if a=b (mod m), then gcd(m,a) = gcd(m,b).
Thus, each congruence class is either relatively prime to m
or not. There are only phi(m) congruence classes whose elements
are relatively prime to m, and thus a reduced residue
system must be made up of one element from each of these
congruence classes. Thus, for every element of S,
there must exist one and only one element of T in the same
congruence class. Thus, the the lemma holds. QED.



So now, let S be any reduced residue system, and
T = { ax | x in S } for some a in S.

By Lemma 1 and 2, Prod[over x in T, x] = Prod[over x in S, x] (mod m)

But also:
Prod[over x in T, x] = Prod[over x in S, a*x] =
a^(phi(m)) * Prod[over x in S, x]


Thus,
a^(phi(m)) * Prod[over x in S, x] = Prod[over x in S, x] (mod m)
a^(phi(m)) = 1 (mod m)

(we are allowed to cancel since the product is relatively prime to m)

QED.

A second, more insightful way, is to generalize and show that the set of 
congruence classes mod m relatively prime to m forms a group under 
multiplication. Then, since the order of an element divides the order of 
the group, and the order of the group is phi(m), we know that a^(phi(m)) 
= 1 (mod m)


As for your second theorem, it is also commonly known that:


x^(ab) - 1 = (x^a - 1)(x^(a(b-1)) + x^(a(b-2)) + ... + 1)

Which means x^n - 1 is composite if x>2 (let a=1,b=n) or if
n is composite.

If you want some better explanations of these concepts, you may
want to seek out some elementary number theory books, such as
"Elements of Number Theory" by Pettofrezzo and Byrkit.


PS. This was typed in a hurry, if anyone sees any mistakes, let me know.


Regards,
   David T. Meyer ([EMAIL PROTECTED])

_
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Re: Mersenne: Prime95 for AIX

[Klaus Kastens]

Hi Chris,

On Fri, 10 May 2002 18:06 +0200, Chris Notz wrote:
> 
> I have several PCs, computing prime95. I have several big RS/6000 too
> and I would like to use them too for calculating prime. Does anyone know
> a program for AIX? I didn't found a program. I hope you know probably
> one.
> 

you could try Glucas: 
or Mlucas: 

I had no problems building Glucas on a POWER3 machine with AIX 5.1, but
this still needs some tuning. (host is currently down for maintenance)


Drop me a line if you are interested.

 Klaus
_
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Re: Mersenne: Prime95 for AIX

[Guillermo Ballester Valor]

On Fri 10 May 2002 18:06, you wrote:

> Hello
>
> I have several PCs, computing prime95. I have several big RS/6000 too
> and I would like to use them too for calculating prime. Does anyone know
> a program for AIX? I didn't found a program. I hope you know probably
> one.
>

You could try to compile Glucas. It is a Mersenne prime tester ready for most 
platforms but unfortunately no so friendly as Prime95.

See 

http://glucas.sourceforge.net

You also can try Mlucas, 

ftp://hogranch.com/pub/mayer/README.html
  
Good luck,

Guillermo

-- 
Guillermo Ballester Valor
[EMAIL PROTECTED]
Granada (Spain)


_
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Mersenne: Prime95 for AIX

[Chris Notz]

Hello

I have several PCs, computing prime95. I have several big RS/6000 too
and I would like to use them too for calculating prime. Does anyone know
a program for AIX? I didn't found a program. I hope you know probably
one.

Thanx and best regards
Chris

--
 http://www.analog-digital.ch
--


_
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Mersenne: RE: Mersenne Digest V1 #961

[Ernst Madsen]

Hi David.

No, you're right. Nobody answered via the list. I can tell, because I
read the Digest, and your 2 mails were the only ones on the subject.

Regards,
Ernst Madsen
[EMAIL PROTECTED]

> 
> Also, I had thought that this was a list for public 
> discussion, and yet I have not received even one replie via 
> the list -- or do the headers hide the fact that the reply is 
> from the list?
> 
> I am greatly perplexed!
> 
> David E. Sanders
> [EMAIL PROTECTED]
> 
> 

_
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers