Rate my proof

I'm working through Velleman's "How to Prove It", and I decided to try and do a proof of a lemma used in one of the exercises. The question in the book were for the reader to think about whether there are any more triplet primes except 3, 5, 7.

Of course there aren't, and the easiest proof of that is showing that since one out of every three consecutive integers needs to be divisible by three, it's impossible for all those three numbers to be prime.

Since that proof uses the (unwritten) lemma that for every n consecutive integers, at least one of them will be divisible by n, I'd try my hand at proving it, before actually diving into the proof methods of the book.

In short, rate my proof Veeky Forums:
Theorem:
For every [math]n[/math] consecutive integers, at least one of those integers will be divisible by [math]n[/math].

Proof:
The case where n is 1 is trivial, since all numbers divide by (at least) 1.

Let [math]n[/math] be an integer such that [math]n > 1[/math]. Let [math]x, x-1,x-2,...,x-(n-1)[/math] be the list of the [math]n[/math] consecutive integers.

We proceed by contradiction. Since none of the integers in the list is divisible by [math]n[/math], [math]x[/math] is not divisible by [math]n[/math]. Thus,

[eqn]x = qn + r[/eqn],
[eqn](1) x - r = qn[/eqn]

Where [math]r[/math] is the remainder.

Since [math]r[/math] is the remainder, [math]0 < r < n[/math], but [math]r[/math] must be greater than [math]n-1[/math], since all integers from [math]x-1[/math] to [math]x - (n-1)[/math] are found in the list. Thus we have a contradiction.

Q.E.D (hopefully)

Feel free to point out the flaws in my proof, there are certain to be some. Anything that's unclear, or unconventional in proofs.

the proof is technically fine but it's a bit weird when you say

>but r must be greater than n−1, since all integers from x−1 to x−(n−1) are found in the list.

in my opinion it's easier to just note that since 0

it's actually quite good.

Yeah, that felt like the "weakest" part to me too, I was afraid there was some circular reasoning going on there, but perhaps not.

And yeah, the way you explained it was way better. So is replacing the last part with something like:

"Since [math]x-r[/math] for every [math]0 < r < n[/math] is in the original list, we have a contradiction."

a better version?

i personally like it better

Yeah, I agree. It reads a lot more clearly. I was sort of looking for a clearer way of "showing" that all those numbers were in the list, but is that not necessary? It seems "self-evident", but is it OK to leave it at that?

it's definitely self-evident since you wrote out the list above

OK yeah, I see it now. I think I've just got PTSD from the whole "let go of the self-evidence" meme when starting to learn proofs.

Thanks!

Also, is it normal to have to re-read a proof you wrote yourself before you fully "get" it? At least when starting out? I fully understood when I wrote it, went away for ten minutes, and then had to take a minute to understand a part of it again. I mean it's trivial as fuck, and I feel like a bit of a brainlet to be struggling with it.

>Also, is it normal to have to re-read a proof you wrote yourself before you fully "get" it? At least when starting out?
its all practice, and it depends on how much of the proof you've hashed out before actually sitting down to write it, sometimes roadblocks or other issues only appear once you actually sit down and try to formalize everything

Yeah, I ran into that (I originally tried to prove it using a list of x, x+1, etc. but that turned out harder to formalize).

But I meant for proofs you've already written. For me with this proof it was the change that you suggested. It caused me a bit of confusion when I thought "Well, so what if r is not one of those numbers and it's not in the list. We don't want it in the list!", completely forgetting the first part, requiring r to be between 0 and n.

What about 2,3,5?

The difference between 2 and 3 is 1, whilst the difference between 3 and 5 is 2.

I'm confused about the post. The proof may be right but it isn't proving that there aren't more triplet primes. prime triplets are of the form (p, p+2, p+6) or (p, p+4, p+6). so 5,7,11 is another prime triplet. so is 11, 13, 17.

Sorry, I was quoting the question wrong. The actual question in the book says, "The sequence 3, 5, 7 is a list of three primes such that each pair of adjacent numbers in the list differ by two. Are there any more such "triplet primes"?"

