algebra (?) number theory
Someonekicked
solved (the book im preparing with does not have solutions).
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
The answer in the book is (d), but dunno how they got it?
(I was looking in my number theory book and read about the linear
Diophantine equation, but im not sure if I should apply it in here!?)
quasi
It's a trick question.
The key word in the problem is the word "positive".
The problem can be done in your head -- no sophisticated math
required.
quasi
vaishakh
try and report after two days if you still couldn't solve it.
quasi
Try 11. Fails, right?
Try 22. Works with x=3, y=1.
Substituting these must eliminate all but one answer, assuming the
problem has exactly one correct answer.
Ok, but is there a more analytical way? Sure -- here's a simple,
unsophisticated approach, just a kind of playing around with the
problem usng congruences.
Rewrite the problem this way:
3x + 7y = 11z
This could be viewed as a congruence in any of 3 ways:
3x + 7y = 0 mod 11
11z - 3y = 0 mod 7
11z - 7y = 0 mod 3
If you can satisfy any of these congruences with integer values, you
at least get integer solutions to the original equation. So stay with
integers for now -- we'll worry about positivity later.
The last one is attractive since the modulus is small, and the other
coefficients easily reduce mod 3.
In other words, mod 3, you can replace 11 by 2, or even better by -1,
and you can replace 7 by 1.
Thus, you get the simple congruence
-z - y = 0 mod 3,
or equivalently,
z + y = 0 mod 3.
So any integers z,y satisfying this congruence will yield integer
solutions, but since you need positive integer solutions, you also
need to insure that x is positive, so you want 11z - 7y > 0.
Equivalently, z > (7/11)*y.
Thus choose y=1, z=2. Solving for x gives x=3.
Then proceed as before, substituting these values into the multiple
choice alternatives.
quasi
MuTsun Tsai
Why? The statement holds for negative integers x and y as well, right?
MuTsun Tsai
>
> Try 22. Works with x=3, y=1.
I think you mean x=5, y=1.
> Substituting these must eliminate all but one answer, assuming the
> problem has exactly one correct answer.
Not necessarily of course. Some choice might be correct by coincidence. For
example, if you take x=5 and y=1, then (b) is also correct. You'll probably
have to try many solutions to have only one left.
Well actually since the adjective "positive" is not important, you can try
an even trivial solution, which is x=7 and y=-3. This well indeed eliminate
all but one choice.
MuTsun Tsai
> 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
>
> The answer in the book is (d), but dunno how they got it?
> (I was looking in my number theory book and read about the linear
> Diophantine equation, but im not sure if I should apply it in here!?)
Ok, now let me give a full theoretic explanation for this problem
In general we may ask the following question :
Let x and y be integer such that ax+by==0 (mod m). Find all linear equations
of x and y such that it must be congruent to zero under the assumption.
By CRT ( Chinese Remainder Theorem ), we know that we may only consider the
case where m is a prime number, say p.
Now, the linear congruence equation ax+by==0 (mod p) has the general
solution (x, -b^(-1)ax) in Z/pZ. In the case we've encounter above, the
solution is (x, -2x), since 7^(-1)==8 and 8*3==2 (mod 11).
So our problem is to find all A, B and C such that Ax-2Bx+C==0 (mod 11) for
any x.
Obviously C must be congruent to zero, otherwise take x==0 and you'll have a
contradiction.
So the equation becomes x(A-2B)==0 (mod 11). Take any invertible x, and
you'll have A-2B==0 (mod 11). Obviously this is also sufficient, so our
conclusion is :
Such equations are of the form Ax+By+C, where A-2B==0 (mod 11) and C==0 (mod
11).
Only (d) fits the condition.
quasi
Yes, you're right, positivity is more of a diversion. It's natural to
try to characterize the integer solutions first, by viewing the
requirements in terms of congruences.
I looked at the problem too quickly and thought it was solved
instantly by inspection, seeing that 22 works with x=5, y=1 (by the
way, thanks for the correction -- I meant x=5, not x=3).
In fact, I never even tested the alternatives -- I just assumed they
would be eliminated. Had I actually tested the alternatives, I would
have realized that that I had made a conceptual error, since two of
the choices would have survived my test.
Also, as you point out, if all I wanted was integer solutions, x=7 and
y=-3 are instant solutions which I overlooked. For that matter, x=-7
and y=3 are also instant.
I jumped too quickly on this problem.
Thanks for all the corrections.
quasi
quasi
>On Sat, 19 Nov 2005 21:15:48 -0500, quasi <qu...@null.set> wrote:
>
>>On Sat, 19 Nov 2005 20:39:32 -0500, "Someonekicked"
>><someon...@comcast.net> wrote:
>>
>>>I am preparing for GRE math, and I dont understand how this problem is
>>>solved (the book im preparing with does not have solutions).
>>>
>>>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
>>>
>>>The answer in the book is (d), but dunno how they got it?
>>>(I was looking in my number theory book and read about the linear
>>>Diophantine equation, but im not sure if I should apply it in here!?)
>>>
>>
As MuTsun Tsai's reply makes clear, positivity can't really be
relevant, and hence, a natural way to deal with this problem is to use
the Chinese Remainder Theorem to characterize all integer solutions.
But my previous, more primitive attack can still be salvaged, with
corrections, as follows ...
Rewrite the problem this way:
3x + 7y = 11z
This could be viewed as a congruence in any of 3 ways:
3x + 7y = 0 mod 11
11z - 3x = 0 mod 7
11z - 7y = 0 mod 3
Any complete solution to any these congruences will yield all integer
solutions to the original equation.
The last one is attractive since the modulus is small, and the other
coefficients easily reduce mod 3.
In other words, mod 3, you can replace 11 by 2, or even better by -1,
and you can replace 7 by 1.
Thus, you get the simple congruence
-z - y = 0 mod 3,
or equivalently,
z + y = 0 mod 3.
This is equivalent to z = 3t - y, where t is an arbitrary integer.
Substituting z = 3t - y for z in the original equation 3x + 7y = 11z,
and then solving for x yields
x = 11t - 6y
So the general integer solution to 3x + 7y = 11z is
x = 11t - 6y, y = y, z = 3t-y
Then, substituting x = 11t - 6y into the multiple choices gives
(a) 4x + 6y simplifies to -18y + 44t
(b) x + y + 5 simplifies to -5y + 11t + 5
(c) 9x + 4y simplifies to -50y + 99t
(d) 4x - 9y simplifies to -33y + 44t
(e) x+y-1 simplifies to -5y+11t
Viewed mod 11, the t terms all drop out, but then it's clear, since y
is arbitrary, that only (d) is always a multiple of 11.
So my prior argument is now repaired, but still, I readily admit that
the Chinese Remainder Theorem is the power tool here, and the right
one. By comparison, what I did was just fooling around.
quasi
conra...@hotmail.com
conditions on x and y other than they be positive integers, so if x =
11, and y = 11, then answers a, c, and d are all divisible by 11,
though d is negative; that objection can be removed by choosing x = 44,
right? I contend that, given the phrasing of the question, my answer
is correct; in fact, it is better than all the other replies because I
got more corrct answers than anyone else 8-) Show me where I am wrong,
and I shall meekly grovel at your collective feet... Thanks for
indulging an amateur..
cfe
quasi
The one word in the problem which you are not taking into account is
the word "must".
Try reading the problem again with special emphasis on that word.
quasi
LC Killingbeck
news:MMmdnR7bsat...@comcast.com:
(b) and (e) can be instantly eliminated (x=y=11 fails).
(3x+7y)+(8x+12y)=11x+19y is not necessarily 0 modulo 11. (a) fails
(3x+7y)+(9x+4y)=12x+11y is not necessarily 0 modulo 11. (c) fails.
That leaves (d) by elimination! OK, if not pressed for time, note that
(3x+7y)+(8x-18y)=11x-11y is identically 0 modulo 11. (d) passes.
Just using the fact that if each expression is zero modulo 11, then so
is any sum or difference; and, doing very quick "by inspection" sums
(didn't even need to try differences) such that the coefficients of one
or the other term was a multiple of 11. Is the approach sound?
Lynn Killingbeck
RickO
Maybe this is too brute force. But if you multiply the original
equation by 5 you don't change the divisibility by 11.
So 0 = 3x + 7y = 15x + 35y mod 11 which is just 4x - 9y mod 11.
The rationale for multiplying by 5? I just looked for the smallest
positive number such that 3k = 4 (11) because of (a). Everything then
fell into place for (d). If it hadn't worked, I would have done the
same for (b): the smallest k such that 3k = 1 (11). This would have
lead to x + 6y
When I used to worry about these kind of things, this was my standard
"don't want to think today" approach.
Cheers,
Rick
Peter Schorn
Apart from the more convoluted approaches you can solve problems of this
kind easily using modular arithmetic:
3x + 7y is divisible by 11 can be reformulated as 3x + 7y = 0 (mod 11).
Solve this equation for x by multiplying it with the multiplicative
inverse of 3 (mod 11) which is 4 to obtain 12x + 28y = 0 (mod 11) or
x = -28y = 5y (mod 11). Plug this into the given choices to see:
(a) 4*5y + 6y = 26y = 4y (mod 11) -> not necessarily 0
(b) 6y + 5 (mod 11) -> not necessarily 0
(c) 45y + 4y = 49y = 5y (mod 11) -> not necessarily 0
(d) 20y - 9y = 11y = 0 (mod 11) -> this is it
(e) 5y + y - 1 = 6y - 1 (mod 11) -> not necessarily 0
Peter
quasi
Very sound, and simple too.
But if there are no easily visible eliminations by inspection, then
you would need to bring some kind of reduction method into play as
well.
quasi
quasi
<NOTlynn.k...@NOTsbcglobal.net> wrote:
Ok, here's another method, pairing the first part of your agument with
another idea ...
Since 3x+7y is a multiple 11 of whenever x and y are congruent to 0
mod 11 (for example x=11, y=11), the non-homogeneous candidates are
eliminated.
Now, since Z_11 is a field, we can use linear algebra. Simply consider
the system of 2 equations in 2 unknowns, where the first equation is
3x +7y = 0 and the second is one of the homogeneous candidates.
Then take the determinant of the 2 by 2 coefficient matrix mod 11.
So for example, for (d),
we have the system
3x + 7y = 0
4x - 9y = 0
The 2 by 2 matrix of coefficients is:
3 7
4 -9
with determinant 0 (mod 11)
Hence 4x - 9y is linearly dependent on 3x + 7y over the field Z_11.
Thus, 3x + 7y = 0 implies 4x - 9y = 0, so already this tells you that
if there's only one answer, it has to be (d).
To eliminate the others, use the trick noted by MuTsun Tsai -- namely,
that 3x + 7y = 0 mod 11 has the obvious integer solution x=7, y=-3. In
Z_11, -3 = 8, hence x=7, y=8 must also be a solution. In particular,
x=7, y=8 is a nonzero solution in Z_11, and also a positive integer
solution to the congruence 3x + 7y = 0 mod 11.
So consider the candidate (a) ...
The coefficient matrix is
3 7
4 -9
which has determinant = 1, hence, the system of equations
3x + 7y = 0
4x - 9y = 0
has the unique solution x=0, y=0 in Z_11.
So the solution (7,8) which solves the first equation can't also be a
solution of the the second. Thus, candidate (a) is eliminated.
The same reasoning eliminates (c), which then completes the analysis.
The Chinese Remainder Theorem is possibly hiding in this argument
somewhere, recast in linear algebraic form.
quasi
quasi
The above matrix should have been written as:
3 7
4 6
>which has determinant = 1, hence, the system of equations
>
>3x + 7y = 0
>4x - 9y = 0
The above system should have been written as:
3x + 7y = 0
4x + 6y = 0
>has the unique solution x=0, y=0 in Z_11.
>
>So the solution (7,8) which solves the first equation can't also be a
>solution of the the second. Thus, candidate (a) is eliminated.
>
>The same reasoning eliminates (c), which then completes the analysis.
>
>The Chinese Remainder Theorem is possibly hiding in this argument
>somewhere, recast in linear algebraic form.
>
>quasi
Aside from those 2 corrections, the argument should be ok now.
quasi
conra...@hotmail.com
Connie "The Groveler" Eaton
Someonekicked
(using all ur answers)
The way I would solve it next time, is
Since 3x + 7y is divisible by 11,
then 3x + 7y = 11z;
Now x = (11z - 7y)/3
Note that I can multiply all answers by 3 since (3,11) = 1;
Plugging x in each of the equations multiplied by 3, I get
(A) 44 z - 28y + 18 y = 44 z - 10y
(B) 11z - 7y + 3y + 15 = 11z - 4y + 15
(C) 99z - 63z + 12y = 99z - 51y
(D) 44z -28y -27y = 44z - 55y <<<< (I would stop here and answer D!)
Someonekicked
"Someonekicked" <someon...@comcast.net> wrote in message
news:OqOdnfhmzIL...@comcast.com...
LC Killingbeck
dnblqZ4MPPR3en...@comcast.com:
Just a couple of comments. (1) If the GRE is a timed multiple-guess exam,
and you need to scribble that much algebra on paper to do the above, it
may well be too slow to finish the whole exam. This is a "few seconds, in
your head" problem. You might use another responder's idea (note that
(3,-7) is trivially true, and adjust to (3,4) if you want the "positive"
constraint), and then just substitute these specific numeric values. The
multiplicative inverse idea is also very fast mental arithmetic (3*2
isn't, 3*3 isn't 3*4=12==> 1 is, so change 3x+7y into x+6y first). My
hit-and-miss approach to find a sum that was a multiple of 11 was very
fast, and will work on the exam since the numbers will be very small
integers. ["learning the exam" more than "learning the material"]
(2) Be sure that the question "which..." really means "which -one- ...",
and not "which -one or more- ...". If the latter, you would need to
consider (e) also, and not stop after finding one answer. [more
"learning the exam"] If the former, consider plugging into the
potential answers in reverse order. [(e) is trivially not, so you only
need to evaluate (d)] Should not reduce the amount of work, with an
exam with randomly scrambled answers, but a "might help, can't hurt"
approach.
Lynn Killingbeck
Gerry Myerson
"Someonekicked" <someon...@comcast.net> wrote:
> I am preparing for GRE math, and I dont understand how this problem is
> solved (the book im preparing with does not have solutions).
>
> 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
The mathematics has been pretty well explored in this thread,
so here's something of a historical note.
The Eotvos contests for Hungarian students in their last year
of high school began in 1894. The first problem on that first
exam was,
Prove that the expressions 2x + 3y and 9x + 5y are divisible by 17
for the same set of integral values of x and y.
See Hungarian Problem Book 1, which was Volume 11 in the
New Mathematical Library, published in 1963.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Bill Dubuque
>Someonekicked <someon...@comcast.net> wrote:
>>
>> I am preparing for GRE math, and I dont understand how this problem
>> is solved (the book im preparing with does not have solutions).
>>
>> 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
>>
>> The answer in the book is (d), but dunno how they got it?
>> (I was looking in my number theory book and read about the linear
>> Diophantine equation, but im not sure if I should apply it in here!?)
>
> It's a trick question. The key word in the problem is the word "positive".
No, "positive" is not the key word. Rather, it is a red herring
since any congruence class (mod 11) has a positive representative.
But the implication 3x + 7y == 0 -> ax + by == 0 (mod 11)
depends only upon the congruence classes of x and y (mod 11).
The key is to convert it from a relational form (divisibility)
to functional form: 11 | ax+by <-> ax+by = 0 in the field Z/11
Therefore the problem amounts to comparing two lines over a field.
This is something one should have learned how to do in grade school.
Line 3x + 7y = 0 is determined by its "obvious" points (0,0),(-7,3).
But (-7,3) = (4,3) lies on only one other line, namely the line d,
which need only be verified for a,c,d since (0,0) excludes b,e .
Or one may verify this at a simpler point (4n,3n), e.g. n=3: (1,-2).
Of course there are many well-known ways to compare lines over a field
besides comparing points, e.g. compare the parameters of the line in
some normal form (e.g. slope and intercept), scale the lines by
nonzero factors that equalize a particular coef of each, etc.
--Bill Dubuque
Bill Dubuque
>Someonekicked <someon...@comcast.net> wrote:
>>
>> 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
>
> The mathematics has been pretty well explored in this thread,
> so here's something of a historical note.
>
> The Eotvos contests for Hungarian students in their last year of
> high school began in 1894. The first problem on that first exam was
>
> for the same set of integral values of x and y.
Both sets comprise the (unique) line "between"
the two points (0,0),(3,-2) over the field Z/17.
Yet another example of the power of uniqueness theorems
for proving equalities. See my prior posts for more examples:
http://google.com/groups?q=author:dubuque+uniqueness
--Bill Dubuque
john_r...@sagitta-ps.com
Because whatever is true or otherwise in this respect for positive
integers is the same regardless of sign, we can disregard the word
"positive".
Then, as 3x + 7y = 3(x-7) + 7(y+3), the respective cases require 11
to divide the number following the bracketed term on the RHS of the
following:
(a) 4(x-7) + 6(y+3) = (4x + 6y) - 10
(b) (x-7) + (y+3) + 5 = (x + y + 5) - 4
(c) 9(x-7) + 4(y+3) = (9x + 4y) - 51
(d) 4(x-7) - 9(y+3) = (4x - 9y) - 55
(e) (x-7) + (y+3) - 1 = (x + y - 1) - 4
If this is a multiple choice exam, you can now confidently just
pick (d) by elimination.
To _prove_ that (d) has the stated property, you can note that
3.(-1) + 7.1 = 1 implies that every integer x, y such that 11
divides 3x + 7y is as follows for some pair of integers p, q,
and conversely for any pair p, q these expressions for x, y
do always render 3x + 7y divisible by 11:
x, y = 7p - 11q, 11q - 3p
and plugging these expressions into 4x - 9y does indeed give
an algebraic multiple of 11:
4x - 9y = 11.(5p - 13q)
(Apologies if this is almost identical to someone else's
solution. But like a lot of people, when tackling problems
such as this I deliberately try to avoid looking at other
posts beforehand!)
Cheers
John R Ramsden (jhnr...@yahoo.com.uk)
* Remove m from com to reply
* From address is defunct
john_r...@sagitta-ps.com
john_r...@sagitta-ps.com wrote:
>
> [...]
>
> To _prove_ that (d) has the stated property, you can note that
> 3.(-1) + 7.1 = 1 implies that every integer x, y such that 11
Woops - I was typing from notes relating to a different problem
(a kind of hybrid of yours and the one Gerry Myerson mentioned).
Anyway, here's a correction:
To prove that (d) has the stated property, you can note that
3(-2) + 7.1 = 1 implies that every pair of integers x, y such
that 11 divides 3x + 7y is as follows for some pair of integers
p, q. Conversely for any pair p, q these expressions for x, y
do always render 3x + 7y divisible by 11:
x, y = 7p - 22q, 11q - 3p
Plugging these expressions into 4x - 9y does indeed give an
algebraic multiple of 11:
4x - 9y = 11.(5p - 17q)