5
$\begingroup$

What is the smallest positive integer that gives the remainder 5 when divided by 6, gives the remainder 2 when divided by 11 and 31 when divided by 35?

Also, are there any standard methods to solve problems like these?

$\endgroup$
  • 5
    $\begingroup$ "Are there standard methods to solve problems like these?" Yes, and the phrase to google is the Chinese Remainder Theorem. Note: you should read something else before wikipedia, because the wikipedia article on the CRT is pitched a bit higher than you're looking for. $\endgroup$ – davidlowryduda Aug 19 '16 at 21:15
  • 6
    $\begingroup$ The title is very misleading. I came in here to yell "Five!" $\endgroup$ – user856 Aug 19 '16 at 21:16
  • 1
    $\begingroup$ @mixedmath The Wikipedia article is "pitched a bit higher"? Unless you've written it yourself, can you even be sure it's pitched correctly? $\endgroup$ – Mr. Brooks Aug 19 '16 at 21:18
  • $\begingroup$ @mixedmath thanks for the pointer. $\endgroup$ – user6395724 Aug 19 '16 at 21:19
  • $\begingroup$ @Rahul sorry bout that :c $\endgroup$ – user6395724 Aug 19 '16 at 21:20
5
$\begingroup$

Rather than mechanically applying the CRT formula, the following method is usually quicker and much simpler (here so simple that it can be computed with purely mental arithmetic).

${\rm mod}\ 35\!:\ {-}4\equiv n\iff n = -4+35j$

${\rm mod}\ 11\!:\ 2\equiv n = -4\!+\!35\,\color{#c00}j\equiv -4+2j\iff 6\equiv 2j\iff j\equiv3\iff \color{#c00}{j = 3+11k} $

Thus we have $\ n = -4+35(\color{#c00}{3+11k}) = 101+11\cdot 35k $

${\rm mod}\ 6\!:\ {-}1\equiv n\equiv 101+11\cdot 35\cdot\color{#0a0}k\equiv -1+k\iff k\equiv 0\iff\color{#0a0}{ k = 6m}$

Hence we have $ \ n = 101+11\cdot 35\cdot\color{#0a0}{6m}$


Remark $ $ Only very small numbers were involved because we solved the congruences with largest moduli first, so that, in the end, when the numbers are bigger, this is compensated by computing at smaller moduli. We simplify arithmetic by using remainders of least magnitude, e.g. we used $\,-4\equiv 31\pmod{35}$. Note that we did not not need to compute any inverses at all (keeping the numbers as small as possible increases the probability that this will occur).

This method also works even if the moduli are not pairwise coprime, though in this general case there may be zero or multiple solutions. Furthermore it leads to the well-known criterion for existence of a solution in the general case - which characterizes the ubiquitous Prüfer domains. They generalize many common number systems and are characterized by a remarkably huge number of interesting properties, e.g. Gauss's Lemma for contents, lcm distributes over gcd (and reversely), contains = divides for fin. gen. ideals, etc. Thus it is well-worth investing the small effort needed to master this viewpoint of CRT.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Jack Thanks. It is puzzling why this method is not more widely taught, esp. since it generalizes widely (I just added a remark about that). $\endgroup$ – Gone Aug 19 '16 at 23:43
  • $\begingroup$ Thank you, seems much easier to understand than CRT. Does this method works for all cases as long as i use the remainder that are closest to zero? And also begin with the expressions with the large moduli? $\endgroup$ – user6395724 Aug 20 '16 at 14:48
  • $\begingroup$ @user6395724 Yes, the method always works (as the linked post shows). When working with congruences one always has the flexibility to replace arguments of sums and products (but not exponents!) by any congruent argument, due to the Congruence Sum and Product Rules. Generally we choose smaller representatives in order to help simplify the arithmetic. For example $\, {\rm mod}\ 10\!:\,\ 9^{2n}\equiv (-1)^{2n}\equiv 1\,$ is simpler when we choose the rep $\,-1\equiv 9\,$ of least magnitude. $\endgroup$ – Gone Aug 20 '16 at 14:58
  • $\begingroup$ This might be a trivial question, but in the second line where does -4+2j come frome? $\endgroup$ – user6395724 Aug 20 '16 at 15:15
  • $\begingroup$ @user We are given that $\ {\rm mod}\ 11\!:\, n\equiv 2.\,$ From the prior line we know $\ n = -4 + 35j.\ $ Plugging this value of $\,n\,$ into this congruence we get $\,2\equiv n \equiv -4+\color{#c00}{35}j \equiv -4+\color{#c00}2j\ $ since $\,\color{#c00}{35} = \color{#c00}2+3(11)\equiv \color{#c00}2.\,$ Then, adding $\,4\,$ to both sides yields $\, 6\equiv 2j\,$ etc. $\endgroup$ – Gone Aug 20 '16 at 15:27
9
$\begingroup$

The system of equations $$ \left\{\begin{array}{ll} n \equiv 5 &\pmod{6} \\ n \equiv 2&\pmod{11} \\ n\equiv 31 &\pmod{35}\end{array}\right. $$ is equivalent to $n\equiv m\pmod{2\cdot 3\cdot 5\cdot 7\cdot 11}$ by the Chinese remainder theorem.
If $m_6, m_{11}, m_{35}$ are the smallest integer solutions of the systems $$ \left\{\begin{array}{ll} n \equiv 1 &\pmod{6} \\ n \equiv 0&\pmod{11} \\ n\equiv 0 &\pmod{35}\end{array}\right. \quad\left\{\begin{array}{ll} n \equiv 0 &\pmod{6} \\ n \equiv 1&\pmod{11} \\ n\equiv 0 &\pmod{35}\end{array}\right.\quad \left\{\begin{array}{ll} n \equiv 0 &\pmod{6} \\ n \equiv 0&\pmod{11} \\ n\equiv 1 &\pmod{35}\end{array}\right.$$ then we have $m\equiv 5m_6+2m_{11}+31 m_{35}\pmod{2310}$, and $m_6,m_{11},m_{35}$ are not difficult to compute. For instance, $m_6$ is a multiple of $11\cdot 35$ that is $\equiv 1\pmod{6}$, but $$ k\cdot 11\cdot 35 \equiv 1\pmod{6} $$ is equivalent to $k\equiv 1\pmod{6}$, hence $m_6=11\cdot 35=385$. In a similar way you may find $m_{11}=210$ and $m_{35}=1716$, then re-combine them in order to find $m=\color{red}{101}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is the last equation supposed to be n=101? $\endgroup$ – Yuriy S Aug 19 '16 at 23:34
5
$\begingroup$

If I'm understanding you correctly, you want to solve the simultaneous congruences $$x \equiv 5 \pmod 6$$ $$x \equiv 2 \pmod{11}$$ $$x \equiv 31 \pmod{35}$$ The moduli, $6, 11, 35$, are coprime, so the standard method comes from the Chinese remainder theorem.

Set $r_1 = 5$, $r_2 = 2$, $r_3 = 31$ (these are the remainders), $m_1 = 6$, $m_2 = 11$, $m_3 = 35$, $M = m_1 \times m_2 \times m_3 = 2310$.

Now we need to find $b_1, b_2, b_3$ such that $$b_i \frac{M}{m_i} \equiv 1 \pmod{m_i}.$$ For example, $b_1 = 1$ since $2310$ divided by $6$ is $385$ and $1 \times 385 \equiv 1 \pmod 6$. I leave you to find $210b_2 \equiv 1 \pmod{11}$ and $66b_3 \equiv 1 \pmod{35}$.

Once you have your $b_i$, the answer is $$x = \sum_{i = 1}^3 r_i b_i \frac{M}{m_i} \mod{2310} = 101.$$ (I 've adapted this from http://oeis.org/wiki/Chinese_remainder_theorem)

Just to doublecheck, go to Wolfram Alpha and type in ChineseRemainder[{5, 2, 31}, {6, 11, 35}].

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

If you aren't familiar or comfortable with Chinese Remainder Theorem you can do this:

$x = 6j + 5$

$x = 11k + 2$

So $6j + 5 = 11k +2$

$j = (11k - 3)/6 \in \mathbb Z$

$j = k + \frac 56k -1/2 \in \mathbb Z$

So $\frac 56 k = M + 1/2$ for some integer $M$.

$3$ is the smallest such number but any $6N + 3$ will work.

So $6j + 5 = 11(6N + 3) +2 = 66N + 35$ (and $j = 11N + 5$ but that's not important)

So $x = 66*N + 35$

We also know $x = 35m + 31$

So $66*N + 35 = 35m + 31$

$(66N + 4)/35= m \in \mathbb Z$

So $N + \frac{31}{35}N + \frac 4{35} \in \mathbb Z$

Simplest solution is $N = 1$ but any $N = 1 + 35P$ will do.

So $x = 66(1 + 35P) + 35 = 35*66P + 101$.

$101$ is the smallest number that works.

But and $35*66P + 101$ will also work.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, are there cases where this method does not work? $\endgroup$ – user6395724 Aug 20 '16 at 14:25
  • $\begingroup$ It may not work if some of the divisors have common factors. Say, remainder 1 if divided by 6 and remainder 2 if divided by 15. That has no solution because when divided by 30 it has remainder 15n + 2 and remainder 6m + 1 and there is not such possible remainder. Read up on The Chinese Remainder Theorem. Basically this is doing the CRT without knowing that you are doing the CRT. $\endgroup$ – fleablood Aug 20 '16 at 15:58
  • $\begingroup$ But if there is a solution this will solve it. And all problems where the divisors have no common factors will have a solution. $\endgroup$ – fleablood Aug 20 '16 at 16:00
  • $\begingroup$ Of course, even if they do have common divisors they might have solutions. remainder 1 if divided by 6 and remained 13 if divided by 15 will have solutions at 13 and all 13 + 30N. $\endgroup$ – fleablood Aug 20 '16 at 16:04
4
$\begingroup$

What is the smallest positive integer that gives the remainder 5 when divided by 6

It is something that can be written as $(6n+5)$

Gives the remainder 2 when divided by 11

And also written as $(11m + 2)$

Lets pause here:

We start with the guess of 5. and we say "that works for the first rule, but not the second."

Then we say 12 - 11 = 1.

If we add 12 to our guess we will get a remainder of that is one more than our previous guess. To get from a remainder of 5 to a remainder of 2 we need to subtract $3\cdot12, 5-36=-31.$

$-31?$ Well that is kind of weird, and it is, but lets hold onto it for now.

Next, the least common multiple of 6 and 11 is 66.

$66k - 31$ has remainders 5,2 when divided by 6 and 11 respectively. Lets write it as $66 (k-1) + 35$ because positive numbers are nicer. That $k$ is an arbitrary... we can just as easily say $66 k + 35$.

3rd rule: 31 when divided by 35.

$\frac {(66 k + 35)}{35}$ gives a remainder of $31k$

$k = 1$, and our number is $101$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

\begin{align} n \equiv 5 &\pmod{6} \\ n \equiv 2 &\pmod{11} \\ n \equiv 31 &\pmod{35} \end{align}

The idea is to find three integers, $A, B,$ and $C$ such that

\begin{array}{|l|l|l|} A \equiv 1 \pmod{6} & B \equiv 0 \pmod{6} & C \equiv 0 \pmod{6} \\ A \equiv 0 \pmod{11} & B \equiv 1 \pmod{11} & C \equiv 0 \pmod{11} \\ A \equiv 0 \pmod{35} & B \equiv 0 \pmod{35} & C \equiv 1 \pmod{35} \end{array}

Your answer will then be $5A + 2B + 31C \pmod{2310}$ where $2310 = 6 \cdot 11 \cdot 35$. Since $6, 11,$ and $35$ are pairwise prime, the Chinese remainder theorem guarantees that $A, B,$ and $C$ exist.

There is a formula that describes how to find $A, B,$ and $C$, but it isn't that much trouble to figure them out from scratch.

The equivalences $A \equiv 0 \pmod{11}$ and $A \equiv 0 \pmod{35}$ imply that $A$ must be a multiple of $385 = 11 \cdot 35.$ So $A = 385x$ for some integer $x$. We solve \begin{align} A &\equiv 1 \pmod 6 \\ 385x &\equiv 1 \pmod 6 \\ x &\equiv 1 \pmod 6 \\ \hline A &= 385(1) = 385 \end{align}

The equivalences $B \equiv 0 \pmod{6}$ and $B \equiv 0 \pmod{35}$ imply that $B$ must be a multiple of $210 = 6 \cdot 35.$ So $B = 210x$ for some integer $x$. We solve \begin{align} B &\equiv 1 \pmod{11} \\ 210x &\equiv 1 \pmod{11} \\ x &\equiv 1 \pmod{11} \\ \hline B &= 210(1) = 210 \end{align}

The equivalences $C \equiv 0 \pmod{6}$ and $C \equiv 0 \pmod{11}$ imply that $C$ must be a multiple of $66 = 6 \cdot 11.$ So $C = 66x$ for some integer $x$. We solve \begin{align} C &\equiv 1 \pmod{35} \\ 66x &\equiv 1 \pmod{35} \\ -4x &\equiv 1 \pmod{35} \\ x &\equiv -9 \pmod{35} \\ \hline C &= 66(-9) = -594 \end{align}

We then compute

\begin{align} n & \equiv 5A + 2B + 35C \pmod{2310} \\ &\equiv 5(385) + 2(210) + 31(-594) \pmod{2310} \\ &\equiv 101\pmod{2310} \\ \end{align}

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

The standard method involves the Chinese remainder theorem, but it's not the only method. I think here you might actually learn the most from the least efficient method.

The least efficient method is to try each positive integer one by one, starting with $x = 1$, and check if it satisfies each of the congruences. The Chinese remainder theorem guarantees that you will find an $x$ that works before you hit $6 \times 11 \times 35 = 2310$.

In the case of $x = 1$, we see that it satisfies none of the congruences. Moving on to $x = 2$, it works only for the second congruence. None of the congruences work with 3 or 4.

Then we see with $x = 5$ that it works for the first congruence but it doesn't work for the second congruence. I suggest a minor refinement: if we find that it doesn't work for one congruence, we don't bother to check if it works for the other congruences.

And so, since $x = 6$ doesn't work for the first congruence, we don't bother to check the other two. Another minor refinement: why don't we just skip ahead to the next number satisfying $x \equiv 5 \bmod 6$? That would be $x = 11$, which obviously satisfies the first congruence but not the second.

Likewise for 17, 23, 29. Then we get to $x = 35$, which satisfies the first two congruences but not the last one. Algebraically speaking, what we're doing is testing $x = r_1 + km_1$, starting with $k = 1$ and incrementing $k$ until we find an $x$ that satisfies all three congruences. That would be $k = 16$, giving us $x = 101$. That's the answer.

There is still one more refinement that might help in the last few minutes of an examination if you can't think of a better way, and that's to use the method described here with the largest modulus, which in this case is $m_3 = 35$ (there's no rule requiring the congruences to be sorted by moduli in ascending order, by the way).

So you do $x = r_3 + km_3$, again starting with $k = 1$. Now you just try 31 and 66 before finding success with $k = 3$ and $x = 101$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Python time! If you're okay with using the computer (the online compiler repl.it can be very handy), you can use the code

num=1

while True:
    if (num % 6 == 5):
        if (num%11 == 2):
            if (num%35 == 31):
                print num
                break
    num += 1

which gives 101. To double check, 101/6=16 R5, so that's right. 101/11=9 R2, so that's right. And 101/35=2 R31, so that is right as well. 101 is the correct answer.

Hope this helps!

Note: This code is adapted from this answer I did.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but python scripts aren't allowed at my examination test :/ $\endgroup$ – user6395724 Aug 19 '16 at 21:36
  • $\begingroup$ Well, I certain did not and would not downvote this but as a mathematical solution it's ... unsatisfying. $\endgroup$ – fleablood Aug 19 '16 at 23:46
  • 1
    $\begingroup$ I think I can explain one of the downvotes: sometimes on this site, when someone wants a question closed (as is the case with this one), they downvote all the answers. I haven't checked, but I think we've all gotten downvoted by that person. $\endgroup$ – Robert Soupe Aug 20 '16 at 5:25
  • 1
    $\begingroup$ up voted because I believe this to be a good alternative answer :) $\endgroup$ – jjonesdesign Aug 20 '16 at 6:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.