divisibility of powers of primes

**thomas430** · Oct28-09, 05:37 PM

Hi all,

so I was looking at Legendre symbols, and I saw that $LaTeX Code: \\left(\\frac{2}{p}\\right)=(-1)^{\\frac{p^2-1}{8}}$ .

How does one show that $LaTeX Code: \\frac{p^2-1}{8}$ is always an integer? That is, how can we show that

?

Can a similar method be applied to show that

?

Thanks :-)

Thomas.

**Bingk** · Oct28-09, 07:25 PM

Hi ... I suggest you wiki the Legendre symbol to get a better idea of it ... also wiki the proof for the Second Supplement to the Law of Quadratic Reciprocity.

The idea is this, we know that even numbers are of the form 2n, and odd numbers 2n+1. We can extend this further by showing that 4n and 4n+2 are even numbers, while 4n+1 and 4n+3 are odd numbers (and the combination of 4n, 4n+1, 4n+2, 4n+3 represent the form of any number) ... this is all actually from the division algorithm which states that for any two integers a and b, both greater than 0, there exists another two integers q and r such that a=bq+r where r is less than b and greater than or equal to zero.

So, we can set our a to be a prime number, say p, and we let our b=8. This gives us the following possibilities:
p=8q
p=8q+1
p=8q+2
p=8q+3
p=8q+4
p=8q+5
p=8q+6
p=8q+7

If you look at those equations, you'll notice that 8q, 8q+2, 8q+4, and 8q+6 will give you even numbers, so they cant be odd primes. So you're left with 8q+1, 8q+3, 8q+5, and 8q+7
as the forms of odd numbers (and thus possibly odd primes).

Now, let's take a look at p^2-1 = (p+1)(p-1) where p is one of the possibilities mentioned above.
For:
p=8q+1, (p+1)(p-1) = (8q+2)(8q) = 8q(8q+2), since 8|8, 8|8q(8q+2), then 8|p
p=8q+3, (8q+4)(8q+2) = 8q(8q+2) + 4(8q+2) = 8q(8q+2) + 32q + 8, and if you look at that, all those terms are divisible by 8, so 8|p
You can do the same for the rest ... and you'll see that if a prime is of any of those forms, then it will be divisible by 8.

You might be able to use this method to show 24|(p^3-p), but it will be somewhat tedious ...

**ramsey2879** · Oct29-09, 08:35 PM

Originally Posted by Bingk

You might be able to use this method to show 24|(p^3-p), but it will be somewhat tedious ...

It is not so tedious since 8|p^2 -1 ==> 8|p^3-p. Thus to prove 24|p^3-p we only have to further prove that 3|p(p-1)(p+1)!!

**Petek** · Oct29-09, 09:32 PM

To prove simply that

is much easier than the proof given above. It's understood that p is odd. Therefore, both p + 1 and p - 1 are even. It's easy to see that, given two consecutive even numbers, one of them must be divisible by 4. It follows that the product (p + 1)(p - 1) is divisible by 8. But

, so

is divisible by 8.

Petek

**Bingk** · Oct30-09, 02:19 AM

I meant it would be tedious the way I did it :) ... Referring to thomas430's question if a similar method could be used to prove it :)

Petek, that's great :) ... I didn't realize that LCM could be taken advantage of in that way :). In my defense, I was trying to explain how (p-1)/2 became (p^2-1)/8 (Legendre symbol stuff :))

**thomas430** · Nov3-09, 03:23 AM

Thanks to all of you for your discussion, you've helped a great deal!

Bingk and Petek, your proofs next to one another gave me great insight :-D