Picture is refined version of the proof. I might print it out or something, since it was my first real proof I did all by myself. I know it sounds super silly, but I'm a silly man.

Some nitpicking:
>Since none of the integers in the list is divisible
Since none of the integers in the list are divisible (In one of my homeworks the correct seriously corrected my grammar)

Dont use Let twice in a row.

It is common to restate your assumption in a proof by contradiction:
We proceed by contradiction. Assume that none of the integers {x,...,x-(n-1)} are divisible by n ... (sometimes it just isnt clear what exactly you are assuming)

A list usually starts with its lowest value and goes up:
x,...,x+(n-1)

You should always state what the symbols you are using mean:
Thus we know that [math]q,r \in \mathbb{N}[/math] with [math] r\neq0[/math] exist such that: ...


Also the " but r must be greater than n−1" isnt obivous. You are beginning the contradiction by choosing a fixed x (the first term in your list) and decomposing that, into q*n + r but this doesnt lead to any contradictions the 0 < r < n part is obviously true, but where does it follow that r has to be greater than n - 1?
(example x = 21; n = 10, then x=q*n+r => q=2, r=1)

I know that you mean the right thing and your proof is mostly fine (far better then my first attempts), but I dont think it is obivous to a reader how you could come to the conlusioun that r > n -1.


But dont let any of this discourage you, for me the hardest part at the beginng was writing a cohernt proof down (even if I understood the arguments), it is something you can only learn by doing proofs and rading them.

Thank you, this is all super helpful. What should I use instead of "let" the second time?

Oh, and here is my second attempt. I've added some examples to show my reasoning, but I feel like all I've managed to do it bloat it.

The problem I'm having is moving from the specific cases of x - r = qn contradicting specific examples in the list of numbers supposed not to be divisible, to the general truth of it. I can clearly see that the list of numbers are in the form x - i, where 0

Oh, and triple post here, is:

"Since x−r for every 0

Maybe just an "and" or "Let n be an integer such that x,..., x-(n-1) is a list of integers".
It sometimes is quite tricky to not repeat the same words over and over again, but it is honestly not that relevant.

As a side note you should also clarify when such a list of integers exist, because if n-1 > x your list is empty, the second formulation above circumvents this by implying that the list you choose is a proper list, but this is just aminor things.

This really is a lot clearer.
I didnt see the pic in , but that makes it perfectly clear where the contradiction is.

As I said, these things take time and practice, but that is a nicely readable proof.

OK! To be honest I'm finding it a little hard to distinguish when things are "clear enough" and when they're not, at least in edge cases like this.

Mathematical Logic is my first love, and no mathematical proofs seem really rigorous to me compared to the logical stuff I normally study.

Do you have any good rule of thumb for when something is not clear enough, perfectly clear, and when it's getting too verbose?

Also, what did you think of this attempt:

>Do you have any good rule of thumb for when something is not clear enough, perfectly clear, and when it's getting too verbose?
If you could forget your own proof and read it again you should understand it. (Maybe match the lines acording to how long you needed to figure out each step?)
That is obivously quite a hard thing to figure out but reading other proofs and just practicing more really helps.
This is also dependend on who you are writing the proof for.
If it is homework you have to turn in, the person correcting will be able to understand your logical leaps, so it is usually fine not to explain things that seem obivous to you.
Writing a proof for someone, who is not familiar with the topic is a lot harder and requires a lot more explaining and details.

This is also completly fine, it is obviously a lot more verbose and probably more suited for someone who is unfamiliar with the topic.

OK. Thanks for all the help! I'm just getting started (this being my first proof) meaning I have a lot of stuff to practice, and Velleman's book seems really good so far.

Practicing reading proofs is pretty straight forward, but for practicing writing proofs it's a bit more complicated, since I can't really check myself if they're correct. Do you know of any place where I could post proofs (apart from Veeky Forums) where people wouldn't mind checking them so that they're correct and also follows conventions and all that?

Again, thanks a bunch for taking the time to help me.

Im sorry I, dont know such a place.

But I'm glad that I could help you with the rest.