Thread: Divisibility of [(p^2) - 1] by 6,12,24 etc. where p is prime number greater than 5

1. Divisibility of [(p^2) - 1] by 6,12,24 etc. where p is prime number greater than 5

p is a prime number greater than 5

Discuss the divisibility of [(p^2) - 1] by 6,12,24....
Is [(p^2) - 1] always divisible by 6, 12, 24. Yes? No? Why?
What's the logic?

Is this some kind of a series?
Is there a proof?

2. I would suggest a proof by induction when $k\geq 7$ where k is prime for each case.

$P(7):6x=49-1\rightarrow 6x=48$ so $P(7)$ is true

Assume $P(k):6x=k^2-1$ is true

$P(k+1):6x=(k+1)^2-1\rightarrow 6x=k^2+2k+1-1\rightarrow 6x=(k^2-1)+2k+1$

The question is does $6|(2k+1)$ now

3. Not sure, but isn't induction used when you are proving something for n = natural number. Here we have 'p' prime. So induction doesn't seem to be the appropriate method.

4. Originally Posted by swordfish774
p is a prime number greater than 5

Discuss the divisibility of [(p^2) - 1] by 6,12,24....
Is [(p^2) - 1] always divisible by 6, 12, 24. Yes? No? Why?
What's the logic?

Is this some kind of a series?
Is there a proof?
First allow me to generalize and modify your question.
Instead of a prime number $p$, I'll consider an integer $a$ that is relatively prime to 6, and the result will imply the case for $p\geq5$. Also, it's enought to show divisibility by 24 and then it implies divisibility by any divisor of 24, in particular 6, 12, 24.
Begin with $a=\pm 1+6k$ (agree?) for some integer $k$, then square both sides: $a^2=1\pm 12k+36k^2=1\pm 12k\cdot(1\pm 3k)$ (The signs are respectively). Finally, $a^2-1=\pm 12k\cdot(1\pm 3k)$ and either $k$ or $1+3k$ is even, and you have divisibility by 24.
To answer your question: Yes and notice it's not special to primes geater than or equal to 5, but to all integers that are relatively prime to 6.

5. Originally Posted by dwsmith
I would suggest a proof by induction when $k\geq 7$ where k is prime for each case.

$P(7):6x=49-1\rightarrow 6x=48$ so $P(7)$ is true

Assume $P(k):6x=k^2-1$ is true

$P(k+1):6x=(k+1)^2-1\rightarrow 6x=k^2+2k+1-1\rightarrow 6x=(k^2-1)+2k+1$

The question is does $6|(2k+1)$ now
I don't think so ( $2k+1$ is odd, whereas 6 is even). Note that you wrote $6x=k^2-1$ (tacit assumption that $k$ must be odd). You also wrote that $6x=(k+1)^2-1$, but then $k+1$ is even and $(k+1)^2-1$ is odd. So $P(k+1)$ is impossible.

6. To rearrange the question, you want to know when $p^2 - 1 | 3 \cdot 2^n$ for $n = 1,2,3...$

We know that for any such prime, we have $p \equiv 1,-1 mod(4)$ and $p \equiv 1,-1 mod(3)$.

As $p^2 - 1 = (p-1) \cdot (p+1)$ it follows from the above that $p^2 - 1$ is always divisible by $3 \cdot 2^2$.

The really interesting question to ask is when is $p^2 - 1 | 2^n$ for n > 2.

It can be shown that if the equation $x^{2^{n-1}} + 1 \equiv 0 mod(p)$ has a solution $x$ then $2^n |p^2 - 1$, as $2^n | p-1$.

Can you figure out why?

This however doesn't identity all of the primes for which $2^n |p^2 - 1$. The question on when does $p+1 | 2^n$ is pretty tough.

7. Originally Posted by jamix
To rearrange the question, you want to know when $p^2 - 1 | 3 \cdot 2^n$ for $n = 1,2,3...$

We know that for any such prime, we have $p \equiv 1,-1 mod(4)$ and $p \equiv 1,-1 mod(3)$.

As $p^2 - 1 = (p-1) \cdot (p+1)$ it follows from the above that $p^2 - 1$ is always divisible by $3 \cdot 2^2$.

The really interesting question to ask is when is $p^2 - 1 | 2^n$ for n > 2.

It can be shown that if the equation $x^{2^{n-1}} + 1 \equiv 0 mod(p)$ has a solution $x$ then 2^n |p^2 - 1, as $2^n | p-1$.

Can you figure out why?

This however doesn't identity all of the primes for which $2^n |p^2 - 1$. The question on when does $p+1 | 2^n$ is pretty tough.
$p\equiv1\bmod{4}\implies p-1\equiv0\bmod{4}$ and $p+1\equiv2\bmod{4}$. Thus $p^2-1\equiv0\bmod{8}$.

The same applies for when $p\equiv -1\bmod{4}$.

So we then have $3\cdot8\mid p^2-1$ as it was already shown $3\mid p^2-1$.

8. Yeah, I think I missed melese's post where he/she mentioned this.

9. Isn't it impossible for $p>3$ to have $( p^2-1)|2^n$?
$p^2-1=(p-1)\cdot(p+1)$ and when you have two consecutive even integers one of them is not divisible by 4, namely, has an odd divisor greater than 1.
Another thing. If $(p+1)|2^n$, then $p+1$ must be a power of two itself. So a necessary (and sufficient) condition is to have $p+1=2^k$ for some integer $k\leq n$, then it follows that $p$ is a Mersenne prime. Do you agree?

10. @ melese

Brilliant! I understood. The best part was the 'prime relative to 6' part.

@jamix

I don't understand the symbols '|' 'mod' and the 3-lined symbol. Can you please elaborate.

other queries: How do you insert the equations as images?

11. I meant to write $2^n | p^2 - 1$ and $2^n | p+1$.

swordfish....

For writing math symbols, use the TEX button (see LATEX section of this forum for more details).

"mod(p)" means the remainder when an integer is divided by $p$. For example $7 \equiv 2 mod(5)$ because 2 is the remainder upon dividing 7 by 5. You could think of it as $\frac{7}{5} = 1 + \frac{2}{5}$.

The sign "|" is a division sign. For example when I say what is $3 | 12$, I'm asking for "12 divided by 3".

Does this make sense?