Finding Greatest Integer Divisor for Primes on GRE Math Practice Test

[jammidactyl]

Not so good with the number theory and don't understand #59 and #61 on the practice GRE. Not even really sure where to start with these problems.

http://www.ets.org/Media/Tests/GRE/pdf/Math.pdf

59. A cyclic group of order 15 has an element x such that the set {x^3, x^5, x^9} has exactly two elements. The number of elements in the set {x^13n : n is a positive integer} is 3, 5, 8, 15 or infinite.

Obviously the answer can't be "infinite". Cyclic implies commutative, but don't know how to use this.

61. What is the greatest integer that divides (p^4) - 1 for every prime number p greater than 5? 12, 30, 48, 120 or 240

Does either Fermat's or Euler's theorem apply here somehow?

 

[Data]

From the given info. for 59, you can see that either x^2 = 1 or x^4 = 1 or x^6 = 1. But the order of x has to divide 15, so |x| has to be 1 or 3; 1 is impossible because the given set has two distinct elements. Thus |x| = 3. That means {x^{13n}| n is a positive integer} has exactly 3 elements, since x^{39} = x^{13\cdot 3} = 1 (and no smaller n gives you 1).

For 61 (for primes p>5), Fermat's theorem gives p^4 - 1 \equiv 0 (mod 5), and Euler's gives p^4 - 1 \equiv 0 (mod 12) and p^4 - 1 \equiv 0 (mod 8), so it has to be either 120 or 240 (since lcm(5, 8, 12) = 120).

Furthermore, every prime is congruent to 1, 3, 5, 7, 9, 11, 13, or 15 (mod 16). You can check that the fourth powers of each of these are congruent to 1 (mod 16):

3^4 \equiv (-7)^2 \equiv 1, \ 5^4 \equiv 9^2 \equiv 1, \ 11^4 \equiv (-5)^2 \equiv 1, \ 13^4 \equiv (-3)^4 \equiv 1.

But lcm(16, 120) = 240, so indeed p^4 \equiv 1 (mod 240) for every prime larger than 5.

 

[jammidactyl]

I read your solution before the stealth edit and became even more confused! Seriously though, thank you for the help! I see #59 now... forgot about Lagrange's Theorem applied to a cyclic group. Never would have got #61, though. Thanks again!

 

[Data]

Sorry about the edit! Typos are evil .

A more direct way to see that the fourth power of an odd prime p (in fact, any odd integer, which of course the other argument shows as well) is 1 mod 16:

By Fermat, p \equiv 1 (mod 2), so p = 2k+1 for some k. Then p^2 = 4k^2 + 4k + 1 = 4(k^2+k)+1, and p^4 = 16(k^2+k)^2 + 8(k^2+k) + 1. Here, though, k^2+k is always even. Thus p^4 \equiv 1 (mod 16).