Help me figure out this property of prime numbers

Factual Questions
1

It’s been a long time since my last formal math course in college, and I haven’t really done proofs since high school. This isn’t a homework question, but when I mentioned it to my sister in law who teaches 6th grade math, she wants to make it one…if we can figure it out.

It seems that for every prime number p (except 2 and 3), pp-1 is divisible by 24. Which I thought was pretty weird. So I started working through explaining each the prime factors of 24: 2223.

Divisible by 2 is easy. After 2, all primes are odd, and odd times odd is odd, pp will be odd, therefore pp-1 is even. That’s one factor down.

Divisible by 4 is almost as simple, and can be explained geometrically. Take a square that is p by p, and remove one cell from the corner. Then remove the entire column that held the missing cell. Now you have two rectangles: p-1 x p, and 1 x p-1. You can rotate the second rectangle and attach it to the bottom of the first to create a rectangle of p-1 x p+1. (I later remembered from high school algebra that xx-yy always equals (x+y)(x-y).) Since p is an odd number (when higher than 2) then p-1 and p+1 are both even. The product of two even numbers is divisible by 4. (Clearly, this doesn’t work when p=2.) Another factor down.

Describing divisible by 3 is giving me more difficulty. And that third factor of 2 is just weird. I’ve run the numbers for all primes under 1 million, and pp-1 is divisible by 3 when p >= 3, as well as 8 when p >= 5. I’m thinking it can be explained by again using differences of squares, or maybe looking at pp-1 in a third dimension somehow, but I’m getting nowhere.

So there’s the two questions. (1) Why is pp-1 divisible by 3 when p is a prime greater than 3, and (2) why is pp-1 divisible by 8 when p is a prime >= 5?

(I came across this weirdness when playing around with a new board game idea. I knew that board games would some day have a positive effect on me! :cool: )

2

7*6 is 42. The nearest multiple of 24 if 48. Close but no cigar. Besides 5 did you actually test this on any other primes?

3

I did that at first, too. The OP means p^2 - 1, not p*(p-1). 7*7 - 1 = 48, which works, as stated.

4

ftg, I think he means (pp)-1, not p(p-1).

Other than that, I have nothing to add but curiosity.

ETA: Looks like someone beat you to it.

5

There’s probably more elegant ways to do this, but:

Factor of 3:

Your prime is either congruent to 1 or 2 modulo 3:

p = 3m+1 or 3m+2 for some value of m.

(3m+1)^2 - 1 = (9m^2 + 6m + 1) - 1 = 9m^2+ 6m, divisible by 3
(3m+2)^2 - 1 = (9m^2 + 6m +4) - 1 = 9m^2 + 6m + 3, divisible by 3

Try the same thing with allowable congruences for 8.

ETA:

Or start with the fact in the last post which crossed mine, except you should then dig into why that is.

6

If p is a prime not equal to three, it’s not divisible by three. The only other possibilities are that p = 3k + 1 or p = 3k + 2 for some integer k. (3k + 1)[sup]2[/sup] - 1 is equal to 9k[sup]2[/sup] + 6k, which is always divisible by three. (3k + 2)[sup]2[/sup] - 1 is equal to 9k[sup]2[/sup] + 12k + 3, which is also always divisible by three. Therefore, p[sup]2[/sup] - 1 is divisible by three for any prime p other than three.

With regards to division by 8, if p is of the form 8k + i and i is odd, a similar argument can be used to directly show that p[sup]2[/sup] - 1 is divisible by 8. When i is even, it fails; I’m not sure how to correct it.

7

Excuse the goof in the expansion of (3m+2)^2. (3m+2)^2 = 9m^2 + 12m + 4, of course, but the argument still works.

8

This is easiest to think of in terms of modular arithmetic. Let’s do divisibility by 3. Let n be any integer. Now divide n by three and you get a whole number, call it k, and a remainder, which is either 0, 1 or 2. So we can write

n = 3k
n = 3k+1
or
n = 3k+2

Another way of expressing this idea is that every number n is either a multiple of three (remainder 0), one more than a multiple of three (remainder 1) or two more than a multiple of three (remainder 2).

Now think about nn:

nn = (3k)(3k) = 3(3kk)
(3k+1)(3k+1) = 9kk + 6k + 1 = 3(3kk + 2k) + 1
(3k+2)(3k+2) = 9kk + 12k + 4 = 9kk + 12k + 3 + 1 = 3(3kk + 4k + 1) + 1

What do we see here? Well, if n isn’t a multiple of 3 then nn is one more than a multiple of three. Now every odd prime number which is different from 3 is not a multiple of 3. Let p be a prime, p > 3. The above argument implies that pp-1 is a multiple of 3. (Because pp is one more than a multiple of 3.)

