Algebraic proofs of divisibility

[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!

 

[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 ...?

 

[economicsnerd]

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

 

[jbunniii]

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

Good catch, I didn't even notice that.

 

[Mr. Fest]

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 ...?

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...

 

[Mr. Fest]

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

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

 

[jbunniii]

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?

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

 

[Mr. Fest]

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

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?

 

[jbunniii]

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.

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:

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).

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

 

[Mr. Fest]

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

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)

 

[Mr. Fest]

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

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

 

[jbunniii]

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)

OK, sounds right.

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

5, actually. Anyway, I was taking issue with this:

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

"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".

 

[Mr. Fest]

OK, sounds right.

5, actually. Anyway, I was taking issue with this:

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

"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".

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...

 

[jbunniii]

But 8 = 2*4...so if it is divisible by 2 and 4 it is divisible by 8

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.

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...

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.

 

[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.