# 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 $\displaystyle k\geq 7$ where k is prime for each case.

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

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

$\displaystyle 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 $\displaystyle 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 $\displaystyle p$, I'll consider an integer $\displaystyle a$ that is relatively prime to 6, and the result will imply the case for $\displaystyle 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 $\displaystyle a=\pm 1+6k$ (agree?) for some integer $\displaystyle k$, then square both sides: $\displaystyle a^2=1\pm 12k+36k^2=1\pm 12k\cdot(1\pm 3k)$ (The signs are respectively). Finally, $\displaystyle a^2-1=\pm 12k\cdot(1\pm 3k)$ and either $\displaystyle k$ or $\displaystyle 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 $\displaystyle k\geq 7$ where k is prime for each case.

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

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

$\displaystyle 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 $\displaystyle 6|(2k+1)$ now
I don't think so ($\displaystyle 2k+1$ is odd, whereas 6 is even). Note that you wrote $\displaystyle 6x=k^2-1$ (tacit assumption that $\displaystyle k$ must be odd). You also wrote that $\displaystyle 6x=(k+1)^2-1$, but then $\displaystyle k+1$ is even and $\displaystyle (k+1)^2-1$ is odd. So $\displaystyle P(k+1)$ is impossible.

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

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

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

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

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

Can you figure out why?

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

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

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

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

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

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

Can you figure out why?

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

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

So we then have $\displaystyle 3\cdot8\mid p^2-1$ as it was already shown $\displaystyle 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 $\displaystyle p>3$ to have $\displaystyle ( p^2-1)|2^n$?
$\displaystyle 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 $\displaystyle (p+1)|2^n$, then $\displaystyle p+1$ must be a power of two itself. So a necessary (and sufficient) condition is to have $\displaystyle p+1=2^k$ for some integer $\displaystyle k\leq n$, then it follows that $\displaystyle 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 $\displaystyle 2^n | p^2 - 1$ and $\displaystyle 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 $\displaystyle p$. For example $\displaystyle 7 \equiv 2 mod(5)$ because 2 is the remainder upon dividing 7 by 5. You could think of it as $\displaystyle \frac{7}{5} = 1 + \frac{2}{5}$.

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

Does this make sense?