You can do something similar to show that pp-1 is a multiple of 8. Let n be any positive integer. Then n takes one of the following forms:

if n is exactly a multiple of 8: n = 8k
if n is 1 more than a multiple of 8: n = 8k+1
if n is 2 more than a multiple of 8: n = 8k+2
:
:
if n is 6 more than a multiple of 8: n = 8k+6
if n is 7 more than a multiple of 8: n = 8k+7

Now, you do the same thing as above when you thought about multiples of 3. Of course, you know that your number is odd, so it has to have an odd remainder. That is, the remainder must be 1, 3, 5 or 7. (You know the remainder cannot be even, because a multiple of 8 plus an even number is also even.)

Here’s what you do if n = 8k+5:

n=8k+5
nn = (8k+5)(8k+5) = 64kk + 80k + 25 = 64kk + 80k + 24 + 1 = 8(8kk + 10k + 3) + 1

So if n is 5 more than a multiple of 8 then nn is 1 more than a multiple of 8. So nn-1 is a multiple of 8.

Clear like mud? :slight_smile:

In general, the number doesn’t have to be prime. It just has to be odd and not a multiple of 3 or 8. So for example:

11-1 = 0 = 024

(25)(25)-1 = 625-1 = 624 = (26)(24)

9

That’s because if n=8k+i and i is even then both n and n[sup]2[/sup] are even. Hence n[sup]2[/sup]-1 is odd and not divisible by 8.

If we restrict to prime numbers, which we need not do, then there are very few even primes and we may consider them case by case. :smiley:

10

atomicbadgerrace, thanks for that link! I had no idea about primes being expressed as (6n +/- 1).

I’m still reading through the answers, but yabob’s and ultrafilter’s explanations seem to do the trick.

With p*p-1 you evaluate the multiplication before the addition. In the absence of parentheses, you always evaluate multiplication and division before addition and subtraction.

…Which is actually kind of funny, since my sister in law is currently working with students who struggling with operator precedence, which kind of brings it back to another item in my OP. :slight_smile:

11

:cool:

12

Maybe a bit shorter, your prime p = 2n + 1 for some n.

pp - 1 = (2n + 1)(2n + 1) - 1 = 4 * n * (n + 1)

Either n or n + 1 are going to be even so there’s your missing factor of 2.

If neither n nor n + 1 are multiples of 3, then there must be some m where n = 3 * m + 1. Unfortuantely, that means p = 6 * m + 3, which wouldn’t be prime, so either n or n + 1 are multiples of 3.

Fascinating.

13

I don’t think I made this clear, but this isn’t really a property of prime numbers. It’s actaully a property of odd integers which aren’t divisible by three. The reason it looks like a property of prime numbers is that there are quite a few small double primes, which skews the sampling.[sup]*[/sup] In order for n to be odd and not a multiple of 3, it has to be either one more or one less than an even multiple of 3. Let’s take a look at the small numbers which have this property. I’ll list the even multiples of 3, typed small to be unobtrusive, together with the number one more and one less than. I’ll italicize the prime numbers and make the composite numbers (except multiples of 3) bold so they stand out.

5 6 7…11 12 13…17 18 19…23 24 25…29 30 31…35 36 37…41 42 43…47 48 49…53 54 55…59 60 61…65 66 67…71 72 73…77 78 79…83 84 85…89 90 91…95 96 97…101 102 103…107 108 109…113 114 115…119 120 121…

Notice how far you have to go before you get to two odd composite numbers in a row which aren’t multiples of three? Madness, I say, sheer madness!

[sup]*[/sup] Of course, all twin primes are going to be of the form 3k-1 and 3k+1. It just happens that they tend to cluster around the small numbers; primes of any sort being a bit thin on the ground as you get into larger and larger numbers.

14

Right, ok, because with 3k+1 and 3k+2 the square of the offset is always 3k+1.

11 = 1 can be expressed as 3k+1 (where k=0), and 22 = 4 can as well (where k=1).

Because when you expand (3k+1)(3k+1) to get 9k^2 + 6k + 1 then that third term - the square of the original number’s offset - can always be expressed as 3k+1.

Poor 3k+2 is left in the dust as an artifact of the arithmetic.

There’s a light bulb slowly flickering on above my head. I think it’s one of those compact fluorescent bulbs, so it’ll get brighter eventually. :smiley:

Divisibility by 8 seems to be a different kind of problem, though. Any given number can be expressed as 8k, 8k+1, 8k+2 … 8k+7. It seems to me that it’s far more likely for p*p to be any of those, but it stubbornly hangs onto 8k+1.

It turns out that for any any odd-numbered p, p*p-1 = 8k+1, so yeah, this isn’t limited to primes.

