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?

- Jun 27th 2010, 09:33 AMswordfish774Divisibility 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? - Jun 27th 2010, 09:59 AMdwsmith
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 - Jun 27th 2010, 10:41 AMswordfish774
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.

- Jun 27th 2010, 11:04 AMmelese
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. - Jun 27th 2010, 11:17 AMmelese
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.

- Jun 27th 2010, 11:30 AMjamix
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. - Jun 27th 2010, 11:38 AMchiph588@
$\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 $. - Jun 27th 2010, 12:04 PMjamix
Yeah, I think I missed melese's post where he/she mentioned this.

- Jun 27th 2010, 12:16 PMmelese
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? - Jun 27th 2010, 12:30 PMswordfish774
@ 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? - Jun 27th 2010, 12:45 PMjamix
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?