Math GRE problem

February 11th, 2005 ~ Posted in: Mathematics

Here’s a problem one of my friends was puzzled by on the Math GRE– I have to admit it’s daunting at first sight:

Let p be prime, p>5. Find the gcd of p^4-1 where p ranges over all applicable primes.

He took the test late last year, and had mentioned it in passing several times, saying he was going to check with the algebra and number theory profs to see how to go about solving it. Today we were waiting outside of a classroom for our Real Analysis test, and the topic came up again, so we sat down and warmed up for the test by solving it together. Although it wasn’t too hard, it still took way more than the 2 and a half minutes you have per problem in the GRE. Admittedly though, the GRE is multiple choice; but in this case, that doesn’t help much, because there was the dreaded “none of the above” option. IMO, this is mathematical competition quality question. Makes me fear the Math GRE :)

He’s going to let me borrow a prep book he has for it, so I can bone up on my number theory/algebra skills.

So, what’s your answer? Ours is past the fold

The whole thing depends on the behavior of p \mod n for an integer n.

Factor (p^4 -1 ) into (p -1)(p+1)(p^2 + 1). Now let’s try to find the highest power of each prime that divides this quantity, starting with 2. Clearly 8=2^3 divides this quantity, because each term is even. Recall that for each prime p, p \mod 4 = 1 or 3, so 4 divides either (p-1) or p + 1 . Therefore 16=2^4 divides it. Moving onto 3, observe that p \mod 3 = 1 or 2 always; therefore 3 divides either p-1 or p+1. For 5: p \mod 5 = 1,2, 3 or 4, and p \mod 5 = 1 \Rightarrow 5 \mid (p-1), p \mod 5 = 2 \Rightarrow 5 \mid (p^2+1), p \mod 5 = 3 \Rightarrow 5 \mid (p^2+1), p \mod 5 = 4 \Rightarrow 5 \mid (p+1), so 5 divides the quantity.

That’s it. To show that no higher powers of these primes are in the gcd, as well as no other primes, you can use the factorizations of 11^4-1 = 14640 = 5 \cdot 16 \cdot 183 and 7^4 - 1 = 2400 = 3 \cdot 800 = 3 \cdot 2^5 \cdot 5^2. Therefore the gcd is 16\cdot 3 \cdot 5 = 240.

This is really ad hoc stuff. Is there more solid theory behind the problem? Also, can you extend this problem for p>7,11,\ldots etc.?

Mathematics ~

One Response to “Math GRE problem”

  • 1. Carl Brannen
    May 18th, 2008 at 7:16 pm

    My approach is to compute 7 and 11. One discovers that the only possible answers are powers of 2 and 1 power of 5. Then I write the prime p as (10n+k), k=1,3,7,9 and compute its 4th power, keeping track of what powers of 2 have to be in the terms. I think your technique is better, but I used to be quite quick at computation.

    Wayyy back [1978] I got a 990 in the Math GRE which was as high a score as they’d give you back then. There are enough easy problems that you have time to work out the hard ones.

    But in general, I think that timed tests are very bad ideas. You end up with grad students biased towards very fast thinkers. That’s really not something that matters much in academia, except for taking tests. I’d rather see the math test have the same number of problems, but last all day long.

This entry was posted on Friday, February 11th, 2005 at 3:40 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply