Right track
 

[QUOTE=wblipp;93224]Mally,

If I understand correctly, you have stumbled onto what is known as a Fermat Probable Prime test, augmented with suggestions about how to perform the modulo that are well suited for hand calculation. Unfortunately, you have read Fermat's Little Theorem backwards, and you do not have a proof of primality: for any prime it is true that a^(p-1) = 1 mod p, but for every choice of "a" there are also some composites for which a^(n-1) = 1 mod n. Try googling PRP and/or "Probable Prime" for more information.

Also check out Strong Probable Prime or SPRP - this improves the PRP test by observing that as long as k is even, you can factor a^k-1 as a difference of squares, and that if p is prime, it must divide one of these. Many composites that return false positives to the PRP test will fail the SPRP test because n=a*b, but a divides one of the terms and b divides a different term, so n divides the product, but not any individual term.[/QUOTE]

:bow:
I agree with what you say and thats a call to go back to the drawing board.
Until such time I will refrain from commenting on your post.
Thank you William, you have once again guided me on the right track
Mally :coffee:

Strange logic
 

[QUOTE=alpertron;93229]According to your proof all Mersenne numbers with prime exponents are prime.

According to your criterion any Mersenne number is prime. :wink:[/QUOTE]

:smile:

I'm afraid I cant agree with your first line statement and your conclusion.

Please refer to Wblipp's post as he is nearer to the truth and desribes more accurately what I presented.

Mally :coffee:

The idea is that all Mersenne numbers with prime exponents are pseudoprimes in base 2 using Fermat's method, so your method will fail for Mersenne numbers.

Mally,

You may want to study Dario's (alpertron's) post more closely. He was making the same point I made - that some composite numbers will pass the test you propose. He provides a large class of examples; he points out that every Mesenne number with prime exponent will pass your proposed test.

William

Misleading.
 

[QUOTE=alpertron;93436]The idea is that all Mersenne numbers with prime exponents are pseudoprimes in base 2 using Fermat's method, so your method will fail for Mersenne numbers.[/QUOTE]

[QUOTE=Wblipp]You may want to study Dario's (alpertron's) post more closely. He was making the same point I made - that some composite numbers will pass the test you propose. He provides a large class of examples; he points out that every Mesenne number with prime exponent will pass your proposed test.

William [/QUOTE]

:smile:
With due respect to both you two outanding math'cians I quote above

The last lines in both the above posts are contradictory.

Very misleading indeed!

Mally :coffee:

Mally, English is not my primary language so maybe I expressed wrong myself.

But the idea is that I showed that all Mersenne numbers with prime exponents pass your _primality_ test when we believe that almost all members of this set are _composite_ numbers.

[QUOTE=alpertron;93436]The idea is that all Mersenne numbers with prime exponents are pseudoprimes in base 2 using Fermat's method, so your method will fail for Mersenne numbers.[/QUOTE]

[QUOTE=wblipp;93447]he points out that every Mesenne number with prime exponent will pass your proposed test.[/QUOTE]


[QUOTE=mfgoode;93491]
The last lines in both the above posts are contradictory.[/QUOTE]

We seem to have a communications failure here; these two messages are attempting to say the same thing. Perhaps the problem lies in the use of the word "failure". Alpertron is saying that every Mersenne number with prime exponent (for example, 2[sup]11[/sup]-1 = 2047) will pass your proposed test and be declared prime by your proposed test. But 2047=23*89, so your proposed test is wrong when it declares 2047 to be prime. He calls this wrong answer a failure of your test.

I called this same event "passing your proposed test" because your proposed test says "prime" - but says so incorrectly.

It's a matter of focusing on the proposed test or the validity of the proposed test - we all agree the proposed test says 2047 is prime and we all agree the proposed test is wrong about 2047. And we've both been trying to say this.

My mistake.
 

:smile:
I'm very sorry that I misunderstood your answer Alpertron, but no matter, you are perfectly clear .

Thank you Wblipp for clarifying my misinterpretation of the posts.

I think you are over emphasising the question of a number passing the test as a pseudo prime or Poulet number. Once this method singles out a possible prime then the other pseudoprime tests can follow but it saves a lot of work.
If I recall correctly the Korsett's criterion can be applied for pseudoprimes.

