Referring to an old post in here:
http://groups.google.com/group/alt.math.undergrad/browse_thread/thread/45c1a88b4c39ae66?tvc=2
The question, taken from a preparation book for GRE math subject test,
was:
Let x and y be positive integers such that 3x + 7y is divisible by
11. Which
of the following must also be divisible by 11?
(a) 4x + 6y (b) x + y + 5 (c) 9x + 4y (d) 4x - 9y (e) x + y -
1
I have a new question about similar problems, but first I will write
down a summary of the previous posts,
**Looking back at the question, and after reviewing all replies, I
guess the "Fastest" approach that one can go about this problem (where
time is very limited in such tests), is proceeding by elimination, as
follows:
1) like most said, "positive", or maybe negative in this regard,
should be directly disregarded.
2) since (0,0) is an obvious solution, then (b) and (e) can easily
eliminated since 5 and -1 are not congruent to 0 mod 11.
3) (-7,3) is also an obvious solution, (a), and (b) can be eliminated.
4) well if 3) did not work, then one can calculate the determinant of
the matrices
for a) |3 7|
|4 6| which gives -10 not congruent to 0 mod 11
for c) |3 7|
|9 4| which gives -51 not congruent to 0 mod 11
so (d) is the answer.
For the record, 2) and 3) were first suggested by Bill Dubuque, 4) was
suggested by quasi.
***Another "fast" approach that was also suggested by Peter Schorn and
MuTsun Tsai is:
we have, 3x + 7y = 0 (mod 11). we wish to write it as x = Ay (mod
11), then substitute Ay in the given choices. To do that, we look for
the inverse of 3 in Z_11, which is 4 in this case, since 3*4 = 12 = 1
(mod 11),
so 3x = -7y (mod 11)
12x = -28y (mod 11)
x = -28y (mod 11)
x = -6y (mod 11)
x = 5y (mod 11)
so replacing that in the choices will give
a) 20y + 6y
b) 5y + y + 5
c) 45y + 4y
d) 20y - 9y
e) 5y + y -1
Obviously the correct answer is d).
My objection to this approach is that sometimes finding the inverse
would not be as fast as in this problem.
My first question is whether step 4) in the first approach might be
needed?
In Burton's Elementary number theory, it is mentioned that if ax = c -
by (mod n), and gcd(a,n) = 1, then there is a unique solution for x
(mod n) for each of the n incongruent values of y (mod n).
Now is it plausible to say that in the worst case, we can have up to
n-1 points, incongruent in the y-coordinate, that validate both Ax +
By = C (mod n), and Dx + Ey = F (mod n), and still Ax + By = C (mod n)
and Dx + Ey = F (mod n) are not equivalent? If it is so, they maybe
that justifies step 4) in the first approach, in the case when C = 0.
My second question is, what if the problem was of this type: Ax + By =
C (mod n), then what is the equivalent of step 4) in the "first
approach".
For example, consider 3x + 7y = -5 (mod 11). To apply the "first
approach". First need to find points as in 2) and 3). take for example
x = -1, so 7y = -2 (mod 11), looking for the inverse of 7 in Z_11
gives 8, so 56y = -16 (mod 11), so y = -5 (mod 11). So (-1,-5) would
be a solution. but how one would go about step 4)?
Thanks in advance!
|
