Compositeness test

jnml · 2018-01-25, 20:22

$\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.)

jnml · 2018-01-25, 20:29

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.

science_man_88 · 2018-01-25, 20:31

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.

CRGreathouse · 2018-01-25, 21:20

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?

Batalov · 2018-01-25, 21:52

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!

jnml · 2018-01-25, 22:06

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? ;-)

science_man_88 · 2018-01-25, 22:07

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

jnml · 2018-01-25, 22:09

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?

CRGreathouse · 2018-01-25, 23:06

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.

Dr Sardonicus · 2018-01-27, 16:04

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.

science_man_88 · 2018-01-27, 16:20

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.

2018-01-25, 20:22	#1
jnml Feb 2012 Prague, Czech Republ 262₈ 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

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

2018-01-27, 16:04	#10
Dr Sardonicus Feb 2017 Nowhere 3²·11·47 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.