- **Number Theory**
(*http://mymathforum.com/number-theory/*)

- - **Breaking news : Fermat pseudo-primes**
(*http://mymathforum.com/number-theory/221218-breaking-news-fermat-pseudo-primes.html*)

Breaking news : Fermat pseudo-primesHi girls and guys, Finally I have found a way to filter out all the Fermat pseudo-primes!!!!!!!!!!! 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. |

Why 341 is a Fermat pseudo-prime? When we compute 2^340-1 mod 341 is equal to zero But if we decompose 2^340-1 in factors then we could write : 2^340-1=(2^170+1)*(2^170-1) or 2^340-1=(2^170+1)*(2^85+1)*(2^85-1) 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^85-1,341)=31 Check test : 2^170-1 mod 341 = 0 2^170+1 mod 341 = 2 2^85+1 mod 341=3*11 2^85-1 mod 341=31 I gave this example but it is valid for any Fermat pseudo-prime number base 2 For n we compute 2^(n-1) mod n if 2^(n-1) mod n = 1 then n could be either prime or pseudo-prime. As all the prime numbers (>3) could be expressed in the form 6k+1 or 6k-1 hence 2^(n-1)=2^(6k+1-1)=2^(6k) or 2^(n-1)=2^(6k-1-1)=2^(6k-2)=2^(2*(2k-1)) In both cases we can factorize them using polynomial factoring of 2 forms : X^2-Y^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. |

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. |

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. |

Hi Mobel. So lets fix some terminology. Taking the modular equation $a^{n-1}\equiv 1\pmod n$, we define: a pseudo-prime $n$ is a composite number such that the aforementioned equation holds for $a=2$. Now, an interesting fact: if $n$ is a pseudo-prime, then $2^n-1$ is also a pseudo-prime. This means: $2^{2^n-1}\equiv 1\pmod{2^n-1}$. 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 pseudo-prime, 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 pseudo-prime, 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. |

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^170-1) That is the first step 2^340-1=(2^170+1)*(2^85+1)*(2^85-1) 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 pseudo-primes 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 Al-Mahed |

Quote:
The number of factors of 2^(n-1)-1 when n is a Fermat pseudo-prime 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 pseudo-prime 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^n-Y^n (like X^3-Y^3 or X^21-Y^21 etc...). |

I got it!!!!!!!!!!!!!!!! n=341 2^(341-1)-1 = (2^340)-1 = (2^170+1)*(2^170-1) When we compute gcd(2^170+1,341)=1 hence we do not need to factor 2^170+1 But gcd(2^170-1,341)=341 hence we will continue to factor 2^170-1 2^170-1=(2^85+1)*(2^85-1) 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 n-1. If n-1 is product of small factors then we could solve easily the problem. If n-1 is a product of large numbers then we will have a serious problem. As the (n-1)`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). |

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 pseudo-prime, 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 $n-1$ in $2^{n-1}-1^{n-1}$ 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 $n-1$. Now, since you are working with Fermat numbers, $n-1$ 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_k-1}\equiv 1\pmod{F_k}$, where $F_k=2^{2^{k}}+1$ is your Fermat number. Write $2^{F_k-1}-1=2^{F_k-1}-1^{F_k-1}=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 pseudo-prime? 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. |

@Al-Mahed Why 341 as example? You have to read this thread : http://mymathforum.com/number-theory...lity-test.html I proposed a new primality test so 341 is a number failing my test. I called Fermat pseudo-prime number base 2 instead of calling it Mobel pseudo-prime. 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, semi-prime numbers, factorization, integer sequences, combinatorics, puzzles .... |

All times are GMT -8. The time now is 02:43 PM. |

Copyright © 2019 My Math Forum. All rights reserved.