Shu Cao

Posted on Wednesday, 23 July, 2003 - 09:08 pm:

Theorem: There are arbitarily large gaps in the series of primes. Stated otherwise, given any positive integer k, there exist k consecutive composite integers.

Proof:

$j$ divides $(k + 1)! + j$ , where $2 \leqj \leq k + 1$ , where k and j are integers.

I do not quite understand this. Can anyone please explain it to me? Thank you. Are the K consecutive integers not directly consecutive to k? Just some integers further on on the integer number line?

Please explain anything else that you think needs explaining!

Thank you!

Arun Iyer

Posted on Wednesday, 23 July, 2003 - 09:20 pm:

Assume (k+1)!+1 is a prime

Now since j divides (k+1)!+j (2£ j£ (k+1))
there is no prime in the interval,
[(k+1)!+1,(k+1)!+(k+1))
(what is the length of this interval?)

as k+1 becomes large,the length of this interval becomes large and hence there are large gaps.

Note that we have proved that there are large gaps only when (k+1)!+1 is a prime but then all we needed to show was that there exists large gaps in the series of primes.

love arun
P.S-> If anything is not understood,write back and I (or Nrich Team who are much better at explaining this than I) will try and help.

Shu Cao

Posted on Wednesday, 23 July, 2003 - 09:47 pm:

Would the length be k?
What about when a prime is not of the form (k+1)!+1?
Thank you!

Arun Iyer

Posted on Wednesday, 23 July, 2003 - 10:18 pm:

Yes the interval length is k.

When i assumed (k+1)!+1 as prime,it was more for simplicity than anything else. I could have very well said that "let p be a prime such that p = (k+1)!+1 or p be such that it comes immediately before (k+1)!+1 i.e there is no prime in the interval [p,(k+1)!+1)". The rest of the proof then simply continues.

love arun
P.S It isinteresting to note that there are many twin primes(i.e prime pairs of form p,p+2)and sexy primes(i.e prime pairs of form p,p+6).

Sarah Sarah

Posted on Friday, 25 July, 2003 - 09:20 pm:

Hey Shu Shu! and Arun!

