Anyone wanna prove this?

Every prime number except 2 and 3 has the form 6q + 1 or 6q + 5 for some integer q. Hint: Use the quotient-remainder theorem to say that n must have one of the forms 6q, 6q + 1, 6q + 2, 6q + 3, 6q + 4, or 6q + 5 for some integer q.

I can never make progress on these damn problems, it seems the only way to do them is if you already know the answer.

Simple.  As noted in the hint all of the integers n have one the form 6q, 6q + 1, 6q + 2, 6q + 3, 6q + 4, or 6q + 5 for some integer q.

Now:
2 and 3 divide 6q i.e. 6q = 0 mod 3 or 6q = 0 mod 2
2 divides 6q + 2
3 divides 6q + 3
2 divides 6q + 4

Now that means that all of the remaining integers including the primes excluding 2 or 3 are of the form 6q + 1 or 6q + 5.

PS Anonymous you really should do your own homework.

Seriously, does that prove that all integers have the form 6q + 1 or 6q + 5? I can think of ones that don't, for instance 6 is of the form 6q.

I try to do my own homework, really, but neither the book nor the teacher is of any help on half of the problems assigned, usually. I have a test this week and I need an understanding of the problems I had to skip.

>>3

primes.

if youre in number theory, or any related proof heavy class, i'd suggest just trying to learn all of the theorems for the sections youve done, or at least the most often used ones. 

get an actual understanding of why the theorems work.  you'll remember a lot more easily, and be more ready to apply them.

as far as how to actually doing the proofs?  a lot of it is just knowing which tricks youve been using a lot, and seeing whihc ones are useful.  its suprisingly hard to teach someone how to go about proving things, which is why your books and professors arent going to be as helpful as youd like.

if you can start understanding the 'why' or 'how' (which come with familiarity more than anything else) of the proof, its much easier to do.  or think of what sort of information would get you the answer you want, and then think of any theorems that would get you that information.

i'll end this lengthy exposition by commenting on your original problem here in the thread, in a lengthy way:

look at the problem:
theres stuff in the form 6q + r, you should almost always be thinking about modular arithmetic or division algorithms when you see that.  it mentions a theorem, and theres primes.

always try to notice if something is a multiple of other numbers in the problem if its relavent.  6 = 2*3

understand what a prime is, useful here is that no prime is a multiple of anything lower than it, and remember what being a multiple of something means in modular arithmetic.

dont know if any of that helped, but im bored and thought id say something.

for all integers n, there exists an integer q such that

n^2 = 4q+1, or n^2 = 4q