Compositeness test
 

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

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

[QUOTE=jnml;478363][TEX]\forall \ k, \ n, \ N \in \mathbb{N},[/TEX] odd [TEX]N, \ N=n^2\ +\ 2kn, \ N[/TEX] is composite [TEX]\leftrightarrow n\ > \ 1[/TEX].

[/QUOTE]

So, what I should have said is:

[TEX]\forall \ k, \ n, \ N \in \mathbb{N},[/TEX] odd [TEX]N, \ N=n^2\ +\ 2kn, \ n \ > \ 1 \rightarrow N[/TEX] is composite.

[QUOTE=jnml;478363][TEX]\forall \ k, \ n, \ N \in \mathbb{N},[/TEX] odd [TEX]N, \ N=n^2\ +\ 2kn, \ N[/TEX] is composite [TEX]\leftrightarrow n\ > \ 1[/TEX].

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

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.

[QUOTE=jnml;478366][TEX]\forall \ k, \ n, \ N \in \mathbb{N},[/TEX] odd [TEX]N, \ N=n^2\ +\ 2kn, \ n \ > \ 1 \rightarrow N[/TEX] is composite.[/QUOTE]

So all we have to do to prove that a number is composite is to find a factor?

[QUOTE=jnml;478363][TEX]\forall \ k, \ n, \ N \in \mathbb{N},[/TEX] odd [TEX]N, \ N=n^2\ +\ 2kn, \ N[/TEX] is composite [TEX]\leftrightarrow n\ > \ 1[/TEX].
[/QUOTE]
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! :max:

[QUOTE=Batalov;478374]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! :max:[/QUOTE]

People calm down :bow:. 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? ;-)

[QUOTE=CRGreathouse;478373]So all we have to do to prove that a number is composite is to find a factor?[/QUOTE]

Which is the same as the test 2n+1 is composite if n>i and n = i mod 2i+1

[QUOTE=Batalov;478374]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! :max:[/QUOTE]

Hmm, that was retracted long before your reply, ie. <-> was changed to ->. What's your point?

[QUOTE=jnml;478376]People calm down[/QUOTE]

I apologize, I didn't really intend to tease.

[QUOTE=jnml;478376]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? ;-)[/QUOTE]

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.

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 [b]CRGreathouse[/b]'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 [i]least[/i] such positive integer. Then, the observation is manifest by

[tex]n \le N/n[/tex],

so that

[tex]n^2 \le N.[/tex]

An additional observation: The integer n is prime. For n > 1, and if 1 < m < n, then m does [i]not[/i] 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.

[QUOTE=Dr Sardonicus;478540]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 [b]CRGreathouse[/b]'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 [i]least[/i] such positive integer. Then, the observation is manifest by

[tex]n \le N/n[/tex],

so that

[tex]n^2 \le N.[/tex]

An additional observation: The integer n is prime. For n > 1, and if 1 < m < n, then m does [i]not[/i] 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.[/QUOTE]

And using that k and n are coprime ( unless its a multiple) we can eliminate many k values.