Number theory question

 Posts: 22
 Joined: Thu Sep 08, 2011 11:59 am
Number theory question
4x  5y + 2z is divisble by 13, show 7x +12y + 3z is also divisible by 13. Please I don't want to see a reasonning pulled out of nowhere. Just show me whether there is a procedure that could be applied to any similar question without trial and error.

 Posts: 61
 Joined: Sun Apr 04, 2010 1:08 pm
Re: Number theory question
I'm not gonna give it away but I'll give you a pretty big hint.
The problem is equivalent to
Given: 4x  5y + 2z = 0 (mod 13)
Show: 7x +12y + 3z = 0 (mod 13)
Suppose we weren't working mod 13 and you wanted to show that
Ax + By + Cz = 0 implies that Dx + Ey + Fz = 0
How would you do that in this case. Now just make the adjustment working mod 13.
The problem is equivalent to
Given: 4x  5y + 2z = 0 (mod 13)
Show: 7x +12y + 3z = 0 (mod 13)
Suppose we weren't working mod 13 and you wanted to show that
Ax + By + Cz = 0 implies that Dx + Ey + Fz = 0
How would you do that in this case. Now just make the adjustment working mod 13.
Re: Number theory question
What do you got this question from? is it from the past exams?
Re: Number theory question
Just a quick comment, trial and error is needed in the exam, not every question can be solved nicely. Your question doesn't take long to see that (5,1,1) is an solution, thus the answer.

 Posts: 61
 Joined: Sun Apr 04, 2010 1:08 pm
Re: Number theory question
YKM, your logic is terribly wrong... (0, 0, 0) is a solution to both. That doesn't prove anything
Re: Number theory question
Thanks for showing that. I totally agree that my approach is not rigourous at all and may even be wrong logically, please note that you might not have enough time to do things rigourously in the exam as you only have little more than 2mins for each question.
And, yes you are so correct that using (0,0,0) does not prove anything (so pls don't use it), but a non zero solution does give you some idea in the exam that might lead to the correct answer.
Though I like proofs, GRE is not about rigourous proof in my opinion.
And, yes you are so correct that using (0,0,0) does not prove anything (so pls don't use it), but a non zero solution does give you some idea in the exam that might lead to the correct answer.
Though I like proofs, GRE is not about rigourous proof in my opinion.
Re: Number theory question
Why don't you try to times a whole number to the first equation? With some guess you will get an idea. In this case if you times 8 to the first equation you'll get 32x40y+16z is divisible by 13. Then you'll work it out.
Re: Number theory question
Here's a reformulation of the problem in terms of linear algebra. First notice that it is sufficient to solve this problems with coeffficients and x,y,z from the field $$\mathbb{Z}_{13}$$. Next, consider two linear transformations $$(\mathbb{Z}_{13})^3 \longrightarrow (\mathbb{Z}_{13})^3$$ given by the matrices
$$A = (4, 5,2), B = (7,12,3).$$
The problem asks you show that the kernel of B is a subset of the kernel of A. Notice that both linear transformations have rank 1. If the ranknullity theorem holds for vector spaces over fields with finite characteristic (I am not sure, you'd have to check), then it suffices to find a basis for the kernel of A and check that it lies in the kernel of B.
Well, here's a basis for the kernel of A: (1,1,7) and (0,1,4). (Assuming ranknullity, the kernel is 2dimensional, and these are two linearly independent elements in it, hence a basis.) Both of these vectors lie in the kernel of B, QED.
$$A = (4, 5,2), B = (7,12,3).$$
The problem asks you show that the kernel of B is a subset of the kernel of A. Notice that both linear transformations have rank 1. If the ranknullity theorem holds for vector spaces over fields with finite characteristic (I am not sure, you'd have to check), then it suffices to find a basis for the kernel of A and check that it lies in the kernel of B.
Well, here's a basis for the kernel of A: (1,1,7) and (0,1,4). (Assuming ranknullity, the kernel is 2dimensional, and these are two linearly independent elements in it, hence a basis.) Both of these vectors lie in the kernel of B, QED.
Re: Number theory question
Given: 4x  5y + 2z = 0 (mod 13)
4x  5y + 2z = 4x +13y 5y +2z = 4x + 8y + 2z = 0 (mod 13)
Now, multiply through by 3/2:
0 = 6x + 12y +3z = 7x +12y +3z (mod 13)
4x  5y + 2z = 4x +13y 5y +2z = 4x + 8y + 2z = 0 (mod 13)
Now, multiply through by 3/2:
0 = 6x + 12y +3z = 7x +12y +3z (mod 13)