Number theory question

Forum for the GRE subject test in mathematics.
Post Reply
AcidThinking
Posts: 22
Joined: Thu Sep 08, 2011 11:59 am

Number theory question

Post by AcidThinking » Thu Sep 08, 2011 12:03 pm

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.

blitzer6266
Posts: 61
Joined: Sun Apr 04, 2010 1:08 pm

Re: Number theory question

Post by blitzer6266 » Thu Sep 08, 2011 5:00 pm

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.

YKM
Posts: 45
Joined: Mon Aug 08, 2011 10:25 am

Re: Number theory question

Post by YKM » Fri Sep 09, 2011 2:42 am

What do you got this question from? is it from the past exams?

YKM
Posts: 45
Joined: Mon Aug 08, 2011 10:25 am

Re: Number theory question

Post by YKM » Fri Sep 09, 2011 2:56 am

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.

blitzer6266
Posts: 61
Joined: Sun Apr 04, 2010 1:08 pm

Re: Number theory question

Post by blitzer6266 » Fri Sep 09, 2011 3:10 am

YKM, your logic is terribly wrong... (0, 0, 0) is a solution to both. That doesn't prove anything

YKM
Posts: 45
Joined: Mon Aug 08, 2011 10:25 am

Re: Number theory question

Post by YKM » Fri Sep 09, 2011 5:22 am

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.

YIFCIMS
Posts: 1
Joined: Wed Oct 19, 2011 11:21 pm

Re: Number theory question

Post by YIFCIMS » Wed Oct 19, 2011 11:25 pm

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 32x-40y+16z is divisible by 13. Then you'll work it out.

owlpride
Posts: 204
Joined: Fri Jan 29, 2010 2:01 am

Re: Number theory question

Post by owlpride » Thu Oct 20, 2011 12:29 am

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 rank-nullity 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 rank-nullity, the kernel is 2-dimensional, and these are two linearly independent elements in it, hence a basis.) Both of these vectors lie in the kernel of B, QED.

rimbaud
Posts: 1
Joined: Thu Nov 10, 2011 3:58 am

Re: Number theory question

Post by rimbaud » Thu Nov 10, 2011 4:05 am

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)



Post Reply