# Number system Problem

N leaves a remainder of 4 when divided by 33, what are the possible remainders when N is divided by 55?

My approach :

Number has to be 33k+4 Possible remainders will be (33k+4)/55 = 33k/55 + 4/55 = remainder of (3k/5 + 4/55) = remainder of (3k/5) + Remainder of (4/55) Since ,Remainder of 3k/5 will be 1,2,3,4 And also remainder of 4/55 will be 4

So, remainder can be 5,6,7,8

I think there is some fundamental logical flaw with my approach. Please let me know what it is

-
Do you know about the Chinese remainder theorem? –  Alex B. Jan 28 '11 at 8:14

One approach which is similar to yours and does work:

Let $r$ be the remainder when $N$ is divided by 55. So, $N=33k+4=55j+r$. Subtracting $55j$ from both sides, we get $33k-55j+4=r$ or $11(3k-5j)+4=r$. Since $3k-5j$ could end up being any integer, let it be $0,1,2,3$ or $4$.

$$r=11(0)+4=4$$ $$r=11(1)+4=15$$ $$r=11(2)+4=26$$ $$r=11(3)+4=37$$ $$r=11(4)+4=48$$

Other choices for $3k-5j$ produce remainders that are too large (or too small).

Edit: I should note that being able to choose any integer for $3k-5j$ relies on the observation that $3(2n)-5(n)=n$. So choosing $k=2n$ and $j=n$ allows $3k-5j$ to equal any integer $n$. While $3$ and $5$ are small enough to make this easy to see. For larger integers, you may need the Euclidean algorithm and Bézout's identity.

-
Nice, this is a neat solution. –  yunone Jan 28 '11 at 8:30
simple and beautiful –  Egalitarian Jan 28 '11 at 12:40

Have you learned about the Chinese Remainder Theorem yet? This problem seems specifically geared towards it. I've never seen remainders calculated the way you have, and it doesn't quite work like that. For example taking $k=1$, $33=\text{remainder}(33/55)\neq \text{remainder}(3/5)=3$, since $33=0\cdot 55+33$ and $3=0\cdot 5+3$ when you use the division algorithm, so you can't just cancel factors. Also, $\text{remainder}(33/55)+\text{remainder}(4/55)\neq \text{remainder}(33/55)$, since otherwise you would have $\text{remainder}(4/55)=0$, but it is in fact $4$.

However, using the Chinese Remainder Theorem, you have a situation like this:

Since $N$ has a remainer of $4$ when divided by $33$, you have $N\equiv 4\pmod{33}$. This implies that $N\equiv 4\equiv 1\pmod{3}$ and more importantly, $N\equiv 4\pmod{11}$. To find the possible remainders of $N$ when divided by $55$, you have to use that fact that $55=5\cdot 11$. Choose possible remainders for $N$ upon division by $5$, and then use the Chinese Remainder Theorem to find the remainders modulo $55$.

Does this help somewhat?

-
Seems I need to know chinese theorem –  Egalitarian Jan 28 '11 at 13:20
@Egalitarian: You don't need to know CRT but you should know it since it is the master theorem behind many such results in elementary number theory. Otherwise you will end up reinventing the wheel with ad-hoc arguments, and you'll never see the number theoretical forest for the trees. –  Bill Dubuque Jan 28 '11 at 16:23

HINT $\$ By the Chinese Remainder Theorem,

$\rm\quad\quad\quad\quad\quad\quad\quad\quad x\equiv r\ (mod\ 55)\$

$\rm\quad\quad\quad\quad\quad\quad\quad\quad x\equiv 4\ (mod\ 33)\$

is solvable iff $\rm\ r\equiv 4\ (mod\ 11)\ \$ since $\rm\ \ 11 = gcd(55,33)$

Hence since $\rm\ \ r = 4 + 11\ k\:\$ we deduce $\rm\ r = 4,\:15\:,\:\cdots\ (mod\ 55)$

-

N is congruent to 4 mod 33 and the highest common factor of 33 and 55 is 11.

So N is congruent to 4 mod 11 and mod 55 can be anything that has this congruence.

Therefore 4, 15, 26, 37 or 48

-

You need to find all values of $x$ satisfying $33k$ + $4=x$ $mod 55$

for some $k\in N$. Multiplying both sides by 5 gives us
$20=5x$ $mod 55$

Note that this is not the same as $4=x$ $mod 55$ as 5 is not a unit in $Z\over{55Z}$. As a result, there are multiple solutions for $x$.

As for your method, it's probably not best to work with fractions, especially reduced fractions. The problem you run into is that $3k/5$ only produces remainders of 1,2,3, or 4 while its obvious that the problem could have much larger remainders (for instance, if $k=1$ the remainder is 37).

-