# GRE Practice Test Questions

1. Apr 12, 2007

### 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 [Broken]

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?

Last edited by a moderator: May 2, 2017
2. Apr 12, 2007

### 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.

Last edited: Apr 12, 2007
3. Apr 12, 2007

### 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!

4. Apr 12, 2007

### 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).

Last edited: Apr 13, 2007