mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-01-25, 20:22   #1
jnml
 
Feb 2012
Prague, Czech Republ

5×37 Posts
Default Compositeness test

\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ N is composite \leftrightarrow n\ > \ 1.

Edit: Actually, there always exists the form with n \ = \ 1, but the form with n \ > \ 1 exists only for composites. (Should have used paper and pencil before posting.)

Last fiddled with by jnml on 2018-01-25 at 20:26 Reason: bug
jnml is offline   Reply With Quote
Old 2018-01-25, 20:29   #2
jnml
 
Feb 2012
Prague, Czech Republ

18510 Posts
Default

Quote:
Originally Posted by jnml View Post
\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ N is composite \leftrightarrow n\ > \ 1.
So, what I should have said is:

\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ n \ > \ 1 \rightarrow N is composite.
jnml is offline   Reply With Quote
Old 2018-01-25, 20:31   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by jnml View Post
\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ N is composite \leftrightarrow n\ > \ 1.

Edit: Actually, there always exists the form with n \ = \ 1, but the form with n \ > \ 1 exists only for composites. (Should have used paper and pencil before posting.)
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 2018-01-25 at 20:39
science_man_88 is offline   Reply With Quote
Old 2018-01-25, 21:20   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by jnml View Post
\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ n \ > \ 1 \rightarrow N is composite.
So all we have to do to prove that a number is composite is to find a factor?
CRGreathouse is offline   Reply With Quote
Old 2018-01-25, 21:52   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

961710 Posts
Default

Quote:
Originally Posted by jnml View Post
\forall \ k, \ n, \ N \in \mathbb{N}, odd N, \ N=n^2\ +\ 2kn, \ N is composite \leftrightarrow n\ > \ 1.
This is such a time saver!
So, if there is an n>1 and n|N, then N is composite?
Brilliant!

Or is it brilliant in the opposite direction?
If n*(n+2k) is composite then n>1? Hmm, not quite. N=9, n=1, k=4... and n is not >1. Shucks!
Batalov is offline   Reply With Quote
Old 2018-01-25, 22:06   #6
jnml
 
Feb 2012
Prague, Czech Republ

5·37 Posts
Default

Quote:
Originally Posted by Batalov View Post
This is such a time saver!
So, if there is an n>1 and n|N, then N is composite?
Brilliant!

Or is it brilliant in the opposite direction?
If n*(n+2k) is composite then n>1? Hmm, not quite. N=9, n=1, k=4... and n is not >1. Shucks!
People calm down . You have no idea how nice is to reinvent wheels for us, uneducated common people.

Just needed to prove something and yes, of course the form implies n|N. But it also, to my surprise, trivialy implies m|N, for m not necessarily equal n and that's what it's useful for my case. Can someone else see that? ;-)
jnml is offline   Reply With Quote
Old 2018-01-25, 22:07   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
So all we have to do to prove that a number is composite is to find a factor?
Which is the same as the test 2n+1 is composite if n>i and n = i mod 2i+1
science_man_88 is offline   Reply With Quote
Old 2018-01-25, 22:09   #8
jnml
 
Feb 2012
Prague, Czech Republ

B916 Posts
Default

Quote:
Originally Posted by Batalov View Post
This is such a time saver!
Or is it brilliant in the opposite direction?
If n*(n+2k) is composite then n>1? Hmm, not quite. N=9, n=1, k=4... and n is not >1. Shucks!
Hmm, that was retracted long before your reply, ie. <-> was changed to ->. What's your point?

Last fiddled with by jnml on 2018-01-25 at 22:10 Reason: s/ago/before/
jnml is offline   Reply With Quote
Old 2018-01-25, 23:06   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by jnml View Post
People calm down
I apologize, I didn't really intend to tease.

Quote:
Originally Posted by jnml View Post
Just needed to prove something and yes, of course the form implies n|N. But it also, to my surprise, trivialy implies m|N, for m not necessarily equal n and that's what it's useful for my case. Can someone else see that? ;-)
You means that if n divides N, then N/n also divides N?

Yes, it's an important principle, the key insight that lets us prove primality by checking up to sqrt(N) rather than N.
CRGreathouse is offline   Reply With Quote
Old 2018-01-27, 16:04   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×33×5×19 Posts
Default

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

n \le N/n,

so that

n^2 \le N.

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.
Dr Sardonicus is online now   Reply With Quote
Old 2018-01-27, 16:20   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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

n \le N/n,

so that

n^2 \le N.

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.
And using that k and n are coprime ( unless its a multiple) we can eliminate many k values.
science_man_88 is offline   Reply With Quote
Reply

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 2018-03-11 23:20
Conjectured compositeness tests for N=k⋅2n±c by Predrag T.Rex Miscellaneous Math 27 2015-10-16 19:02
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
Will the torture test, test ALL available memory? swinster Software 2 2007-12-01 17:54
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 14:10.


Fri Dec 3 14:10:27 UTC 2021 up 133 days, 8:39, 0 users, load averages: 2.06, 1.55, 1.29

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.