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

**swordfish774** · June 27th 2010, 09:33 AM

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?

**dwsmith** · June 27th 2010, 09:59 AM

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

**swordfish774** · June 27th 2010, 10:41 AM

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.

**melese** · June 27th 2010, 11:04 AM

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.

**melese** · June 27th 2010, 11:17 AM

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.

**jamix** · June 27th 2010, 11:30 AM

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.

**chiph588@** · June 27th 2010, 11:38 AM

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

**jamix** · June 27th 2010, 12:04 PM

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

**melese** · June 27th 2010, 12:16 PM

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?

**swordfish774** · June 27th 2010, 12:30 PM

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

**jamix** · June 27th 2010, 12:45 PM

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?

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Prime Divisibility Proof

Divisibility by prime

Prime Numbers and Divisibility

Prime Numbers and Divisibility

Some Prime Number Divisibility Questions

Search Tags