20180125, 20:22  #1 
Feb 2012
Prague, Czech Republ
5×37 Posts 
Compositeness test
odd is composite .
Edit: Actually, there always exists the form with , but the form with exists only for composites. (Should have used paper and pencil before posting.) Last fiddled with by jnml on 20180125 at 20:26 Reason: bug 
20180125, 20:29  #2 
Feb 2012
Prague, Czech Republ
271_{8} Posts 

20180125, 20:31  #3 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Except if we knew n, we'd have a factorization of N. N need be same parity as n. If k and n aren't coprime then there's a smaller factor of N in their GCD.
Last fiddled with by science_man_88 on 20180125 at 20:39 
20180125, 21:20  #4 
Aug 2006
3×1,993 Posts 

20180125, 21:52  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·3^{2}·269 Posts 

20180125, 22:06  #6  
Feb 2012
Prague, Czech Republ
5×37 Posts 
Quote:
Just needed to prove something and yes, of course the form implies nN. But it also, to my surprise, trivialy implies mN, for m not necessarily equal n and that's what it's useful for my case. Can someone else see that? ;) 

20180125, 22:07  #7 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 

20180125, 22:09  #8 
Feb 2012
Prague, Czech Republ
271_{8} Posts 
Hmm, that was retracted long before your reply, ie. <> was changed to >. What's your point?
Last fiddled with by jnml on 20180125 at 22:10 Reason: s/ago/before/ 
20180125, 23:06  #9  
Aug 2006
3×1,993 Posts 
I apologize, I didn't really intend to tease.
Quote:
Yes, it's an important principle, the key insight that lets us prove primality by checking up to sqrt(N) rather than N. 

20180127, 16:04  #10 
Feb 2017
Nowhere
19·281 Posts 
The OP to the thread only requires the minor correction that k could also be zero. Since N is specified to be odd, all positive integer divisors of N are odd, so any two of them differ by an even integer.
Pursuant to CRGreathouse's observation, suppose that N is composite. This means that N > 1, and that there is an integer n, 1 < n < N, such that n divides N. Suppose n is the least such positive integer. Then, the observation is manifest by , so that An additional observation: The integer n is prime. For n > 1, and if 1 < m < n, then m does not divide n (because then m would divide N, contradicting the definition of n as the least such integer). Thus n is prime, directly from the definition of primality. 
20180127, 16:20  #11  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Conjectured compositeness tests for N=k⋅2n±c by Predrag  T.Rex  Miscellaneous Math  27  20151016 19:02 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
Will the torture test, test ALL available memory?  swinster  Software  2  20071201 17:54 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 