More prime number mumbo jumbo

Let be the kth prime number. Show that cannot be the perfect square of an integer.

Like most "proof this cannot be", we assume it's true, and then show that it's not possible. So, we rewrite this as:



What's that? A difference of squares?? Factor the right side:


Now we have something we can work with. First, let's replace with 2, since we know 2 is the first prime:



From this, we can deduce that (x+1)(x-1) is divisible by 2, and is thus even. The only way this is possible is if x is odd. (Odd + 1 = Even, but Even + 1 = Odd) This also means that both (x+1) and (x-1) are even. Now, this is where we can find our contradiction. Let's divide both sides by 2. What we are left with on the left side is . We know that 2 is the only even prime number, so all of these numbers must be odd. But, since both (x+1) and (x-1) are even, we have another factor of two on the right side. And since is all odd numbers, it isn't divisible by 2. What does this mean? It means we've made a mistake, and that mistake was our original assumption, that is the square of an integer. Therefore, through assuming it's true and pointing out a contradiction, we've proved that it isn't possible.

Basic probability problem

Here's one from one of my problem solving books:

Let x be an integer randomly selected, such that What is the probability that x is divisible by 7, 11, or both?

This is basically a counting problem, as most probability problems are: We count the total amount of numbers which satisfy the conditions, and divide by the total amount of numbers. So we're looking for the amount of numbers from 1 to 500 which are divisible by 7 or 11 or both. So lets start with 7:
Largest multiple of 7 not greater than 500 is 497 (7 * 71), so there are 71 numbers divisible by 7.
Now for 11:
Largest multiple of 11 not greater than 500 is 495 (11 * 45), so there are 45 numbers divisible by 11.

Now, it would be a mistake to add these together and divide by 500 to say that the probability is . Why?
The reason this is wrong is because we counted the numbers which are divisible by 7 and 11 twice: once when we counted numbers divisible by 7, and again when we counted numbers divisible by 11. To compensate, we have to subtract the amount of numbers divisible by both, so we only count them once.

7 and 11 are prime, so the only numbers which are divisible by both are multiples of 77 (7 * 11):
Largest multiple of 77 not greater than 500 is 462 (77 * 6), so there are 6 numbers divisible by both 7 and 11.
Now we can find our probability:

Quick proof

This is just something I randomly started thinking about, and came up with a short proof for:

Prove that for any multiplication of any positive integers greater than 1, that the product of these numbers and two will be greater than the product of the original numbers, with one of the numbers increased by 1 before multiplying.

Not too hard to show. Let our desired product be:


We wish to show that:



Divide both sides by most of the terms:





Which was one of our givens. If you were proving this, you should probably show it by working forwards instead FROM the given, but I'm not doing that for you. It's easy to see that my steps are reversible.

First problem explanation!

So this is my first problem explanation. I wrote it mostly to help myself, because I need experience writing proofs and stuff like that. (When I find some more time, I'll make the expressions easier to read using latex or something)

Find all prime numbers p such that 32p + 1 is the cube of an integer.
Source: AwesomeMath 2008 Admission Test A (the deadline for passing it in is way overdue, so I figure it's ok to post a solution)

Things you should know beforehand:
Factorizations
Parity operations (Even * even = ?, Odd + even = ? Stuff like that)
Properties of prime numbers and prime factorizations

Rewrite this as 32p + 1 = n^3, where n is an integer. Subtract 1 from each side, and we get
32p = n^3 - 1. Using difference of cubes, we can factor the right side as (n-1)(n^2 + n + 1). Now we can work exclusively with the right side for a bit. Realize that this side (n-1)(n^2 + n + 1) must be even for it to be divisible by 32. So let's consider two cases: n is even, or, n is odd.

n is even: (For notation purposes, E is an even number and O is an odd number)
(E - 1)(E^2 + E + 1)
(O)(E + E + 1)
(O)(E + 1)
(O)(O)
O
Therefore, n cannot be even.

n is odd:
(O - 1)(O^2 + O + 1)
(E)(O + O + 1)
(E)(E + 1)
(E)(O)
E
therefore, since n cannot be even, and it is possible for n to be odd, n must be odd.

Let's also keep in mind from our work that (n-1) is even and (n^2 + n + 1) is odd.
We want our final product, (n-1)(n^2 + n + 1), to be divisible by 32. Thinking in term of prime factors, 32 = 2^5. So our product must have at least 2^5, or 5 two's, in its prime factorization. Also keep in mind that since (n^2 + n + 1) is odd, it will have no 2's in its prime factorization, so all of them must come from (n-1). Also, if n-1 has any other prime factors besides 2^5, then when we solve for p by dividing (n-1)(n^2 + n + 1) by 32, p will not be prime.

From this, we can conclude that (n-1) MUST equal 32, because our product must be divisible by 32, and (n^2 + n + 1) MUST be prime, because when we solve for it, it is equal to our p.

Letting n - 1 = 32, n = 33. Plugging n = 33 into n^2 + n + 1, we get 1123. We can easily check 1123 against a list of prime numbers, to discover that it is indeed prime. Therefore, the only prime p which satisfies the original argument is 1123.

Of course, we should always check our solution to make sure it works:

32p + 1 = n^3
32(1123) + 1 = n^3
35936 + 1 = n^3
35937 = n^3
n = cuberoot(35937) = 33