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

Postby rolo91 » Sun Aug 26, 2012 12:29 pm UTC

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

Postby CCC » Sun Aug 26, 2012 12:47 pm UTC

What can you say about (x+1)?

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

Re: collection of problems

Postby z4lis » Sun Aug 26, 2012 1:06 pm UTC

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

Postby rolo91 » Sun Aug 26, 2012 3:38 pm UTC

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

Postby CCC » Sun Aug 26, 2012 5:15 pm UTC

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

Postby rolo91 » Sun Aug 26, 2012 5:29 pm UTC

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.

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

Re: collection of problems

Postby PM 2Ring » Mon Aug 27, 2012 4:43 am UTC

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

Postby CCC » Mon Aug 27, 2012 6:41 am UTC

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


Exactly. You've got your answer, and you've got your proof that it's correct.

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

Postby rolo91 » Mon Aug 27, 2012 4:09 pm UTC

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?

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

Re: collection of problems

Postby Dopefish » Mon Aug 27, 2012 6:27 pm UTC

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

Postby rolo91 » Mon Aug 27, 2012 8:52 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 3 guests