Prime number

[vvaann]

What is the greatest integer that divides p^4 -1 for every prime number p greater than 5 ?

A. 12
B. 30
C. 48
D. 120
E. 240

Answer key:

SPOILER: E

[reactor]

I have no idea about the problem. The phrase "for every" introduces too much difficulty for me. :-(
The only thing I figured out is that p^4 -1 is an even number (odd^4 = odd, odd -1 = even).

[Dragonfinity]

Okay, this is tough to explain.

First note the theorem that x^(p-1) is congruent to 1 (mod p) where p and x are relatively prime. So, x^4 is congruent to 1 (mod 5), when x is a prime greater than 5; hence, x^4 - 1 is divisible by 5 (or p^4 - 1 is divisible by 5, in the notation used above).

Next, note that p^4 -1 factors into (p^2 + 1)(p^2 - 1). As p is a prime greater than 5, p is odd, so p^2 + 1 is even and divisible by two. So far, we have independent factors of 5 and 2.

Now, we'll show that p^2 - 1 is divisible by 24 = 3*4*2. Using the theorem above, we see that p^2 -1 is divisible by 3. Also, p^2 - 1 = (p + 1)(p - 1). Okay, now this is tricky. Since p is odd, both p + 1, p - 1 are even. But, one is divisible by 2, while the other is divisible by 4. So, we've shown that p^2 - 1 is divisible by 24.

Therefore, we've shown that p^4 - 1 is divisible by 5*2*24 = 240.

[matroid]

That's a nice explanation!

I'd add only one comment: we don't even need Fermat Theorem (x^(p-1) is congruent to 1 (mod p) where p and x are relatively prime). Since f(p) := p^4 - 1 = (p^2 + 1)(p^2 - 1) = (p^2 + 1)(p + 1)(p - 1), and p>5, either (p-1) or (p+1) is divisible by 3. (Otherwise p would be, which is impossible.)

In the same way: if neither (p-1) nor (p+1) is divisible by 5, the p must be congruent to +2 or -2 (mod 5), so (p^2+1) is congruent to 5 or 0 (mod 5).

It's the same idea that Dragonfinity used to prove that f(p) is divisible by not only 4 but 8.

Cheers, Md.

[alamps3]

Originally Posted by matroid

In the same way: if neither (p-1) nor (p+1) is divisible by 5, the p must be congruent to +2 or -2 (mod 5), so (p^2+1) is congruent to 5 or 0 (mod 5).

Can someone expand on why this is true. I don't understand.

[kdilks]

Every number is -2,-1,0,1,2 mod 5. Since p>5, p is not 0 mod 5. If p-1 is not a multiple of 5, then p is not 1 mod 5. If p+1 is not a multiple of 5, then p is not -1 mod 5. So it has to be -2 or 2 mod 5. In both cases, p^2+1 will be 0 mod 5. So at least one of p-1,p+1,and p^2+1 must be divisible by 5.