Someonekicked <atouiahmad@[EMAIL PROTECTED]
> wrote:
>
> Referring to an old post in here:
> http://google.com/groups?threadm=MMmdnR7bsatJTuLeRVn-hg%40comcast.com
>
> The question from a preparation book for GRE math subject test was:
> Let x,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:
>
> 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,
2) & 3) always works since over a field a line is uniquely determined
by any two distinct points on it.
> 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.
That's equivalent to comparing the slopes of the lines (through
a common point), an approach which I already mentioned before.
> 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. [...]
That's equivalent to comparing the inverse slopes of the lines.
As I mentioned, one can employ any usual normal form for lines.
> 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.
Over a field any of the usual normal forms for lines may be employed.
However, if n isn't prime then Z/n isn't a field and this breaks down.
E.g. in Z/15 the lines y = 0, 3x = 5y both pass through (0,0), (5,0)
but (5,3) is on the latter but not the former. So over a non-field ring
a line is no longer uniquely determined by two distinct points on it.
> 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)?
Since Z/11 is a field the usual normal forms for lines may be employed.
Using 2) & 3) corresponds to finding two common distinct points on it.
Using 4) corresponds to finding a common point and slope. Noticing that
-5 = 6 is divisible by 3 yields one obvious point (2,0), which then
yields another point (2,0)+(7,-3) = (-2,-3).
The key to understanding is to stop thinking about these as _relations_
among integers (mod n) and, instead, to think functionally, by viewing
Z (mod p) as a field, where one can transfer all the usual arithmetical
intuition, using the usual arithmetic operations and their laws. I've
emphasized this strongly in many prior posts here, see my prior links
in the recent thread [1] that spawned this one.
--Bill Dubuque
[1]
http://google.com/groups?threadm=y8z3aouf00k.fsf%40nestle.csail.mit.edu
|
