Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the greatest integer that divides $p^4-1$ for every prime number $p > 5$? This was on a practice math GRE so it's probably really easy.

share|improve this question

3 Answers 3

up vote 9 down vote accepted

I suppose this is more of a brute force method. By FlT, you know $p^4\equiv 1\pmod{5}$, so $5$ is a factor. Also, factoring, you get

$$p^4-1=(p-1)(p+1)(p^2+1),$$

and since $p$ is odd, each factor is divisible by $2$. Moreover, one of the factors $p-1$ or $p+1$ is divisible by $4$, so $4\cdot2\cdot 2=16$ is another factor. Finally, of the three consecutive integers, $p-1$, $p$, and $p+1$, $3$ is a factor of one. Since $p$ is prime and larger than $5$, $3\nmid p$, so $3|p^4-1$. Hence $16\cdot 3\cdot 5=240$ is a factor of $p^4-1$ for any prime $p\gt 5$.

It still remains to see that $240$ is the greatest such divisor. This can be confirmed by looking at $7^4-1=2400$ and $11^4-1=14640$.

share|improve this answer
2  
A possibly simpler way is that: $p^{16} - 1 = 0 \mod 48$, as $\varphi(48) = 16$. We also have $x^4 + 1 = 2 \mod 4$ for odd $x$. Thus $p^4 - 1 = 0 \mod 48$. Since $p^4 - 1 = 0 \mod 5$ too, it follows that $p^4 - 1 = 0 \mod 240$. –  Aryabhata May 21 '11 at 5:09
    
@Aryabhatta, thanks, I was hoping to see something nicer than what I said. –  yunone May 21 '11 at 5:12
    
@yunone: Unfortunately, looks like the above comment is incorrect. Maybe there is a way to correct it. One other way it that for $p=6k \pm 1$, we have $p^2 - 1 = 36k^2 \pm 12k = 12k(3k\pm 1)$. Which is divisible by $24$ as $k(3k\pm 1)$ is even. Since $p^2 + 1$ is even, $p^4 - 1$ is divisible by $48$. –  Aryabhata May 21 '11 at 6:01
1  
btw, for a 'heavier' proof: en.wikipedia.org/wiki/Carmichael_function. Since $\lambda(240) = 4$, it follows that $p^4 - 1 = 0 \mod 240$. –  Aryabhata May 21 '11 at 6:12
    
That seems to solve it! Thanks :) –  badatmath May 21 '11 at 15:09

$\rm\:p\nmid p^4-1\:$ so $\rm\:2,3,5\:$ are the only possible prime divisors. $240$ is the maximal product of such since $11^4-1 = 122\cdot 120 = 2^4\cdot3\cdot5\cdot 61\:.$ Now, as I mentioned on sci.math on Sep 1, 2003, for every n coprime to $\:2,3,5\:,\:$ hence certainly for every prime > $5$, we have that $\rm\:n^4 \equiv 1\ (mod\ 240)\:$ since $240$ has Carmichael lambda function $\rm\:\lambda(240) = \lambda(2^4\cdot3\cdot 5) = lcm(2^{4-2},\phi(3),\phi(5)) = 4\:.$

See also my my post on Carmichael's generalizations of little Fermat and Euler's phi function, and many applications of such in prior posts. It's well-worth learning these generalizations since they are ubiquitous in number theory.

share|improve this answer

Let $n$ be the number. Then the only prime factors of $n$ are 2,3,5, because any other prime number $p$ doesn't divide $p^4-1$.

So $n=2^a3^b5^c$, and using the fact that $p^2-1 \cong 1 mod 24$, $p^2+1$ is even and $p^4 \cong 1 \mod 5$, the answer is easy to figure..

To finish it:

If $p=5 mod 8$ (13 works) then $p+1, p^2+1$ are $2 \mod 4$ and $P-1 = 4 mod 8$, thus $a \leq 4$.

If $p= 4 mod 9$ (again 13 works) $p^2-1= 6 \mod 9$ and $p^2+1 =8 \mod 9$ thus $b \leq 1$.

If $p= 6 \mod 25$, then $p^2-1= 10 \mod 25$ and $p^2-1= 10 \mod 25$ so $c \leq 1$. I think that actually $p=7$ works nicer in this case....

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.