Find smallest number when divided by 2,3,4,5,6,7,8,9,10 leaves 1,2,3,4,5,6,7,8,9 remainder.How to go about solving this problem??
Find smallest number when divided by 2,3,4,5,6,7,8,9,10 leaves 1,2,3,4,5,6,7,8,9 remainder
-
0Solve the simultaneous congruences, $x\equiv 1\pmod 2$ $x\equiv 2\pmod 3$$x\equiv 3\pmod 4$$x\equiv 4\pmod 5$$x\equiv 5\pmod 6$$x\equiv 6\pmod 7$$x\equiv 7\pmod 8$$x\equiv 8\pmod 9$$x\equiv 9\pmod {10}$ using [Chinese Remainder Theorem](https://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&sqi=2&ved=0ahUKEwiQ79z0483JAhXHJI4KHS8GDdkQFggbMAA&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FChinese_remainder_theorem&usg=AFQjCNG02olovAm1xRnA4i_03dy4qFlgYw&sig2=SxOkJRuCUklbRkMrnysa5w&bvm=bv.109332125,d.c2E). – 2015-12-09
3 Answers
There is no smallest such number. But there is a smallest positive integer.
Note that $-1$ has the desired property. The integers that have the desired property are all the integers of the form $-1+kM$, where $M$ is the least common multiple of the integers $2,3,4,\dots, 10$ and $k$ ranges over the integers. So the smallest positive integer that works is $M-1$. It is not difficult to find $M$.
Remark: This type of problem is in general much more messy to solve. A specified sequence of remainders may not be achievable, and even when it is, efficiently finding an integer that works involves using the Chinese Remainder Theorem, or some equivalent procedure. In our particular case, finding an integer that works was easy, since $-1$ is clearly a solution. Its only flaw is that it is not positive, but that flaw can be dealt with.
What's going on is easier to see if we use congruence notation. We are told that a certain integer $x$ is congruent to $1$ modulo $2$, congruent to $2$ modulo $3$, congruent to $3$ modulo $4$, and so on up to congruent to $9$ modulo $10$. We can restate these congruences in the form $x$ is congruent to $-1$ modulo $2$, $x$ is congruent to $-1$ modulo $3$, $x$ is congruent to $-1$ modulo $4$, and so on up to $x$ is congruent to $-1$ modulo $10$. So $x=-1$ works for every one of our moduli.
Added details: There is something not very intuitive about the remainder when a negative integer like $-1$ is divided by, say, $6$. The congruence notation is quite helpful here, but we will try to do without. The remainder when the number $a$ is divided by $6$ is the integer $r$ such that $0\le r\le 5$, and there is some integer $q$ such that $a=6q+r$.
Apply this definition to $a=-1$. Note that $-1=6q+r$, where $q=-1$ and $r=5$. So the remainder when $-1$ is divided by $6$ is $5$. The same sort of argument works for all the numbers $2$ to $10$.
To show that all the numbers that satisfy our property have the shape $-1+kM$, we must check (i) All the numbers of this form do satisfy our property, and (ii) Nothing else does.
For (i), suppose that $M$ is the least common multiple of the numbers from $2$ to $10$. Then when we divide $-1+kM$ by any $m$ from $2$ to $10$, we get the same remainder as when we divide $-1$ by $m$, because $m$ divides $M$. Since the remainder when $-1$ is divided by $m$ is $m-1$, the remainder when $-1+kM$ is divided by $m$ is also $m-1$, and therefore $-1+kM$ "works."
To prove (ii), suppose that $x$ has the same remainder as $-1$ when $x$ is divided by any of the numbers from $2$ to $10$. Then $x-(-1)$ has remainder $0$ when it is divided by any one of the numbers from $2$ to $10$. It follows that $x+1$ is divisible by the least common multiple of the numbers from $2$ to $10$. Thus $M$ divides $x+1$, which means that $x$ has the shape $kM-1$.
-
0It might be easier to see if you just ask "what happens when you add $1$ to such a number?" Then it must be perfectly divisible by $2,3,\dots,10$. So you are trying to find a number $N$ such that $N+1$ is divisible by all these numbers, and the least such $N+1$ is the least common multiple. – 2013-04-23
The smallest such number is 2519. The next number can obtain by the equation 2519x+x-1. Where x can replaced by any whole number
-
0True, although wouldn't it be easier just to write $2520x-1$? – 2015-12-09
first you will divide 3/2 and you will get 1 . then you wll divide 8/3 you get 2 . then you divide 15/4 you get 3 . divide 24/5 you get 4 . you will do this process and you will get reminder.