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?

Easier way:

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

Fermat's Little Theorem says p-1 is divisible by 2, p^2-1 is divisible by 3, p^4-1 is divisible by 5. So, the answer must be divisible by 2x3x5. Moreover, the answer has 4 factors of 2 because (p^2-1), (p-1), and (p+1) gives three factors of 2 and the pair (p-1), (p+1) are consecutive even numbers so one of them is a multiple of 4 giving the fourth factor of 2.

--

-kira

.

Relevant Pages