15

Yeah, bummer, eh? Here I was all excited to announce a big primes breakthrough and declare modern cryptography as limp as a wet Kleenix, sending modern commerce and espionage into a tailspin.

Sorry Skald, at least I tried.

16

Both facts in the OP are special cases of Carmichael’s theorem.

17

Expanding on that a bit:
For every number b, there is a smallest number (let us call it L(b)) such that a^L(b) - 1 is divisible by b whenever a and b are coprime (i.e., share no common factors other than 1).

As it happens, we can deduce the following properties regarding the function L:
When x and y are coprime, then L(x*y) is the least common multiple of L(x) and L(y).
When x is a power of a prime p but not divisible by 8, then L(x) = x * (p-1)/p.
Finally, when x is a power of 2 which is divisible by 8, then L(x) = x/4.
From these three clauses, we can readily figure out the value of L at all other numbers, by first factoring them into products of powers of primes.

In particular, L(24) = LCM(L(2^3), L(3)) = LCM(2, 2) = 2, which explains why any number neither divisible by 2 nor 3 will have x^2 - 1 being divisible by 24.
Similarly, L(8) = L(2^3) = 2, which explains why any odd number will have x^2 - 1 being divisible by 8.

18

I think that limiting yourself to prime numbers is a fools game, here. The really interesting property is that for any odd number n, n[sup]2[/sup] is one more than a multiple of 8. This is something that you can actually explain to school children, using a special property of square numbers:

Namely,

n[sup]2[/sup] = 1 + 3 + 5 + 7 + … + (2n-1)

Why is this?

Observe the following diagrams:



*  **  ***  ****  *****  ******
   **  ***  ****  *****  ******
       ***  ****  *****  ******
            ****  *****  ******
                  *****  ******
                         ******

To get from 1[sup]2[/sup] to 2[sup]2[/sup] you add an extra star along the bottom and right hand edges and then one more in the corner. To get from 2[sup]2[/sup] to 3[sup]2[/sup] you add two stars along both edges and then one in the corner. So to get from n[sup]2[/sup] to (n+1)[sup]2[/sup] you add n stars along the bottom and right hand edges and then one more in the corner. That is, the n[sup]th[/sup] square is the sum of the first n odd numbers.

1[sup]2[/sup] = 1
2[sup]2[/sup] = 1 + 3
3[sup]2[/sup] = 1 + 3 + 5
4[sup]2[/sup] = 1 + 3 + 5 + 7
5[sup]2[/sup] = 1 + 3 + 5 + 7 + 9
6[sup]2[/sup] = 1 + 3 + 5 + 7 + 9 + 11
7[sup]2[/sup] = 1 + 3 + 5 + 7 + 9 + 11 + 13

et cetera.

But now let’s just look at the odd squares:

1[sup]2[/sup] = 1
3[sup]2[/sup] = 1 + 3 + 5
5[sup]2[/sup] = 1 + 3 + 5 + 7 + 9
7[sup]2[/sup] = 1 + 3 + 5 + 7 + 9 + 11 + 13
9[sup]2[/sup] = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17
11[sup]2[/sup] = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21

3+5 = 8
7+9 = 16
11+13 = 24
15+17 = 32
19+21 = 40

So to get from one odd square to the next, you add a multiple of 8. Why? Well, 3+5=8. That’s clear. What about 7+9?

7+9 = (3+4) + (5+4) = (3+5) + (4+4) = (3+5) + 8.

Since 3+5 is a multiple of 8, 3+5 + 8 is a multiple of 8, too.

Now 11+13 = (7+4) + (9+4) = (7+9) + 8 is also a multiple of 8.

You can keep going. So to get from one odd square to the next, you always add a multiple of 8. Since the first odd square (1) is one more than a multiple of 8, every other odd square is one more than a multiple of 8, as well. (Because you just keep on adding multiples of 8.)

19

If you just want to prove the facts for the special cases of 8, then there are much easier ways to go about it. E.g., 1, 3, 5, and 7 all satisfy x^2 = 1 (modulo 8), so we can conclude that all odd numbers do.

20

Yeah, but the context of all of this is showing something cool to 6th graders. I was approaching the question first from the perspective of “why is this true” and then from the perspective of “how do you explain it to eleven year olds.” Now, it’s possible that drawing pictures of squares is pitched a bit low for the 6th grade set. It’s almost certain that algebra is going to be above their heads, so most of the discussion above is right out. I’m sure you could talk about modular arithmetic, but extending it far enough to talk about this actual problem seems difficult to me.

On the other hand, 6th graders have a good handle on arithmetic, and can surely draw pictures of squares. They can recognize odd numbers and certainly know that anything times two plus one is odd. So… pictures of squares and the like.