CRGreathouse has answered most of the questions so there isn't much more for me to say.

[QUOTE=gophne;476653]2) How was Fermat's Little Theorem/Fermat's Primality Test "derived". I am asking out of interest, if you know.
[/QUOTE]

According to the [URL="http://primes.utm.edu/glossary/xpage/Fermat.html"]Prime Pages[/URL], Fermat noticed that 2p divides 2^p-2 for p prime while studying perfect numbers, which are of course closely related to Mersenne primes. I don't think we have any record of how he proved his theorem. Nick has given links to proofs if you want to see those.

[quote]4) Do you agree that the "mersenne number" way of expressing then the Fermat's Little theorem, base 2 could also help with factorization of mersenne numbers, something the standard form of the Fermat Primality Test does not do.[/quote]

Neither form really has an advantage over the other in base 2, because the two forms are equivalent: you can get very quickly from one to the other as I showed in my last post. However, it is harder to generalise your form to bases other than 2. The reason your form works is that (n+1)/2 is an integer for any n that is not a multiple of 2. But if we change 2 to 3, this is no longer true.

[quote]This is because when you are testing the mersenne numbers modulo vs the odd numbers, the remainders of the modulo operation is cyclical, starting with 1 and terminating with (n+1)/2, when the odd number is prime or a false prime I suspect as well. When a particular odd number is a factor of a particular mersenne number, the the 0 remainder, falls at the centre of the modulo cycle that ends with (n+1)/2. This could be algorithmized into some sort of checker for mersenne number compositeness.[/quote]

As far as I can tell, you're just saying that if you calculate 2^n-1 mod every odd number in turn, and you find that 2^n-1 ≡ 0 mod m for some odd number m, then m is a factor of 2^n-1. This is a very slow way of factoring Mersenne numbers - it's just trial division, and it's not even efficient trial division.

My thought was work backwards as though the 2 in n+2 was n+1 and solve the congruence to be 0.

Equivalents generalize to:

2^(n-1)==1 mod n
Subtract 2^y or some natural y≤n
2^(n-1)-2^y == n-(2^y-1) mod n
Divide by 2^y
2^(n-y-1)-1 == (n-(2^y-1))/(2^y) mod n
Replace n by n+2^y
2^(n+2^y-y-1)-1== (n+1)/(2^y) mod (n+2^y)

Unless I messed up a step.edit: or the statement for Fermat's theorem like I did originally. Edit 2: I think you may find it can be changed still to a modular arithmetic statement about double mersennes with 2 more steps though.

N-th Value Primality Algorithm
 

Hi Everybody

Time for playing with another possible new/unusual ? Primality Algorithm on the

[I]mersenneforum.org>Extra Stuff>Blogorrhea>gophne>"New"primality test/check Forum.[/I]

Not sure if anybody would be interested, but at risk of missing out on a possible "new" primality test/algorithm, which is the equivalent to missing out on M50

The Algorithm is as follows;

For the series of odd numbers, where the 1st term of the series is 1, to the [I]n-th term VALUE[/I], increment 2, step 1,

where n is an element of the set of integers =>1, and the n-th term results in the series having an odd number of terms,


In sigma notation the series would look something like this:


n-th (VALUE)

Z (2n-1) [I]Z representing Sigma[/I] in lieu of

n=1


[B]Then for any of the terms of the series so constituted, starting at the 2nd term to the term whose value would be equal to the value of the [I]n-th value[/I] -2.
If any of the terms in the test range is a multiple of, or shares a common factor with, the [I]n-th value[/I], then the [I]n-th value[/I] is Composite, else Prime.
[/B]

To do an example just so to clarify the wording (I am not familiar with Latex on this Site yet);

Let the [I]nth-value[/I] be equal to 7, then the algorithm series, applying Sigma, would be;

01,03,05,07

The test "range" according to the algorithm would be;

03,05......................................................Constituting the "seed" terms in the test range.

03 + 14 =17
05 + 14 =19

Since both these derived values are not multiples, or do not share a common factor with any of the "seed" terms, the [I]n-th value[/I] , namely "7" is Prime, as per the algorithm.

Let us try [I]n-th value[/I] is equal to 2047

The test range would be;

[B]03,05,07,09,11,13,15.......2045[/B].........Test range/Seed terms

For this test range the derived algorithm values would be [B][I]seed terms[/I] + 4094[/B]

The Seed/Algorithm pairs formed would be;

(3,34097) (5,4099),(7,5001),(9,5003), (11, 5005), (13,5007)......

But the 5th term of these pairings share a common factor "11", so according to the algorithm the [I]n-th value[/I] is Composite.

Could anybody confirm or refute that this primality algorithm is true for all Composites/Primes.

Would the above constitute a legitimate primality algorithm?

[I]Caveat: Not sure if anybody else worked on or published any similar primality algorithms, but I could not find anything similar looking it up in Wikipedia.

[QUOTE=gophne;476754]Hi Everybody

Time for playing with another possible new/unusual ? Primality Algorithm on the

[I]mersenneforum.org>Extra Stuff>Blogorrhea>gophne>"New"primality test/check Forum.[/I]

Not sure if anybody would be interested, but at risk of missing out on a possible "new" primality test/algorithm, which is the equivalent to missing out on M50

The Algorithm is as follows;

For the series of odd numbers, where the 1st term of the series is 1, to the [I]n-th term VALUE[/I], increment 2, step 1,

where n is an element of the set of integers =>1, and the n-th term results in the series having an odd number of terms,


In sigma notation the series would look something like this:


n-th (VALUE)

Z (2n-1) [I]Z representing Sigma[/I] in lieu of

n=1


[B]Then for any of the terms of the series so constituted, starting at the 2nd term to the term whose value would be equal to the value of the [I]n-th value[/I] -2.
If any of the terms in the test range is a multiple of, or shares a common factor with, the [I]n-th value[/I], then the [I]n-th value[/I] is Composite, else Prime.
[/B]

To do an example just so to clarify the wording (I am not familiar with Latex on this Site yet);

Let the [I]nth-value[/I] be equal to 7, then the algorithm series, applying Sigma, would be;

01,03,05,07

The test "range" according to the algorithm would be;

03,05......................................................Constituting the "seed" terms in the test range.

03 + 14 =17
05 + 14 =19

Since both these derived values are not multiples, or do not share a common factor with any of the "seed" terms, the [I]n-th value[/I] , namely "7" is Prime, as per the algorithm.

Let us try [I]n-th value[/I] is equal to 2047

The test range would be;

[B]03,05,07,09,11,13,15.......2045[/B].........Test range/Seed terms

For this test range the derived algorithm values would be [B][I]seed terms[/I] + 4094[/B]

The Seed/Algorithm pairs formed would be;

(3,34097) (5,4099),(7,5001),(9,5003), (11, 5005), (13,5007)......

But the 5th term of these pairings share a common factor "11", so according to the algorithm the [I]n-th value[/I] is Composite.

Could anybody confirm or refute that this primality algorithm is true for all Composites/Primes.

Would the above constitute a legitimate primality algorithm?

[I]Caveat: Not sure if anybody else worked on or published any similar primality algorithms, but I could not find anything similar looking it up in Wikipedia.[/QUOTE]

Offuscated trial division.

[QUOTE=science_man_88;476758]Offuscated trial division.[/QUOTE]
Hi science_man_88

I love you, but your monosyllabic answers does not help. Please explain some more or even better, do the "offuscated trial division" for the two examples given. Thanx.

So your algorithm:

