How to solve this very quickly? 
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$?



*

*$20$

*$30$

*$29$

*$38$


How could we solve this under a minute? Please explain your approach.
 A: $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.
A: 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\:. $
A: 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.
