Re: a problem in elementary number theory

On 2007-10-30 16:59:39 -0400, "dmitry.sustretov@xxxxxxxxx" <dmitry.sustretov@xxxxxxxxx> said:

Hello,

I am stuck solving this problem from GRE Math training booklet:

Find the maximal integer x such that x divides p^4-1 for all prime
numbers p > 5.

[they actually have a list to choose from: 12, 30, 48, 120, 240]

Do you have any ideas?

My guess is 240.

p^4-1 = (p^2+1)(p+1)(p-1).

So, since p is odd, we see that all three factors p^2+1, p+1, p-1 are even. So, there is at least 3 factors of 2. Moreover, p+1 and p-1 are consecutive even numbers. So, one of them must be a multiple of 4. So, that gives another factor of 2. Hence, the answer must have 2^4. This leave 48 and 240.

Now,
48 = 2^4 x 3,
240 = 2^4 x 3 x 5.
So, we need to see if 5 is always a factor of p^4-1 for p>5. Since p is prime, its unit digit must be 1, 3, 7 or 9. If the unit digit of p is 1, then 5 divides p-1. If the unit digit of p is 3, then 5 divides p^2+1. If 7, then 5 divides p^2+1. If 9 then 5 divides p+1. So, there is a factor of 5.

Thus, this leaves 240.

Of course, I would probably not have gotten it on the test since it took me more than the average 2.5 min. per problem to do this.

--

-kira

.

Relevant Pages