Take odd N (which we're checking if it is prime or composite)

For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime.


Trial division algortihm:

Take odd N (which we're checking if it is prime or composite)

For all odd [B]prime[/B] n = 3,5,7,.. < [B]sqrt[/B](N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.


As you can see, you're just doing a much slower version of trial division.

What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.

[QUOTE=axn;476802]So your algorithm:

Take odd N (which we're checking if it is prime or composite)

For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime.


Trial division algortihm:

Take odd N (which we're checking if it is prime or composite)

For all odd [B]prime[/B] n = 3,5,7,.. < [B]sqrt[/B](N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.


As you can see, you're just doing a much slower version of trial division.

What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.[/QUOTE]
Hmmmmm

Not exactly I think. [B][I]Trial division[/I][/B] divided the TEST number by the set of odd numbers up to the sqaure root of that number, until a possible divisor (that leaves a residue of 0 is found). If no such divisors are found, the number is Prime.

The algorithm states that if any of the [I]odd numbers + 2 times the nth Value[/I] in the [I]test range[/I] has a common factor,[I] independant of the number being tested[/I]. I know it would be cumbersome for very large numbers (so is [I]trial division[/I]), but I am trying to establish a "Primality" Test relationship here. There are many Primality Tests out there that are very cumbersome or even incalculable after a few steps, but are still recognised as Primality Tests never-the-less.

Thanks for distilling "my" algorithm into a more clear form for readers to evaluate the "primality test" aspect of it. Much better than my attempt, so if readers could please use axn's form of it.

[QUOTE=gophne;476807]Hmmmmm

Not exactly I think. [B][I]Trial division[/I][/B] divided the TEST number by the set of odd numbers up to the sqaure root of that number, until a possible divisor (that leaves a residue of 0 is found). If no such divisors are found, the number is Prime.

The algorithm states that if any of the [I]odd numbers + 2 times the nth Value[/I] in the [I]test range[/I] has a common factor,[I] independant of the number being tested[/I]. I know it would be cumbersome for very large numbers (so is [I]trial division[/I]), but I am trying to establish a "Primality" Test relationship here. There are many Primality Tests out there that are very cumbersome or even incalculable after a few steps, but are still recognised as Primality Tests never-the-less.

Thanks for distilling "my" algorithm into a more clear form for readers to evaluate the "primality test" aspect of it. Much better than my attempt, so if readers could please use axn's form of it.[/QUOTE]

I don't think you've taken on board what axn meant by this:

[QUOTE=axn;476802]What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.[/QUOTE]

The point is that, if n is odd, then gcd(n, n+2N) = gcd(n, N) and so you are just checking if n has any common factors with N. But if N is not prime, then the smallest n that has a common factor with N is the smallest prime factor of N, so in fact when you first find n such that gcd(n, n+2N) > 1, that n is a factor of N. So you're just doing inefficient trial division.

I guess that technically counts as a "primality test" in that it does correctly determine primality or otherwise of N.
But it's easy to come up with useless primality tests. Here's one: if N>4, then N is prime if and only if N does not divide (N-1)!. Unlike trial division, it's got only one step, so what could possibly go wrong...?

As for why gcd(n, n+2N) = gcd(n, N), it's time for another basic number theory lesson:
Suppose d divides n and n+2N.
Then d must divide their difference, which is 2N.
But d divides n, which is odd, so d is odd, and thus d must divide N.
Conversely, suppose d divides n and N.
Then clearly d divides n+N+N = n+2N.
So the sets of common factors of (n, n+2N) and (n, N) are exactly the same, and in particular gcd(n, n+2N) = gcd(n, N).

Uncompromisingly monosyllabic
 

[QUOTE=gophne;476800]Hi science_man_88

I love you, but your monosyllabic answers does not help. Please explain some more or even better, do the "offuscated trial division" for the two examples given. Thanx.[/QUOTE]That phrase in quotes is not as you say, nor is it spelled right.

I think "You hide a test which splits by small primes, one by one" may be good.

Paul.

Petition to call the simplified form of this test the Gophne-Axn Little Lemma.