I think the assumption that there is a prime (k+1)!+1 is both unnecessary and unjustified (for example, it isn't true for k=3). To restate the given proof: given any integer k, the k consecutive integers (k+1)!+2, (k+2)!+3,...,(k+1)!+(k+1) are all non-prime. This doesn't depend on there being a prime somewhere nearby, as Arun suggested. What has NOT been shown is that there is a sequence of exactly k composite integers bounded on either side by primes - and you wouldn't expect to be able to show that, because it's not true (it's false for any even value of k).

Arun, are there arbitrarily large twin primes? (goodness.. that's a weird image now I think about it).. And arbitrarily large sexy primes?

love Sarah

Arun Iyer

Posted on Saturday, 26 July, 2003 - 06:43 am:

Sarah,
Don't you think i was trying to "explain" the idea behind the proof and not "giving" a proof???

Don't you think a statement like "The question is equivalent to saying that there exist a large series of consecutive integers which are non-prime. Hence proved." would lead a confused person astray at the start??

If your answer is "No" for both the questions then what it shows is that i am very bad at explaining things and i should keep myself away from these things.

As for twin primes and sexy primes,look here
twin primes
sexy primes

love arun

Sarah Sarah

Posted on Saturday, 26 July, 2003 - 12:13 pm:

Hello Arun,

Sorry - by 'the given proof' I mean the one Siu Siu wrote in her original post, not your explanation.

I am genuinely puzzled by your account: I still don't see the point of inventing a prime somewhere near the interval [(k+1)!+2,(k+1)!+(k+1)]. The idea of the proof Shu had, I think, is that it gives a simple way of finding a sequence of k composite integers for arbitrary k.

I also found a list of record monster primes at
http://www.utm.edu/research/primes/largest.html
They say it's thought there are infinitely many twin primes, but that it hasn't been proven. Obviously if there are infinitely many, then there are arbitrarily large ones, and I think the converse is also true (if there are arbitrarily large twin primes, there is no biggest pair, hence the set is infinite..?)

Also: are there arbitrarily large gaps in the sequence of squarefree integers (i.e. numbers having no repeated factors)?

love Sarah

Shu Cao

Posted on Saturday, 26 July, 2003 - 06:10 pm:

Thank you Sarah and Arun!
Do you think that I understand what the theorem is saying if I think that it is saying that between any two primes there will be k composite numbers anywhere in the set of positive integers, where k is any non negative integer?
Can one get a list of the squarefree integers by using something like Eratosthenes sieve?
Can one look on squarefree integers as if they were primes in a set of numbers where the composite numbers are defined as having at least one factor greater than 1 that is a power of an integer to more than 2?
Can I say consider a product of primes abc...n, where n is the smallest prime,
the sequence of numbers (abc...n)^2+1, (abc...n)^2+2,...(abc...n)^2+(n-1) are squarefree integers, so the lengths of the gaps between the squarefree integers can be 1 less than any prime?
Thank you!
love ss
ps do I know sarah personally? just wondering...

Marcos

Posted on Saturday, 26 July, 2003 - 06:28 pm:

Shu,
I think you're trying to show that there are arbitrarily large gaps in the sequence of non-squarefree numbers , contrary to what Sarah wanted. (Anyhow I think your approach works for this case though)

Marcos

Sarah Sarah

Posted on Saturday, 26 July, 2003 - 07:32 pm:

Yo
There aren't arbitrarily large gaps in the sequence of squareful integers - the largest is 3 (e.g. 5,6,7) since every 4th integer is divisible by 2² .
I think you're right that there are no numbers with squared factors a,b,c,...,or n in the interval [(abc...n)² +1,(abc...n)² +n² -1] but there's no reason why there shouldn't be numbers with other square factors in that interval.
I think the number system you suggested where you call squarefree numbers primes and squareful numbers composite numbers would be a bit weird, because the product of two squarefree numbers could be squarefree or squareful depending on whether the two numbers are coprime (in the traditional sense). But yeaaha I think you can use something like Eratosthenes sieve to find squarefree numbers.
I'm looking for a way to generate a sequence of k consecutive squareful integers, for arbitrary k. Basically, need a foolproof way to find a number N=f(k) such that
N = 0 (mod a₁ ² )
N+1 = 0(mod a₂ ² )
N+2 = 0(mod a₃ ² )
.
.
N+k-1 = 0(mod a_k ² )
I think maybe it should be possible if you choose the a_i so they're pairwise coprime, since then (this is the bit I'm not sure about) you can fix the residues mod a₁ ² , mod a₂ ² , etc. independently. I have no idea how to find a suitable N though. Well I have a sort of vague idea but it's not very good.. love Sarah

Sarah Sarah

Posted on Saturday, 26 July, 2003 - 08:02 pm:

Well here is my lame idea (it takes a lot of computation, and I haven't proved the most important bit works):
let a_i be the i^th prime so a₁ =2,a₂ =3,a₃ =5, and so on.
Let N₁ =a₁ ²
Now add a₁ ² repeatedly until you get a number N₂ such that
N₂ +1º 0(mod a₂ ² )
then add a₁ ² a₂ ² repeatedly until you get a number N₃ such that
N₃ +2º 0(mod a₃ ² )
.
.
when you've got N_i add the product a₁ ² a₂ ² a₃ ² ...a_i ² repeatedly until you get a number N_i+1 such that
N_i+1 +i = 0(mod a_i+1 ² )
etc. etc. until you get to N_k
The k consecutive integers in the interval [N_k ,N_k +k-1] are all squareful.

I suppose it doesn't matter, as long as I can show the algorithm WORKS, how much computation actually running it requires, since the object was to show that there exists such a sequence of integers and not to actually find such a sequence. The problem is that I haven't shown that by adding a₁ ² a₂ ² a₃ ² ...a_i ² repeatedly to the N_i already found I am guaranteed to find - eventually - a number with the required residue (mod a_i+1 ² ). I think it's true, like I said, since I chose the a_i so they're all pairwise coprime, but I haven't proved it. Basically it remains to show that if (x,y)=1 then there exists an integer n such that
nx = r(mod y) for any residue r.

humph.

Sarah x

Sarah Sarah

Posted on Saturday, 26 July, 2003 - 08:05 pm:

And while I'm hogging the thread, Shu, can you see a very simple way - following on from your original thing - to show that there are infinitely many strings of k consecutive composite integers, for any integer k?
(they might not be separated by primes, though)

love Sarah

Michael Doré

Posted on Saturday, 26 July, 2003 - 09:36 pm:

Hi Sarah,

Very nice construction! You are actually 99% of the way towards proving it works - i.e. it does indeed produce k consecutive squareful integers. As you say you only have to prove that if (x,y) = 1 and r is any integer then there is an integer n such that nx = r (mod y). Well it should be clear that you can let r = 1 without loss of generality. Then it reduces to the very well known fact:

- If (x,y) = 1 then there exists n such that nx = 1 (mod y).

This in turn follows immediately from Bezout's theorem which states:

- If x,y are integers then there exists integers m,n such that mx + ny = HCF(x,y)

The most usual way of proving this uses Euclid's algorithm. See for example this link .

An alternative (slicker, possibly less informative, though actually equivalent) way of proving Bezout's theorem is as follows. Let x,y be integers. Consider the minimal positive integer l expressible in the form mx + ny for some integers m,n. It is clear that this cannot be less than HCF(x,y). If it equals HCF(x,y) then we're done. Suppose, for a contradiction, it is greater. Then it cannot be a factor of both x and y. Can you see how to derive a contradiction from this? That would then finish off your proof.

One further point is that you are actually reinventing another well known result called the Chinese remainder theorem. This states:

- If a₁ ,...,a_n are pairwise coprime integers and b₁ ,...,b_n are any integers then we can find an integer N such that N = b_i (mod a_i ) for each i. Furthermore N is essentially unique - that is if N' also satisfies this property then N' = N (mod a₁ ...a_n ).

The existence part can be proved using your approach - and the uniqueness part is easy.

By the way, above it was noted that you cannot find arbitrarily large blocks of square-free integers. I'll mention that a hard related question is: do there exist arbitrarily long arithmetic progressions of squarefree integers? I saw this in a magazine (Crux Mathematicorum) and only one person solved it - and he needed to quote a very deep result first proved in the 70s in order to prove the answer is yes.

Sarah Sarah

Posted on Monday, 28 July, 2003 - 10:59 am:

Michael, thank you!

I was thinking that maybe it could be argued that if (x,y)=1 then the smallest solution of nx=0 (mod y) is n=y. Hence if you add x repeatedly to a number N=r(mod y), each residue can't occur more than once every n+1 additions.. etc..

cheers
Sarah

Michael Doré

Posted on Monday, 28 July, 2003 - 12:20 pm:

That is precisely the way to prove the Chinese remainder theorem.

Michael