Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GRE Practice Test Questions

  1. Apr 12, 2007 #1
    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?
     
  2. jcsd
  3. Apr 12, 2007 #2
    From the given info. for 59, you can see that either [itex]x^2 = 1[/itex] or [itex]x^4 = 1[/itex] or [itex]x^6 = 1[/itex]. 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 [itex]x^{39} = x^{13\cdot 3} = 1[/itex] (and no smaller n gives you 1).

    For 61 (for primes p>5), Fermat's theorem gives [itex]p^4 - 1 \equiv 0[/itex] (mod 5), and Euler's gives [itex]p^4 - 1 \equiv 0[/itex] (mod 12) and [itex]p^4 - 1 \equiv 0[/itex] (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):

    [tex]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.[/tex]

    But lcm(16, 120) = 240, so indeed [itex]p^4 \equiv 1[/itex] (mod 240) for every prime larger than 5.
     
    Last edited: Apr 12, 2007
  4. Apr 12, 2007 #3
    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!
     
  5. Apr 12, 2007 #4
    Sorry about the edit! Typos are evil :devil:.

    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, [itex]p \equiv 1[/itex] (mod 2), so p = 2k+1 for some k. Then [itex]p^2 = 4k^2 + 4k + 1 = 4(k^2+k)+1[/itex], and [itex]p^4 = 16(k^2+k)^2 + 8(k^2+k) + 1[/itex]. Here, though, [itex]k^2+k[/itex] is always even. Thus [itex]p^4 \equiv 1[/itex] (mod 16).
     
    Last edited: Apr 13, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: GRE Practice Test Questions
  1. Question in test (Replies: 4)

Loading...