October 10th, 2015, 12:14 PM  #1 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Breaking news : Fermat pseudoprimes
Hi girls and guys, Finally I have found a way to filter out all the Fermat pseudoprimes!!!!!!!!!!! Easy to do it. Try to rethink the Fermat test. Forget all what you learned about it. Try to find an elementary proof of little Fermat theorem. See you later. 
October 11th, 2015, 09:17 AM  #2 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
Why 341 is a Fermat pseudoprime? When we compute 2^3401 mod 341 is equal to zero But if we decompose 2^3401 in factors then we could write : 2^3401=(2^170+1)*(2^1701) or 2^3401=(2^170+1)*(2^85+1)*(2^851) we could continue factorizing until we find no other factor than those computed. I`m not going to find all the factors but just what I need to show that 341 is composite. By compute the gcd`s I will show that 341 is composite number gcd(2^85+1,341)=33 33 is > 1 and < 341 hence 341 is composite. I can continue : gcd(2^851,341)=31 Check test : 2^1701 mod 341 = 0 2^170+1 mod 341 = 2 2^85+1 mod 341=3*11 2^851 mod 341=31 I gave this example but it is valid for any Fermat pseudoprime number base 2 For n we compute 2^(n1) mod n if 2^(n1) mod n = 1 then n could be either prime or pseudoprime. As all the prime numbers (>3) could be expressed in the form 6k+1 or 6k1 hence 2^(n1)=2^(6k+11)=2^(6k) or 2^(n1)=2^(6k11)=2^(6k2)=2^(2*(2k1)) In both cases we can factorize them using polynomial factoring of 2 forms : X^2Y^2 or X^(2t+1)+ or Y(2t+1) There are algorithm doing this job Once we have all the polynomial factors (f1,f2,f3,....fm) we should compute gcd(f1,n) gcd(f2,n) gcd(f3,n) ..... gcd(fm,n) if one of those gcd give a value between 1 and n then n is surely composite otherwise is certified prime. I do not know the algorithmic complexity of such algorithm when n is large. Ps : If there is some omission or mistaping please correct it. I`m too ill to focus on details but the primality problem is solved for ever. 
October 11th, 2015, 09:19 AM  #3 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
If someone can put all what I said above in technical form (Latex and so one) it will be helpful. Anyone can read it without any discomfort. The problem is definitely solved. Any question will be welcomed. 
October 11th, 2015, 11:10 AM  #4 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
I need to know if there is a way or formula to compute the number of distinct primes dividing (2^(n!))1 Example : 15 distinct primes divide (2^(5!))1 6 distinct primes divide (2^(4!))1 I do not need the exact value but just an approximation. I need it to solve another problem. Thank you for any doc or clue or formula or URL. It is not an emergency. 
October 11th, 2015, 12:17 PM  #5 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
Hi Mobel. So lets fix some terminology. Taking the modular equation $a^{n1}\equiv 1\pmod n$, we define: a pseudoprime $n$ is a composite number such that the aforementioned equation holds for $a=2$. Now, an interesting fact: if $n$ is a pseudoprime, then $2^n1$ is also a pseudoprime. This means: $2^{2^n1}\equiv 1\pmod{2^n1}$. A Fermat number is a number of the form $2^{2^k}+1$, so we are talking about different things because, in this case, for $2^{2^k}+1=n$ where $n$ is a pseudoprime, we have $2^{2^{2^k}}\equiv 1\pmod{2^{2^k}+1}$. Now if you plug it in the first identity you will get an increasing amount of powers of two, I mean, if $2^{2^k}+1$ is a pseudoprime, then $$2^{2^{2^{2^k}+1}1}\equiv 1\pmod{2^{2^{2^k}+1}1}$$. But that seems to lead to nowhere, because it gets an infinite sequence of raising powers which grows pretty quickly in computational complexity. This means that factorizing it is unpractical. 
October 11th, 2015, 01:24 PM  #6 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
It seems impractical at first glance. Factoring 2^(2*n)1 or 2^(3*n)1 is impractical if we want to find all the factors. But if we need only one factor then we have to find a way to reach quickly. How can we do that? n=341 2^340  1 = (2^170+1)*(2^1701) That is the first step 2^3401=(2^170+1)*(2^85+1)*(2^851) That is a part the second level because 2^85+1 can be factorized as (2^17)^5+1^5 =(2+1)*some stuff There are even parts and odd parts on 340=4*85 (4 is the even part and 85 the odd part). As we go from the first level to the level below of factorization we will find that a factor giving us the solution. It deserves to be studied to make sure that n is finally composite without any doubt. I`m aware of the hurdles. I`m not dumb. Unfortunately I`m not programmer to test some Fermat pseudoprimes numbers to see if there is a pattern to exploit to get the job done. My solution is definitive. No one can tell that it will not lead to the solution. It is time to improve the second part of the algorithm. I can not do it alone. While working on that problem I deeply think that we could use the Fermat test improved to factorize any odd number. I`m waiting for other comments. Thank you AlMahed 
October 11th, 2015, 02:26 PM  #7  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
The number of factors of 2^(n1)1 when n is a Fermat pseudoprime base 2 are finite. Only one factor will allow us to find the solution. In fact there are many. How to detect which one is not an unsolvable problem. Just think little bit about it. Stay focused on the problem. It seems to me that you have taken another having nothing to do with my problem. If n is pseudoprime then for sure (2^n)1 is composite. As n is odd (2^n)1 is composite and can be factorized as difference of odd powers X^nY^n (like X^3Y^3 or X^21Y^21 etc...).  
October 11th, 2015, 03:42 PM  #8 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
I got it!!!!!!!!!!!!!!!! n=341 2^(3411)1 = (2^340)1 = (2^170+1)*(2^1701) When we compute gcd(2^170+1,341)=1 hence we do not need to factor 2^170+1 But gcd(2^1701,341)=341 hence we will continue to factor 2^1701 2^1701=(2^85+1)*(2^851) What is gcd(2^85+1,341)=11 hence 11 divide 341 end 341 is composite 341=11*31 So the research will some sort of binary research. It will speed the test. Important : keep in mind that there is a difference between the polynomial factors and the divisors. 2^85+1 is one factor but it is equal to the product of 4 primes 3*11*43691*26831423036065352611 The solution is almost complete. We need to evaluate the algorithm complexity when n become large. The hurdle will be the factorization of n1. If n1 is product of small factors then we could solve easily the problem. If n1 is a product of large numbers then we will have a serious problem. As the (n1)`s of Fermat pseudo primes are often product of small factors I do not think that it will be a problem at least for some lower size (200 digits more I do not know). 
October 11th, 2015, 09:22 PM  #9  
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
Hi Mobel, I misread your posts so mea culpa, I assumed you asked for some methods. But I was also confused, you said that 341 is a Fermat pseudoprime, this is very wrong since 340 is not a power of 2. I'll just comment your last post. Quote:
Quote:
Basically your test boils down to factor the exponent $n1$ in $2^{n1}1^{n1}$ by writing it as a difference of two powers, so this is again the very same problem in complexity terms, i.e., to factor $n$ which is "as big" as $n1$. Now, since you are working with Fermat numbers, $n1$ will be a power of 2 and this greatly simplify things in this respect, there is really no big issue in dividing by 2 until reaching 1. In this case you are testing whether $2^{F_k1}\equiv 1\pmod{F_k}$, where $F_k=2^{2^{k}}+1$ is your Fermat number. Write $2^{F_k1}1=2^{F_k1}1^{F_k1}=2^{2^{2^{k}}}1^{2^{2^{k}}}$ and your factors are simply $$ 2^{\frac{2^{2^{k}\ell}}{2^\ell}}1^{\frac{2^{2^{k}\ell}}{2^\ell}}. $$ You then must have all these factors, which are very easy to compute. But, is this a test of $F_k$ being a pseudoprime? You could multiply these factors and see if some subset of them is divisible by $F_k$, clearly none can be exactly $F_k$. But this looks complicated, although there is perhaps a way using what I suggested. After working in some details lots of complication appeared, so once I have something better I post here. If any detail is misunderstood please point out.  
October 12th, 2015, 01:50 AM  #10 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
@AlMahed Why 341 as example? You have to read this thread : New primality test I proposed a new primality test so 341 is a number failing my test. I called Fermat pseudoprime number base 2 instead of calling it Mobel pseudoprime. Charles will understand what I`m talking about because he intervenes in that thread. All my threads are linked in some way or another. My interests : primes, semiprime numbers, factorization, integer sequences, combinatorics, puzzles .... 

Tags 
breaking, fermat, news, pseudoprimes 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fermat primes  fafa  Number Theory  4  July 10th, 2013 11:25 AM 
Problems driving me crazy.(Primes,Fermat,Euler)  usermind  Number Theory  1  October 5th, 2010 09:30 AM 
Pseudofinite fields  Mathworm  Abstract Algebra  1  March 5th, 2009 02:20 PM 
PseudoDiophantine Nuisance  reddmann  Number Theory  2  August 30th, 2007 08:03 AM 