My Math Forum If P is prime imply that a is prime

 Number Theory Number Theory Math Forum

 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:
 Originally Posted by Peter 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.
Proving that if a is composite then P is composite it is easy to do.
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 gcd-algorithm 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: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: If P is prime imply that a is prime

Quote:
 Originally Posted by momo I read in wikipedia that it exists some gcd-algorithm 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)). "
That would be Stehlé-Zimmermann gcd with Schönhage-Strassen multiplication as a subroutine. The algorithm is only useful for enormous numbers, but perhaps yours would do. C & P describe the algorithm in Prime Numbers: A Computational Perspective.

Quote:
 Originally Posted by momo 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.
But you still need to check P' for primality, and it's vastly larger than a. Take a = 97, for example. Then s = 9, P = 362977, s' = 602, P' = 45788659515499329351313286264520603415561092601786 9681525189285667319840609
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: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: If P is prime imply that a is prime

Quote:
 Originally Posted by momo 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.
It's not even true. gcd(P, P') = 1, but 38459 divides P'. The number is 'small' enough that this could even be checked by hand... though Pari will do it in microseconds.

 Tags imply, prime

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post momo Number Theory 4 June 3rd, 2017 03:29 PM Snoopy Abstract Algebra 9 March 20th, 2011 09:32 PM Bogauss Number Theory 13 February 4th, 2011 11:42 AM Sara so Number Theory 5 December 20th, 2010 10:52 AM Sara so Number Theory 2 November 13th, 2010 02:51 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top