Let p and q be distinct primes. There is a proper subgroup J of the additive group of integers which contains exactly three elements of the set {p,p+q,pq, p^q, q^p}. Which three elements are in J?
(A) pq,p^q,q^p
(B) p+q,pq,p^q
(C) p,p+q, pq
(D) p, p^q,q^p
(E) p,pq,p^q
Ans:(E)
The only relevant idea I can think of is using Fermat's little Theorem:
Since p and q are distinct primes,then p^q = p(mod q)
which means p^qp=nq where n could be any integers and of course pq is one of the
element.
But since it's a subgroup of additive group of integers, where is the identity and inverse?
Thanks. Any idea for this question?
GR9367 #55
Re: GR9367 #55
Fact: If Z is the group of integers under addition, then all subgroups of Z are of the form nZ, for some integer n. (Here the notation nZ means {nx  x in Z}.)
Now you know that elements of the subgroup must have a common factor >1, since they are in nZ for n>1. The answer follows by properties of divisibility.
Why is the above fact true? Well, I'll let you check that nZ is a subgroup. Now, if H is a subgroup of Z, and a,b are two nonzero elements of H, consider the equation ax + by = gcd(a,b). It's a basic fact that this equation always has an infinite class of solutions in integers (x,y).
Since a is in H, and b is in H, a + a + ... + a (x times) is in H, and b + b + ... + b (y times) is in H, so ax + by=gcd(a,b) is in H.
If gcd(a,b) = 1 for some a,b in H then 1 is in H, so n*1 = n is in H for every n and H = Z.
If gcd(a,b) > 1 for every a,b in H, then H = nZ for some Z. Why? Well, gcd's are in H as well so gcd's of gcd's are >1 as well, so there is a gcd n of all gcd's which is >1. Every a in H can be expressed as bn for some b by the properties of gcd.
Now you know that elements of the subgroup must have a common factor >1, since they are in nZ for n>1. The answer follows by properties of divisibility.
Why is the above fact true? Well, I'll let you check that nZ is a subgroup. Now, if H is a subgroup of Z, and a,b are two nonzero elements of H, consider the equation ax + by = gcd(a,b). It's a basic fact that this equation always has an infinite class of solutions in integers (x,y).
Since a is in H, and b is in H, a + a + ... + a (x times) is in H, and b + b + ... + b (y times) is in H, so ax + by=gcd(a,b) is in H.
If gcd(a,b) = 1 for some a,b in H then 1 is in H, so n*1 = n is in H for every n and H = Z.
If gcd(a,b) > 1 for every a,b in H, then H = nZ for some Z. Why? Well, gcd's are in H as well so gcd's of gcd's are >1 as well, so there is a gcd n of all gcd's which is >1. Every a in H can be expressed as bn for some b by the properties of gcd.

 Posts: 6
 Joined: Mon Sep 07, 2009 11:23 am
Re: GR9367 #55
Thanks prong, for this method. I didnt know much about using gcd's.
The method I tried was:
Assume p is in the subgroup. Then x1 = p + p has to be in the group as well. Similarly, p + p + ... + p will be in the group, for an arbitrary number of additions. Therefore p + p + ... + p = pq will be in the group, for q number of multiplications.
Now you have two elements out of three {p, pq}.
The last step would be scorn on by mathematicians, but i think its fine for the GRE. Only choices C and E have these two elements. Consider C. Since p + q is in the group, and inverses exist (obviously  its a group) then " p + q + (p)" should be in the group. THis means "q" should be in the group, but its not. So you are left with E.
My reasoning behind including p^q is rather messed up, so i'll not post it here.
Do let me know if there is some fundamental error with my approach, which may have worked here but would fail me elsewhere.
Also, can someone help me with question 63 of this test?
Thanks
The method I tried was:
Assume p is in the subgroup. Then x1 = p + p has to be in the group as well. Similarly, p + p + ... + p will be in the group, for an arbitrary number of additions. Therefore p + p + ... + p = pq will be in the group, for q number of multiplications.
Now you have two elements out of three {p, pq}.
The last step would be scorn on by mathematicians, but i think its fine for the GRE. Only choices C and E have these two elements. Consider C. Since p + q is in the group, and inverses exist (obviously  its a group) then " p + q + (p)" should be in the group. THis means "q" should be in the group, but its not. So you are left with E.
My reasoning behind including p^q is rather messed up, so i'll not post it here.
Do let me know if there is some fundamental error with my approach, which may have worked here but would fail me elsewhere.
Also, can someone help me with question 63 of this test?
Thanks
Re: GR9367 #55
Thanks all. That's really helpful.
goingunder, The way to solve #63 is transformation of polar coordinates.
Since we know x=r*cos(ci) and y=r*sin(ci) > r^2= x^2+y^2
double int( exp((x^2+y^2)dxdy =double int( exp(r^2) r dr d(ci)
=double int( r*exp(r^2)) dr d(ci) where 0<=r<=2 and 0<=ci<=2pi
....
I thought this is enough for you to solve this question.
goingunder, The way to solve #63 is transformation of polar coordinates.
Since we know x=r*cos(ci) and y=r*sin(ci) > r^2= x^2+y^2
double int( exp((x^2+y^2)dxdy =double int( exp(r^2) r dr d(ci)
=double int( r*exp(r^2)) dr d(ci) where 0<=r<=2 and 0<=ci<=2pi
....
I thought this is enough for you to solve this question.