And to my luck I have one last example left worked out for me that exactly shows that the very number Dario has picked viz: 2047 has been proved that it is NOT a prime by the same method I have presented altho' I made my examples as straightforward as I could. It simply does Not by pass the
algorithm and is detected

I would call this Divine intervention believe it or not.!

If 2047 is detected as a pseudoprime then by induction the rest of the primes should follow suit. Not rigorous, but all mathematicians particularly Fermat depended on intuition and hunches to achieve correct results.

So I cross my fingers and hope for the best. So far I have not personally tested this algorithm for random primes, myself ,to be honest but will now attempt to do so

I will definitely present this ingenious method of proving that 2047 is NOT prime using Fermat's theorem exatly as in my worked examples but I have a long journey ahead of me early morning so Please wait for it till I come back in the evening.

You may try this method out on 2047 but I warn you its a very tricky derivation if you have not , so far followed fully, my two worked examples.
Please get the gist of them, as if not, then you will not follow the one I present.

The originator has forethought this in the computer era and not meant for hand or calculator calculations. This man is a genious and hats off to him.

Mally :coffee:

[QUOTE=mfgoode;93512]You may try this method out on 2047 but I warn you its a very tricky derivation if you have not , so far followed fully, my two worked examples.[/QUOTE]

Are you planning on changing your method? As presented so far, you method would result in:

2[sup]2046[/sup]-1 = (2[sup]1023[/sup]-1)*(2[sup]1023[/sup]+1)
=(2[sup]11*93[/sup]-1)*(2[sup]11*93[/sup]+1)
=(2048[sup]93[/sup]-1)*(2048[sup]93[/sup]+1)
=((N+1)[sup]93[/sup]-1)*((N+1)[sup]93[/sup]+1)
=N*(N+2)
=N

Thereby falsely claiming 2047 is prime.

[QUOTE=wblipp;93514]Are you planning on changing your method? As presented so far, you method would result in:

2[sup]2046[/sup]-1 = (2[sup]1023[/sup]-1)*(2[sup]1023[/sup]+1)

Thereby falsely claiming 2047 is prime.[/QUOTE]
:smile:
No William, your reasoning is circular. It is like X = a^2 - b^2 so---X=X
I have no time right now but to shortly reply to you but will do so when I get back.
Rgds.

Mally :coffee:

Number 2047 Mersenne pseudoprime
 

:smile:
Number 2047: This number has factors 89 and 23. It is = 2^11 – 1 a Mersenne number and composite.

Let us test if this number is a prime or not. And whether it has factors or not by the application of FLT and Binomial theorems.

2 ^ (2047 – 1) – 1 = 2^2046 – 1
= (2^1023 + 1) (2^1023 – 1)

Now 2^1023 =[ 2^30 * 2] ^ 33 (Since 1023 = 31 * 33)
We have from our tables 2^30 = 1073741824

So 2^1023 = [1073741824 * 2]^33
Express 1073741824 in units of 2047

Thus 1073741824 = (524544) * (2047 ) + 256 (remainder)
If (524544)(2047) is denoted by N

Then 2^30 = N + 256 (N is 2047 Or its multiple )
Therefore 2^31 =2 N + 512 (Here 2N is a multiple so call it N )

Therefore 2^1023 = (N + 512)^33
= ( N + 511 and 3/4 + 1/4 )^33 But 511and ¾ = 2047/4

So= (5N/4 + ¼)^33

Now 2^1023 + 1 = (5N/4 +1/4)^33 + 1

2^1023 – 1 = (5N/4 + ¼) ^33 - 1

2^1023 = (5N/4 + ¼)^33

= ¼^33 (5N + 1)^33 (taking out the quarter)
Squaring both sides and subtracting 1 we get2^2046 – 1 = (1/4)^66 (5N + 1)^66 – 1

The last term of the expansion ( ¼)^ 66 is less numerically than – 1.

Therefore the expansion is not fully divisible.

Therefore by FLT 2047 is not a prime

Since 2047 is a Mersenne pseudoprime I presume that all mersenne pseduoprimes can be detected by this method and will not pass thru the prime sieve where the primes are let thru.

However a number like 341 an FLT pseudoprime will not be detected thru the sieve

A good test would be to see whether 2^67 can be detected or not by this algorithm. I have not attempted but leave it for you to test it out .

Mally :coffee: