2
$\begingroup$

$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 = \text{remainder of $\left(3k/5 + 4/55\right)$} = \text{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.

  • 0
    Do you know about the Chinese remainder theorem?2011-01-28

5 Answers 5

7

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.

  • 0
    simple and beautiful2011-01-28
2

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?

  • 3
    @Eg$a$litarian: You don't *need* to know **CRT** $b$ut you *should* know it since it is the **m$a$ster theorem** $b$ehind 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.2011-01-28
2

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)$

1

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

0

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