4
$\begingroup$

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5(this is a gre subject math problem)

I think that $p^4-1=(p^2+1)(p-1)(p+1)$,so 8 must divide all the $p^4-1$ for p>5,then I am stuck in how to continue analyze the question. can someone tell me how to find that greatest integer?

the choice is (A)12 (B)30 (c) 48 (d)120 (E) 240

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Aug 14 '17 at 19:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

10
$\begingroup$

Hint : $p>5$ so $p$ is not divisible by $3$, hence either $p-1$ or $p+1$ is divisible by $3$. So $3$ divides $p^4-1$. So $3$ divides it and $8$ divides it. Added: Notice that $p-1$ and $p+1$ are consecutive multiples of $2$, so one them is divisible by $4$. As Batimovski suggested, you can use Fermat's little theorem to conclude that $p^{4} \equiv 1$ mod $5$. So, we got so far $(p-1)(p+1)$ is divisible by $8$ and $3$, and $p^{2}+1$ is even, so $p^{4}-1$ divisible by $16$, and then by $3$, so by $16 \times 3 \times 5=240$ as they are pairwise comprime, the largest number on your list!

$\endgroup$
  • $\begingroup$ But $5$ and $16$ divide $p^4-1$ as well. $\endgroup$ – Batominovski Jul 3 '15 at 17:28
  • $\begingroup$ Jup, Fermat! ${}{}{}$ $\endgroup$ – mich95 Jul 3 '15 at 17:29
6
$\begingroup$

I would like to promote the idea of calculating with small examples, hoping to see a pattern.

$$ \gcd( 7^4 -1, 11^4 - 1) = 240. $$ $$ \gcd( 7^4 -1, 11^4 - 1,13^4-1) = 240. $$ So, it seems to be $240.$ the others have given enough arguments to show this is the final answer.

My point is that students ought to learn to try easy cases, smaller problems, when they do not see the big picture yet.

$\endgroup$
  • $\begingroup$ oh, thank you for your advice $\endgroup$ – python3 Jul 3 '15 at 17:42
  • $\begingroup$ This is especially good advice for a time-sensitive environment, like the GRE test. It's probably much quicker (and more reliable) than figuring out how exactly many of what primes must divide $p^4 - 1$. $\endgroup$ – pjs36 Jul 3 '15 at 18:05
4
$\begingroup$

You correctly observed that $8$ must divide the number. However, $16$ must also divide it, since one of $p- 1 $ or $p+1 $ is a multiple of $4$. Furthermore, $16$ is the largest power of $2$ that divides the number, since $p^2 +1$ is never a multiple of $4$.

$3 $ divides our number since $p $ is not a multiple of $3 $ and thus one of $p+1 $ or $p-1$ is a multiple of $3 $. $9$ does not divide the number, since $p^2+1 $ is never a multiple of $3 $.

$p^4-1$ is always a multiple of $5 $ by Fermat's Little Theorem. $25 $ isn't always a divisor. For example, $29^4-1\equiv 4^4-1\equiv 5 \pmod{25}$ .

For any larger prime, $p\nmid p ^4-1$, so the answer finally becomes:

$$ 16\cdot 3\cdot 5=240$$

$\endgroup$
  • 1
    $\begingroup$ Typing LaTeX on mobile is painful, so do tell if I made a mistake $\endgroup$ – SBareS Jul 3 '15 at 18:09
  • $\begingroup$ oh, you are right,thanks $\endgroup$ – python3 Jul 3 '15 at 19:18
2
$\begingroup$

If $q|(p^4-1),$ where $p>5,q$ are primes,

clearly, the greatest factor has to be of the form $N=2^{a+1}3^{b+1}5^{c+1}$ where $a,b,c$ are non-negative integers

Now, Carmichael Function $\lambda(2^{a+1}3^{b+1}5^{c+1})=$lcm$(2^{a-1},(3-1)3^b,(5-1)5^c)=3^b5^c2^{\text{max}(a-1,1,2)}$ which we need to be $4$

$\implies b=c=0,a-1\le2\iff a\le3$

So, $N_{\text{max}}=N=2^{3+1}3^{0+1}5^{0+1}$

$\endgroup$
1
$\begingroup$

In general, let $d$ be a natural number and $f(d)$ the greatest common divisor of all numbers of the form $p^d-1$, where $p\geq d+2$ is a prime integer. Denote by $g(d)$ the product of all numbers of the form $q^k$, where $q$ is an odd (positive) prime and $k$ is the largest positive integer such that $q^{k-1}(q-1)$ divides $d$. We also define $$h(d):=\left\{\begin{array}{ll} 2 & ,\text{ if }d\text{ is odd}\,, \\ 2^{k+2} & ,\text{ if }d\text{ is even and }k\text{ is the largest exponent of }2\text{ in the factorization of }d\,. \end{array}\right. $$ Then, I claim that $f(d)=g(d)\cdot h(d)$.

First, we shall verify that $g(d)$ and $h(d)$ divide $f(d)$. For $g(d)$, we have to invoke Euler's totient function and Euler's Theorem. For $h(d)$, if $d$ is odd, the claim is trivial, and if $d=2^ks$ with $s$ being odd, then $p^d-1=\left(p^s-1\right)\left(p^s+1\right)\cdot \prod_{i=1}^{k-1}\,\left(p^{2^is}+1\right)$, and we see that $8=2^3$ divides $\left(p^s-1\right)\left(p^s+1\right)$, whereas $2$ divides each $p^{2^is}+1$ for $i=1,2,\ldots,k-1$. Hence, $g(d)\cdot h(d)\mid f(d)$, as desired.

Now, we claim that $f(d) \mid g(d)\cdot h(d)$. First, if $f(d)$ is divisible by $q^k$, where $q$ is an odd (positive) prime and $k\in\mathbb{N}$ such that $q^{k-1}(q-1)$ does not divide $d$, then $p^d\equiv 1\pmod{q^k}$ for every prime $p\geq d+2$. Hence, $p^{\gcd\left(d,q^{k-1}(q-1)\right)}\equiv 1\pmod{q^k}$ for all prime $p\geq d+2$. Let $\omega$ be a primitive element modulo $q^k$, then there exists a prime $p\equiv \omega\pmod{q^k}$ (by Dirichlet's Theorem). Hence, $\omega^{\gcd\left(d,q^{k-1}(q-1)\right)}\equiv 1\pmod{q}$. However, due to the definition of $\omega$, we must have $q^{k-1}(q-1)=\gcd\left(d,q^{k-1}(q-1)\right)$, which contradicts the assumption that $q^{k-1}(q-1)$ does not divide $d$. By taking a prime $p\geq d+2$ such that $p\equiv 3\pmod{8}$, we can see that $2^{h(d)}\mid f(d)$ but $2^{h(d)+1}\nmid f(d)$.

In summary, $f(d)=g(d)\cdot h(d)$ for every $d\in\mathbb{N}$. Note that, if $d$ is odd, then $g(d)=1$, whence $f(d)=2$ for all odd $d$. For example, if $d=12$, then $h(d)=2^{2+2}=2^4=16$ and $g(d)=3^2\cdot 5\cdot 7\cdot 13=4095$. That is, $f(d)=2^4\cdot 3^2\cdot 5\cdot 7\cdot 13=65520$.

$\endgroup$

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