4
$\begingroup$

A number leaves a remainder $2$ when divided by $9$.Which of the following could not be the remainder when it is divided by $45$?

  1. $20$
  2. $30$
  3. $29$
  4. $38$

How could we solve this under a minute? Please explain your approach.

3 Answers 3

3

$x = 9k + 2$.

Now if $k = 5m + r$, $0 \leq r \leq 4$ then $x = 45m + 9r + 2$.

Thus the remainder upon dividing by $45$ should be of the form $9r + 2$. $30$ isn't it.

In other words, $x-2$ is divisible by $9$, hence the remainder upon dividing $x-2$ by $45$ should also be divisible by $9$, as $45$ is divisible by $9$.

In general, if $x$ leaves a remainder $r$ upon dividing by $a$, the possible remainders it leaves when divided by $b$ are of the form $k \times \text{gcd}(a,b) + r$. ($\text{gcd}$ = greatest common divisor).

In this case, $\text{gcd}(9,45) = 9$.

If $a$ and $b$ are co-prime, then any remainder is possible.

See: Bezout's Identity.

  • 0
    @Tret: x = at + r = bq + s. i.e at - bq = (r-s). If a,b are coprime we can choose t and q so that at-bq = 1 or 2 or 3 or any number we want. If a,b are not coprime, then it is necessarily true that gcd(a,b) divides r-s.2011-07-13
3

It's easy: $\rm \ 45\ k + n\ =\ 9\ m + 2\ \Rightarrow\ 9\:$ divides $\rm\: n-2\:,\: $ which fails only for the 2nd choice $\rm\:n = 30\:. $

2

Under a minute? How strangely precise.

Denote the number by $n$. Take each of your options. If they work, you can write (respectively)

1- $n = 45q + 20$

2- $n = 45q + 30$

3- $n = 45q + 29$

4- $n = 45q + 38$

Now, we know that upon dividing by 9 we get a remainder of 2. Lets look at the first example. $n = 45q + 20$. Dividing $n$ by 9 we have

$n/9 = (45q + 20) / 9 = 45q/9 + 20/9 = 5q + 20/9$.

Hence the remainder comes from $20/9$, and as $18 = 9\cdot 2$, the remainder is 2. So this is OK! Looking at each of the options, you can see that 20,29 and 38 all must give a remainder of 2 upon division by 9, whereas dividing 30 by 9 gives a remainder of 3.