13
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Aryabhata May 21 '11 at 5:09
  • $\begingroup$ @Aryabhatta, thanks, I was hoping to see something nicer than what I said. $\endgroup$ – yunone May 21 '11 at 5:12
  • $\begingroup$ @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$. $\endgroup$ – Aryabhata May 21 '11 at 6:01
  • 1
    $\begingroup$ btw, for a 'heavier' proof: en.wikipedia.org/wiki/Carmichael_function. Since $\lambda(240) = 4$, it follows that $p^4 - 1 = 0 \mod 240$. $\endgroup$ – Aryabhata May 21 '11 at 6:12
  • $\begingroup$ That seems to solve it! Thanks :) $\endgroup$ – badatmath May 21 '11 at 15:09
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Kind of heuristic but after factoring $p^4-1$, consider the prime factorisation of $240$:

$$240 = 2^4 \cdot 3 \cdot 5$$

The greatest prime here is $5$. Now, observe that our assumption is $p > 5$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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