## collection of problems

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

rolo91
Posts: 38
Joined: Mon Aug 06, 2012 10:21 am UTC

### collection of problems

I'm trying to do some exercises I found on my university's website. They are suppossed to be basic, but some of them are giving me problems, and I'm worried about it because they shouldn't, as they are aimed to the 1st course, which I recently passed. I plan to do them all, because I feel I'm way down the level of knowledge I'm supposed to have. However, I don't have any place where I can ask for help when I get stuck, so I hope you can help me in those moments:

(In case it's not clear: , they're not homework, I won't show the results to any teacher, I just want to learn to solve them.)

Here's one of them that I can't solve:

I'm supposed to find the smaller natural number X that, when divided by

2,3,4,5,6,7,8,9,10

has to give as remainder

1,2,3,4,5,6,7,8,9

respectively.

That is:
(x-1) is divisible by 2
(x-2) is divisible by 3
(....)
(x-9) is divisible by 10

I can see that x = 2a +1, x = 3b + 2, etc. but I don't know what to do from there.

Any help?

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: collection of problems

What can you say about (x+1)?

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: collection of problems

Would you know how to solve the problem if the list were instead:

2, 3, 5, 7

giving remainder

1, 2, 4, 6

?

Note: This is probably not how you want to solve this problem, but this is an easier version that you should know how to do before attempting your problem.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

rolo91
Posts: 38
Joined: Mon Aug 06, 2012 10:21 am UTC

### Re: collection of problems

CCC wrote:What can you say about (x+1)?

I know (x+1) divides 2,3,4,5,6,7,8,9. and 10.

And as I'm looking for the smaller possible x, intuitively x+1 seems to be mcd(1,2,3,4,5,6,7,8,9); which, looking at prime factors, should be 2³*3²*5*7= 2520

Thus, x must be 2519 and in fact that number satisfies the requirements. The problem is that I don't know how to proof that this:

(x-1) is divisible by 2
(x-2) is divisible by 3
(....)
(x-9) is divisible by 10

implies this:

(x+1) divides 2,3,4,5,6,7,8,9 and 10

z4lis wrote:Would you know how to solve the problem if the list were instead:

2, 3, 5, 7

giving remainder

1, 2, 4, 6

?

Note: This is probably not how you want to solve this problem, but this is an easier version that you should know how to do before attempting your problem.

The problem in that simplified version seems to be the same as in the full version, the only variation is that in your version all the numbers are primes,right?

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: collection of problems

rolo91 wrote:The problem is that I don't know how to proof that this:

(x-1) is divisible by 2
(x-2) is divisible by 3
(....)
(x-9) is divisible by 10

implies this:

(x+1) divides 2,3,4,5,6,7,8,9 and 10

Earlier, you said that:

rolo91 wrote:I know (x+1) divides 2,3,4,5,6,7,8,9. and 10.

How do you know that?

rolo91
Posts: 38
Joined: Mon Aug 06, 2012 10:21 am UTC

### Re: collection of problems

because, if x-(n-1) is divisible by n, then [x-(n-1)]+n = x+1 is divisible by n too. But I would like to be able to express that more... formally.

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: collection of problems

rolo91 wrote:I know (x+1) divides 2,3,4,5,6,7,8,9 and 10.

No, you don't. You know that (x+1) is divisible by 2,3,4,5,6,7,8,9 and 10. It's probably just a typo, but mistakes like that can lead to disaster.

rolo91 wrote:And as I'm looking for the smaller possible x, intuitively x+1 seems to be mcd(1,2,3,4,5,6,7,8,9); which, looking at prime factors, should be 2³*3²*5*7= 2520

I'm not familiar with "mcd", but it appears that you're talking about the lcm - the least common multiple. And yes, you need to show that your technique for finding the lcm of a set of numbers is valid.

z4lis wrote:Would you know how to solve the problem if the list were instead:

2, 3, 5, 7

giving remainder

1, 2, 4, 6

?

rolo91 wrote:The problem in that simplified version seems to be the same as in the full version, the only variation is that in your version all the numbers are primes,right?

Indeed. This version is simpler because it's easy to show that the lcm of a set of primes must be the product of those primes (especially if you assume the Fundamental Theorem of Arithmetic).

rolo91 wrote:because, if x-(n-1) is divisible by n, then [x-(n-1)]+n = x+1 is divisible by n too. But I would like to be able to express that more... formally.

Well, it's pretty obvious if you're allowed to use modular arithmetic.
If a mod n = 0 then (a+n) mod n = 0
Otherwise, you can use the distributive law.
Spoiler:
Let n | a. Then there exists k: a = kn
a + n = kn + n = (k + 1)n
and n | (k + 1)n

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: collection of problems

rolo91 wrote:because, if x-(n-1) is divisible by n, then [x-(n-1)]+n = x+1 is divisible by n too.

rolo91 wrote:But I would like to be able to express that more... formally.

Be careful. There's a trap here.

Laying out a proof formally should mean no more than making sure to write out the steps, one by one, and check them to ensure that there are no errors. The purpose of this is to divide the problem into small parts, each of which are easily checked by someone else (or by yourself); that is, to make any possible error easier to find and to pin down. It does not matter what those steps are, as long as they are correct. Going from

x-(n-1) is divisible by n

to

then [x-(n-1)]+n = x+1 is divisible by n too.

is correct, and is a small enough operation to do in a single step. There's no formality that you can add to that to make it better. (You could probably seperate it into a few smaller steps if you really wanted, but it's not necessary in my view).

