
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 24th, 2008, 07:26 PM  #1 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  If P is prime imply that a is prime
a integer >2 s=int(sqrt(a)) s!= factorial s P= a + s! If P is prime then a is prime. How to prove it? 
September 25th, 2008, 12:14 AM  #2 
Senior Member Joined: Sep 2008 Posts: 150 Thanks: 5  Re: If P is prime imply that a is prime
Try an indirect proof: If a is not a prim, it should have a divisor d lower or equal sqrt(a). Well then d should divide P=a+s!. So P is not prime. 
September 25th, 2008, 07:50 AM  #3  
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Re: If P is prime imply that a is prime Quote:
But proving that if P is prime then a is prime is more difficult because if a is prime P could be prime or composite. Direct proof is hard to do. 43 is prime 6!=720 720+43=763 is not prime 763=7*109 What we can say is that if a is prime and P composite then the divisor of P is bigger than s  
September 25th, 2008, 08:56 AM  #4 
Senior Member Joined: May 2008 From: York, UK Posts: 1,300 Thanks: 0  Re: If P is prime imply that a is prime
Quite often a direct proof in a case such as this is impossible. The indirect proof proposed by Peter (assuming it is correct) is a proof by contrapositive and is just as 'good' a proof as a direct proof.

September 25th, 2008, 02:16 PM  #5 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Re: If P is prime imply that a is prime
I have found a way to know if P is prime or not. If we compute a new number P' = P + int(sqrt(P))! we have to check gcd(P,P'). If gcd(P,P')=1 then we are sure (if we know that a is prime) that P is prime number. If gcd(P,P') different than 1 P is composite. But the problem is how to compute such big numbers. Is there any algorithm to compute gcd(a+s!,P+s'!)? s'=int(sqrt(a+s!)) 
September 25th, 2008, 03:32 PM  #6 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Re: If P is prime imply that a is prime
I read in wikipedia that it exists some gcdalgorithm reducing the time computing. http://en.wikipedia.org/wiki/Euclidean_algorithm "There are more complex algorithms that can reduce the running time to O(n(logn)2(loglogn)). " With the technique above we could "create" some big prime numbers. We begin by any known prime a We compute P=a+s! We compute P'=P +s'! We compute the gcd(P,P') If P' is prime then we loop by reusing P as a We do it until we find a big prime number. I do not know how big it will be and how many time it will require. 
September 25th, 2008, 06:34 PM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: If P is prime imply that a is prime Quote:
Quote:
63579725449566870607520539922019775110433854542621 654701947779096005018441911916 84237142216311566452708386112731719886757712916913 982175063709576776959333207573 74653440480920233219664260822931041023401132880043 129392864924657932463694883723 52060621157381257864186239515004618853550519076484 896793569094622102088595319410 65368967400954244335225979474223862428597668694013 609152676309914870900772877460 75921975062449157877798144901626535479218431486830 489838973725587455563543064418 12337610314141797853967687608957294030712558965749 158896229736620566136776138218 04119241585045560428117814024643073617899124982149 991606598388878347430389460603 64033424134904953186980939424054047704915391277923 240180577665862328990936258015 24748989642777176851787808310975168958916300733465 703557136630445964245284076717 44119187315354126769360858157638259179536403946204 101453087343422560771517668539 18122616266086909203975777155200860067765658945405 607838815532691281965374179612 60895188821240525810560747179895337152902169751689 461712278332357832020291620046 79846230143838339337337432422211342229902374590582 066045399686457915058431592786 95612053875847832482068116807055713039835929041755 418768789936162209792000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000362977. (For what it's worth, the big number P' isn't prime; it's divisible by 38459.)  
September 25th, 2008, 07:40 PM  #8 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Re: If P is prime imply that a is prime
I knew that P' would be big. But if we can compute easily gcd(P,P') we can do it for a lot of prime numbers. You do not have to check the primality of P' because if gcd(P,P')=1 then P' is prime. Is it useful or no ? I do not know. 
September 25th, 2008, 07:51 PM  #9 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Re: If P is prime imply that a is prime
You wrote : 'But you still need to check P' for primality" Knowing that we have chosen the number a as prime, you do not need to do so because if gcd(P,P')=1 then P' is prime. P=a+s! If a is prime then P could be either prime or composite. If we want to know if P is prime then we compute P'=P+s'! If gcd(P,P') is equal to 1 we are sure that P is prime. I'm not talking about P'. If P is prime then we use it as a and we loop again by using the same routine. In your case P' is composite. Some numbers a will give you 2 or 3 numbers (maybe more) in a row. 
September 26th, 2008, 04:43 AM  #10  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: If P is prime imply that a is prime Quote:
 

Tags 
imply, prime 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primorial + prime = prime  momo  Number Theory  4  June 3rd, 2017 03:29 PM 
Does having prime radical imply being primary?  Snoopy  Abstract Algebra  9  March 20th, 2011 09:32 PM 
p is prime if (2p)! mod (p^3) not = 0  Bogauss  Number Theory  13  February 4th, 2011 11:42 AM 
Prime  Sara so  Number Theory  5  December 20th, 2010 10:52 AM 
p prime  Sara so  Number Theory  2  November 13th, 2010 02:51 AM 