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^p2 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^n1 mod every odd number in turn, and you find that 2^n1 ≡ 0 mod m for some odd number m, then m is a factor of 2^n1. 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^(n1)==1 mod n Subtract 2^y or some natural y≤n 2^(n1)2^y == n(2^y1) mod n Divide by 2^y 2^(ny1)1 == (n(2^y1))/(2^y) mod n Replace n by n+2^y 2^(n+2^yy1)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. 
Nth 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]nth term VALUE[/I], increment 2, step 1, where n is an element of the set of integers =>1, and the nth term results in the series having an odd number of terms, In sigma notation the series would look something like this: nth (VALUE) Z (2n1) [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]nth value[/I] 2. If any of the terms in the test range is a multiple of, or shares a common factor with, the [I]nth value[/I], then the [I]nth 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]nthvalue[/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]nth value[/I] , namely "7" is Prime, as per the algorithm. Let us try [I]nth 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]nth 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]nth term VALUE[/I], increment 2, step 1, where n is an element of the set of integers =>1, and the nth term results in the series having an odd number of terms, In sigma notation the series would look something like this: nth (VALUE) Z (2n1) [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]nth value[/I] 2. If any of the terms in the test range is a multiple of, or shares a common factor with, the [I]nth value[/I], then the [I]nth 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]nthvalue[/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]nth value[/I] , namely "7" is Prime, as per the algorithm. Let us try [I]nth 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]nth 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 nevertheless. 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 nevertheless. 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 (N1)!. 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 GophneAxn Little Lemma.

All times are UTC. The time now is 05:41. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.