Yes, you can make it look more complicated; honestly, you can make anything look more complicated. With a bit of effort, I could take "1+1=2" and rewrite it in a form that looks as complex as you might wish. But what's the point of that? Then most people won't be able to work out what I've done, and for those who can it won't be worth the effort.

If you try to make a proof look more complicated simply because you like complicated proofs, or because you want to look impressive, then that's where the trap comes in. It's twofold; first of all, extra complexity means extra scope for errors, extra opportunity for mistakes. Second of all, it's harder for others to read; the point of writing down a mathematical proof is to communicate it (in an exam, it's to communicate it to your professor) and so you shouldn't be doing anything to make that communication more difficult.

Having said that, take note of PM 2Ring's point about the difference between "divides" and "is divisible by". That is an error, and one that I should have picked up on as well but didn't.

rolo91
Posts: 38
Joined: Mon Aug 06, 2012 10:21 am UTC

### Re: collection of problems

PM 2Ring wrote:
rolo91 wrote:I know (x+1) divides 2,3,4,5,6,7,8,9 and 10.

No, you don't. You know that (x+1) is divisible by 2,3,4,5,6,7,8,9 and 10. It's probably just a typo, but mistakes like that can lead to disaster.

rolo91 wrote:And as I'm looking for the smaller possible x, intuitively x+1 seems to be mcd(1,2,3,4,5,6,7,8,9); which, looking at prime factors, should be 2³*3²*5*7= 2520

I'm not familiar with "mcd", but it appears that you're talking about the lcm - the least common multiple. And yes, you need to show that your technique for finding the lcm of a set of numbers is valid.

Ooops, sorry, those two where typos. Mcd is Spanish for lcm, I forgot to translate it.

CCC wrote:Be careful. There's a trap here.

Laying out a proof formally should mean no more than making sure to write out the steps, one by one, and check them to ensure that there are no errors. The purpose of this is to divide the problem into small parts, each of which are easily checked by someone else (or by yourself); that is, to make any possible error easier to find and to pin down. It does not matter what those steps are, as long as they are correct. Going from

x-(n-1) is divisible by n

to

then [x-(n-1)]+n = x+1 is divisible by n too.

is correct, and is a small enough operation to do in a single step. There's no formality that you can add to that to make it better. (You could probably seperate it into a few smaller steps if you really wanted, but it's not necessary in my view).

Yes, you can make it look more complicated; honestly, you can make anything look more complicated. With a bit of effort, I could take "1+1=2" and rewrite it in a form that looks as complex as you might wish. But what's the point of that? Then most people won't be able to work out what I've done, and for those who can it won't be worth the effort.

If you try to make a proof look more complicated simply because you like complicated proofs, or because you want to look impressive, then that's where the trap comes in. It's twofold; first of all, extra complexity means extra scope for errors, extra opportunity for mistakes. Second of all, it's harder for others to read; the point of writing down a mathematical proof is to communicate it (in an exam, it's to communicate it to your professor) and so you shouldn't be doing anything to make that communication more difficult.

Well, it's not that I want to overcomplicated. My problem is that in some exams I've been warned for not developing enough my explanations, and I don't exactly know were to stop. For example, as PM 2Ring points, here I didn't include a proof to explain how I found the lcm, so... I have to explain that ?

I mean, I guess that for every possible problem you can do, in every step I do things that may have to be proofed. Going to the extremes, it's obvious that I don't need to prove that 1+1=2 every time I add two numbers, nor I have to develop the theory behind matrix multiplication every time I multiply 2 matrices, but.. How can I know where's the point at which I'm expected to stop?

Dopefish
Posts: 855
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

### Re: collection of problems

How can I know where's the point at which I'm expected to stop?

Well, this depends on environment to enivironment, and from prof to prof. Two rules of thumb I've had was that you should always write your proofs so that they could be understood by someone two weeks behind you in the course (so being rather explicit in why such and such a theorem you learned/proved in the past week applies), and the other one I've heard was to always write clearly enough that a bright student from the preceding course could follow your work.

Using that, things like addition/multiplication essentially never need to be proved valid (expect perhaps in the first couple weeks when matrix multiplication is introduced for example), but most intuition-derived things about the material you're presently covering almost certain requires a proof (or at least a careful explanation).

rolo91
Posts: 38
Joined: Mon Aug 06, 2012 10:21 am UTC

### Re: collection of problems

That seems like a good rule.

Ok, thanks to all of you for your help! So far I've managed to solve the rest of the problems without much trouble, if I'm stuck again I'll ask in this thread to avoid cluttering the forum...