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

[Helicobacter]

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

 

[Bill Simpson]

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.

 

[Helicobacter]

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.

 

[Hurkyl]

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)

 

[Helicobacter]

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 :(

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.

Ok, I will insert random numbers and try to show my reasoning.

 

[Mark44]

For #2, there are three zeroes, and these numbers are the same as those that divide the polynomial (x + 2)(x + 7)(x + 8).

 

[Helicobacter]

For #2, there are three zeroes, and these numbers are the same as those that divide the polynomial (x + 2)(x + 7)(x + 8).

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.

 

[Mark44]

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)).

 

[jgens]

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.

 

[Mark44]

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.

 

[Mark44]

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.

 

[jgens]

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.

 

[dimitri151]

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 anyone 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$$\cong$$0 (mod 9) or x$$\cong$$7 (mod 9)
9|(x+7) when x$$\cong$$2 (mod 9)
9|(x+8) when x$$\cong$$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$$\cong$$1(mod 3)
3|(x+7) when x$$\cong$$2 (mod 3)
3|(x+8) when x$$\cong$$1(mod 3)
So (x+2) and (x+8) are each divisible by 3 when x$$\cong$$1 (mod 3).
So the complete solution is: 9|f(x) when x$$\cong$$2,7 (mod 9) or x$$\cong$$1 (mod 3).
Here,"$$\cong$$" means congruent (normally this means something like isomorphic).

 

[Hurkyl]

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 = 3², 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.

 

[dimitri151]

#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.

 

[Helicobacter]

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.

 

[Bill Simpson]

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.

 

[Helicobacter]

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.

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 10³²+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 (10^{even integer}+2)/11 and (10^{odd 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?

 

[adriank]

"Remainder" should make you think about modular arithmetic. Modulo 11, 10 = -1; thus 10³² + 2 = (-1)³² + 2 = 1 + 2 = 3 (mod 11).

 

[Helicobacter]

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?

 

[chaoseverlasting]

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.
.

The polynomial is divisible by two, seven, eight for x being a multiple of two, seven, eight. Thus for x=ka (k=const), f(x) is divisible by a.
For the first problem you can write z1=7k+5 an z2=4p+3. If you have to find the minimum condition for which they are equal, you can write 7k+5 as 4k+3k+5=4p+3.

This gives you4k+3k+2=4p.

For the equality to hold, 3k+2 must be a multiple of 4. The smallest such multiple is 8. Thus, for k=2 you have the smallest such number, which would be 7*2+5=19.

For the third problem, at most I guess what you can say is that as y is odd is that the remainder from y+2 will be a multiple 1, 3, 5, but the remainder from x+1 can be any number less than 7. As y+2 can give you a remainder of 1, the final remainder can be any number less than 7.

 

[adriank]

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?

Sure. If you wanted, you could also note that 10² = 100 = 1 (mod 11), so since 2 divides 32, 10³² = 1 (mod 11).

 

[Helicobacter]

"Remainder" should make you think about modular arithmetic. Modulo 11, 10 = -1; thus 10³² + 2 = (-1)³² + 2 = 1 + 2 = 3 (mod 11).

In retrospect I still don't understand this approach. Several things are unclear to me:
I don't understand the syntax of "Modulo 11, 10 = -1"
How did you know that you can change the base by increments of the modulus?

On the RHS, how did you know that 3 comes in front of the (mod 11), in advance? The 3 was never mentioned.
EDIT: Maybe it was carried over from the LHS. However, I read that congruence does not necessarily mean "equal."

I continued the topic of remainders, modulus, and division here:
https://www.physicsforums.com/showthread.php?p=2836712#post2836712