# Algebraic proofs of divisibility

1. May 7, 2014

### Mr. Fest

Hello,

I have a problem with algebra and divisibility etc. I have a swedish textbook that really sucks. Not a good solutions section and no separate solutions manual either. Just a lot of proofs to show.

At the moment I'm stuck at proofs with divisibility.

I have two examples:

1) Prove that if p is a prime number ≥ 3, then 24 | (p^2 - 1)

2) Prove that if p is a prime number ≥ 3, then 3 | (2p^2 + 1)

How to think and show this.

I know that p can be written as 2k + 1 since all prime numbers larger than 3 are odd numbers.

So in case 1) we have to show that 24 | 4k(k + 1) = 4(k^2 + k). But how?

In case 2) we have to show that 3 | 8k^2 + 8k + 3 = 2(4k^2 + 4k) + 3 so we have to show that 3 is divisible by every other odd number? (This is due to the fact that 2(4k^2 + 4k) is an even number and if we add 3 we get the second odd number after... Again, how to show that the number is always divisible by 3...

In general I'm having trouble with these type of questions...

Hope some of you guys can help me develop my way of thinking...

Thanks so very much in advance!

2. May 7, 2014

### jbunniii

To get started on the first problem, note that $p^2 - 1 = (p-1)(p+1)$. If $p$ is prime and $\geq 3$, then $p$ is odd, so both $p-1$ and $p+1$ are even. Thus $4 | (p^2 - 1)$. But you can actually conclude more than that. In fact $8 | (p^2 - 1)$ because either $p-1$ or $p+1$ must be divisible by ...?

3. May 7, 2014

### economicsnerd

You'll want $p>3$. Note that $p=3$ is a counterexample to both of those statements.

4. May 7, 2014

### jbunniii

Good catch, I didn't even notice that.

5. May 8, 2014

### Mr. Fest

Yeah, I agree that 4 | (p^2 - 1) since it is either divisible by (p + 1) or (p - 1) for all p. Also, 8 | (p^2 - 1) because both (p + 1) and (p - 1) are also divisible by 2. So, 8 = 2*4 | (p^2 - 1) = (p + 1)(p - 1). But the question that remains is how we can show that it is divisible by 24?

24 can be written as 2*2*2*3 or 2*3*4. We have shown that (p^2 - 1) can divided by 2*2*2 = 2*4 but we also have to show that it can be dividied by 3... From the top of my head I get that if p = 7 or 11 we have 3 | p - 1 = 6 and 3 | p + 1 = 12 --> 24 | (p^2 - 1).

But I want to understand how to prove that this is true for all p>3...

6. May 8, 2014

### Mr. Fest

Yeah sorry my bad. Wrote the question wrong. Although I cannot correct my original post...

7. May 8, 2014

### jbunniii

Consider the numbers p-1, p, and p+1. Exactly one of these must be divisible by 3. Can it be p?

8. May 8, 2014

### Mr. Fest

No, it cannot be p since if 3 | p > 3 then p would not be a prime number. And p-1, p, and p+1 three on each other following numbers --> 3 must be a divisor of at least one of them.

This must mean that p^2 - 1 is divisible by 2, 3 and 4 --> it must be divisible by 24.

So, this will be enough to prove that 24|p^2 - 1 given that p is a prime number > 3?

9. May 8, 2014

### jbunniii

No, the implication does not follow. For example, 12 is divisible by 2, 3, and 4, but it is not divisible by 24.

You need to use the fact that p^2 - 1 is divisible by 8 and 3. You just established divisibility by 3. In a previous post, you addressed divisibility by 8, but I'm not convinced by your proof:
You need to argue as follows:
* both p-1 and p+1 are divisible by 2
* one of p-1 or p+1 must be divisible by 4
* therefore, (p-1)(p+1) is divisible by 8

10. May 8, 2014

### Mr. Fest

Isn't that what I did?
You need to argue as follows:
* both p-1 and p+1 are divisible by 2 (because both p-1 and p+1 are even numbers)
* one of p-1 or p+1 must be divisible by 4
Yeah, I agree that 4 | (p^2 - 1) since either (p + 1) or (p - 1) is divisible by 4 for all p
* therefore, (p-1)(p+1) is divisible by 8
8 | (p^2 - 1) because both (p + 1) and (p - 1) are divisible by 2 and since also either p + 1 or p - 1 are divisible by 4 we have that 8 | (p^2 - 1) = (p+1)(p-1)

11. May 8, 2014

### Mr. Fest

Remember that p is a prime number > 3 so the smallest p > 3 is 7...

12. May 8, 2014

### jbunniii

OK, sounds right.
5, actually. :tongue: Anyway, I was taking issue with this:
"is divisible by 2, 3, and 4" does not imply "must be divisible by 24", whereas "is divisible by 3 and 8" DOES imply "must be divisible by 24".

13. May 8, 2014

### Mr. Fest

Haha my bad...but still then p^2 - 1 = 24...

But 8 = 2*4...so if it is divisible by 2 and 4 it is divisible by 8 and also divisible by 3 --> divisible by 24?

But still. We have shown that it is divisible by 8 and 3 why does it become divisible by 24? Sorry if I'm slow and tired at the moment...

Last edited: May 8, 2014
14. May 8, 2014

### jbunniii

No, there are many numbers that are divisible by 2 and 4 but not by 8. Examples: 12, 20, 28, 44, ... So divisibility by 2 and 4 does not imply divisibility by 8. That's why you had to show it directly, by showing that one of the factors of $p^2 - 1$ is divisible by 2 and the other one is divisible by 4. Then the product is divisible by 8.
Consider the prime factorization: divisibility by 8 means that there are at least three factors of 2, and divisibility by 3 means there is at least one factor of 3. Therefore the prime factorization looks like $(2^n)(3^m)\cdots$ where $n \geq 3$ and $m \geq 1$. But $24 = (2^3)(3^1)$ so this shows that 24 is a divisor.

15. May 8, 2014

### xiavatar

His proof is fine. He stated that both p-1 AND p+1 are divisible by two and also either p-1 OR p+1is divisible b 4, so therefore 8|(p+1)(p-1).

He just worded it badly at the end, but otherwise his proof is fine.