Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Efficient way to solve basic high school level number theory questions?

  1. Aug 2, 2010 #1
    I signed up for the coaching service for the GRE and when looked through the questions I struggled with elementary number theory. What's the most efficient way to deal deal with the following kind of questions.

    1. Positive integer Z_1 divided by 7 gives a remainder of 5 and Z_2 divided by 4 leaves a remainder of 3. Some constraint on Z_1 and Z_2 (e.g., they are equal and should be minimum [e.g., Z_1 = Z_2, min(Z_1)], or they should be in a certain range [e..g, Z_1 element of {235-256}], or Z_2 is a defined in terms of Z_1 [e.g., Z_2 = Z_1+2]).

    2. f(x)= (x+2)*(x+7)*(x+8), for x element of Z+. Is f(x) evenly divisible by 9?

    3. x a positive integer and y is an odd positive integer
    Find the remainder when (x+1)*(y+2) is divided by 7

    4. How do I deal with questions that define long numbers with the last few digits similar to the one in the other number, e.g.,
    What's larger: 9000014*131818 or 9000818*131014
     
    Last edited: Aug 2, 2010
  2. jcsd
  3. Aug 2, 2010 #2
    4. What's larger: (n + 0.837)*(0.487) or (n + 0.487)*(0.837)
    is the same as
    What's larger: n*0.487 + 0.837*0.487 or n*0.837 + 0.487*0.837
    is the same as
    What's larger: n*0.487 or n*0.837

    Figure out exactly what I did and when and why that is acceptable to do.
    Note: You did not give any conditions on the value of N. That will matter too.

    Then figure out how you could use this same method for
    What's larger: 9000014*131818 or 9000818*131014.
    The problem looks different, but look at this until you are enlightened.

    Lastly, I don't know how much time or motivation you have, but Engel's "Problem Solving Strategies" is a training manual for math competitions to solve problems at this level or perhaps a bit above these. That is an interesting book if you want to sharpen your skills at solving elementary number theory problems. You might find that in a library if you want to peek at it before ordering a copy for yourself.
     
  4. Aug 2, 2010 #3
    Now I feel stupid. LOL I just stared at the problem but simply expanding it makes it a joke. Thanks for your advice and book recommendation.

    Not sure yet how to find a shortcut to the second one.

    The bold variables are usually small prime numbers.
     
  5. Aug 2, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The most efficient way will be the way you understand.

    We can't help you effectively unless you show us in what ways you already understand to attack these problems. Once you show us that, we can identify things you've overlooked, bits that you could streamline, and so forth.



    I did contest mathematics in school, and I was a good one. One of the insights I developed over time is that finding a "clever" or "efficient" solution is often a waste of time -- if you can see a clear path forward then take it. Don't stop to mull things over it until you estimate it's taking too long to produce results.

    For example, the first half of your question 4 has an, IMO, blatantly obvious path to proceed. If you took it -- not even knowing if it was a useful path -- you would have quickly reproduced Bill's approach to the problem.

    (P.S. you really shouldn't edit content out of your original post -- it can make the thread hard to follow)
     
  6. Aug 2, 2010 #5
    Oh, maybe decomposing the numbers in 4. works.

    (9000000+14)*(131800+818) or (9000000+818)*(131000+14)
    = 9000000*131800+9000000*818+14*131800+14*818 vs. 9000000*131000+9000000*14+818*131000+818*14
    = 9000000*818+14*131800 vs. 9000000*14+818*131000

    It's still not obvious :(


    Ok, I will insert random numbers and try to show my reasoning.
     
    Last edited: Aug 2, 2010
  7. Aug 2, 2010 #6

    Mark44

    Staff: Mentor

    For #2, there are three zeroes, and these numbers are the same as those that divide the polynomial (x + 2)(x + 7)(x + 8).
     
  8. Aug 2, 2010 #7
    Ok, the zeros are -2, -7, and -8, but suppose the questions asks whether one can divide by an arbitrary positive integer.

    My approach to each of the first three problems is to plug in numbers foolishly brute-force style. My goal of this thread is to find an efficient, systematic approach.
     
    Last edited: Aug 2, 2010
  9. Aug 2, 2010 #8

    Mark44

    Staff: Mentor

    The zeroes are the only real numbers that divide (x + 2)(x + 7)(x + 8). IOW, if a is a zero of a polynomial function p(x), then a|p(x) (a divides p(x)).
     
  10. Aug 2, 2010 #9

    jgens

    User Avatar
    Gold Member

    Mark, perhaps I'm missing something, but I can't make sense of what you're saying. If p is a polynomial function and p(a) = 0, then x-a divides p(x), but a does not necessarily divide p(x). For example, consider p(x) = x+7; clearly 7 doesn't divide p(x) for all x.

    Edit: By the way, I would solve this problem by noting that it's possible to choose an x such that none of x+2, x+7 and x+8 contain 3 as a prime factor.
     
    Last edited: Aug 2, 2010
  11. Aug 2, 2010 #10

    Mark44

    Staff: Mentor

    jgens, you're right. I guess I was thinking in terms of synthetic division, and I really meant that if f(a) = 0 then x - a divides f(x), which is no help in the OP's problem. Sorry for any confusion this caused.
     
  12. Aug 2, 2010 #11

    Mark44

    Staff: Mentor

    Another stab at #2.
    For some values of x, f(x) = (x + 2)(x + 7)(x + 8) is divisible by 9. For example, f(1) = 3*8*9, is divisible by 9. So is f(2) = 4*9*10. f(3) isn't divisible by 9, but f(4) is. If you check a few values of f(x) you might see a pattern emerging.
     
  13. Aug 2, 2010 #12

    jgens

    User Avatar
    Gold Member

    For problems like number 1, you can probably find solutions using modular arithmetic or by writing out the possible variations and looking for patterns/intersections/etc. which could help solve the problem.
     
  14. Aug 2, 2010 #13
    For 2) f(x)= (x+2)*(x+7)*(x+8), for x element of Z+. Is f(x) evenly divisible by 9? I don't think there's a way out of doing cases. f(x) is divisible by 9 when any one of the terms is divisible by nine or when any two of the terms are divisible by 3. So,
    9|(x+2)when x+2[tex]\cong[/tex]0 (mod 9) or x[tex]\cong[/tex]7 (mod 9)
    9|(x+7) when x[tex]\cong[/tex]2 (mod 9)
    9|(x+8) when x[tex]\cong[/tex]1 (mod 9)
    You have to check also if any two of the terms can be simultaneously divisible by 3.
    So 3|(x+2)when x[tex]\cong[/tex]1(mod 3)
    3|(x+7) when x[tex]\cong[/tex]2 (mod 3)
    3|(x+8) when x[tex]\cong[/tex]1(mod 3)
    So (x+2) and (x+8) are each divisible by 3 when x[tex]\cong[/tex]1 (mod 3).
    So the complete solution is: 9|f(x) when x[tex]\cong[/tex]2,7 (mod 9) or x[tex]\cong[/tex]1 (mod 3).
    Here,"[tex]\cong[/tex]" means congruent (normally this means something like isomorphic).
     
  15. Aug 2, 2010 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's more writing, but less thinking, to simply write a table whose columns are
    • x mod 9
    • x+2 mod 9
    • x+7 mod 9
    • x+8 mod 9
    • f(x) mod 9

    Since 9 = 32, I might attack it mod 3; first write the table whose columns are
    • x mod 3
    • x+2 mod 3
    • x+7 mod 3
    • x+8 mod 3
    • f(x) mod 3
    And then only write the relevant rows into the previous table.

    Oh, hey, those columns are x+2, x+1, x+2. If I had memorized facts about squares mod 3 and mod 9, maybe I could apply them. But a second of thought suggests I don't think I've memorized enough facts though so I'd ignore that lead.
     
  16. Aug 2, 2010 #15
    #3 looks undetermined. The remainder could be anything, since x+1 could be any integer.
    #1 looks like Chinese remainder theorem. Just do algebra, substitutions. Question is a little muddled.
     
  17. Aug 2, 2010 #16
    I clouded the numbers and the wording of the problems because I didn't want to violate any proprietary/closed information of my coaching site's content. That's probably the cause of the ambiguity.
    In any case I appreciate your feedback, so that I can investigate modular arithmetic and the Chinese remainder theorem.
     
  18. Aug 6, 2010 #17
    You replied:
    "= 9000000*818+14*131800 vs. 9000000*14+818*131000
    It's still not obvious :("

    I suspect you may to want to kick your self again.

    9000000*818+14*131800 < 9000000*14+818*131000 ???
    9000000*818-9000000*14< 818*131000-14*131800 ???
    9000000*(818-14)<(818-14)*131000 ???
    9000000<131000 ???

    Now, as I said in my first response, WHY did I do each of those steps?
    WHY was each of those correct to do? WHEN would they NOT be correct?

    I remember reading something vaguely like "The first time you see this it is an incomprehensible trick, the second time you see this it is a brilliant idea, the third time you see this it is an obvious method."

    There is a thin little book titled "Thinking Mathematically", not the more recent thick introductory algebra book by the same title. The original book I believe was meant to teach graduate students how to become algebra teachers, when they had known how to do algebra for so long that they had forgotten how they actually do this or learned to do this. In that book it describes how to become aware of the process, and the failings, that you use to solve problems. It seemed to me to be less whiney and repetitive than Polya's "How to Solve It." I should try to find my copy, or probably just buy another copy. I recommend it to anyone.
     
  19. Aug 8, 2010 #18
    Very transparent. Thanks.

    Often times the solution to a "hard" GRE question looks easy, but going from a state of ignorance to an arbitrary, albeit easy looking, solution is difficult. To show what I mean, consider another practice problem I found on the coaching site:

    C is the remainder when 1032+2 is divided by 11
    (a) C is greater than 3
    (b) 3 is greater than C
    (c) C is equal to 3
    (d) Cannot be determined

    The solution suggests finding the alternating pattern of (10even integer+2)/11 and (10odd integer+2)/11 - by substituting/plugging in small integers into the power. Easy solution, but how do you get the idea of exploiting this particular - seemingly arbitrary - property of numbers - that remainders will be the same for even and odd powers of 10, respectively. You either have to be a genius to know exactly what to do or you have to have a lot of knowledge about the properties of numbers.

    Or, am I missing something? Is there a property that would make me able to master this kind of question?
     
    Last edited: Aug 8, 2010
  20. Aug 8, 2010 #19
    "Remainder" should make you think about modular arithmetic. Modulo 11, 10 = -1; thus 1032 + 2 = (-1)32 + 2 = 1 + 2 = 3 (mod 11).
     
  21. Aug 9, 2010 #20
    How do you reach -1? 10 (mod 11) is congruent to 10.

    EDIT: But also -1 is congruent to it. So you just try to find the simplest form of congruency to do the computations?
     
    Last edited: Aug 9, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook