Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.javascript
Subject: Re: Primality sieve challenge
Date: Tue, 19 Jan 2016 14:04:12 +0000
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <87bn8h64yr.fsf@bsb.me.uk>
References: <5b608a56-e16b-4467-a0ce-4e30f6796920@googlegroups.com> <n7guk8$s1v$1@gioia.aioe.org> <jb9q9b9gefblv051va88js4u5arthakqsf@4ax.com> <37264925.IaaGi9xk8D@PointedEars.de> <87ziw27kln.fsf@bsb.me.uk> <2865358.ifOrN9Bpor@PointedEars.de> <0f34c52b-ae45-49b0-8363-080d3d11d5fb@googlegroups.com> <3532030.noGN7VB15C@PointedEars.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="32278"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19JZQ2WOQkhEjutNglACPfVfwLMZMYkLu4="
Cancel-Lock: sha1:4TzUO+Mx5s2wS2e9s3dxYSFvNQk= sha1:4aq4R4olLSf/2dKAWcvV+MGffek=
X-BSB-Auth: 1.4d8c72fbe5c10e49f32a.20160119140412GMT.87bn8h64yr.fsf@bsb.me.uk
Xref: csiph.com comp.lang.javascript:29345

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Scott Sauyet wrote:
>
>> Thomas 'PointedEars' Lahn wrote:
>>> Ben Bacarisse wrote:
>>>> but all those that have the form 6k + {0, 2, 3, 4} are clearly
>>>> composite.
>>> I can see why it is so for {0, 2, 4} (all multiples of 6 are divisible by
>>> 2, so are the sums when added 2 or 4), but why also for the summand 3?
>> 
>> Because 6k + 3 is divisible by 3.
>
> Why?  I can see that it follows for k = 1 (9), k = 2 (15), k = 3 (21), and 
> for several greater k, but why for *all* k?

(6k + 3)/3 = 2k + 1 which is an integer.  If that is not enough, you'd
better say what part you doubt rather than just ask another "why?".

<snip>
>> Since all positive integers > 5 are (trivially) of one of forms `6k + 0`,
>> `6k + 1`, `6k + 2`, `6k + 3`, `6k + 4`, or `6k + 5`, and we've easily
>> demonstrated that all those of the form `6k + {0, 2, 3, 4}` are composite,
>
> Yes.
>
>> all primes must be of the form `6k + 1` or `6k + 5`.

(all suitably large primes...)

> Again, why?  If something is true for A and B, it does not follow that it is 
> not true for C ∉ {A, B}: p(A) ∧ p(B) ↛ ¬p(C); here p(X) := “X is composite 
> (not prime)”.  What relation I am missing here?

The key is that every integer > 5 is in one of the six sets Rr = { 6k +
r | k ∈ N } where r is one of 0, 1,... 5.  All the primes are there
somewhere in one or more of these sets.  But all the numbers in R0, R2,
R3 and R4 are composite.  What options are left?  There may be no
primes, of course, but if there are any, they must in either R1 or R5.

-- 
Ben.