mersenneforum.org Compositeness test
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-25, 20:22 #1 jnml   Feb 2012 Prague, Czech Republ 5×37 Posts 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
2018-01-25, 20:29   #2
jnml

Feb 2012
Prague, Czech Republ

2718 Posts

Quote:
 Originally Posted by jnml $\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.

2018-01-25, 20:31   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by jnml $\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

2018-01-25, 21:20   #4
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by jnml $\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?

2018-01-25, 21:52   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·32·269 Posts

Quote:
 Originally Posted by jnml $\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!

2018-01-25, 22:06   #6
jnml

Feb 2012
Prague, Czech Republ

5×37 Posts

Quote:
 Originally Posted by Batalov 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? ;-)

2018-01-25, 22:07   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CRGreathouse 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

2018-01-25, 22:09   #8
jnml

Feb 2012
Prague, Czech Republ

2718 Posts

Quote:
 Originally Posted by Batalov 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/

2018-01-25, 23:06   #9
CRGreathouse

Aug 2006

3×1,993 Posts

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

Quote:
 Originally Posted by jnml 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.

 2018-01-27, 16:04 #10 Dr Sardonicus     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 $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.
2018-01-27, 16:20   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 T.Rex Miscellaneous Math 27 2015-10-16 19:02 lidocorc Software 3 2008-12-03 15:12 swinster Software 2 2007-12-01 17:54 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 01:23.

Tue Jan 18 01:23:37 UTC 2022 up 178 days, 19:52, 0 users, load averages: 1.47, 1.31, 1.28