Intereting Posts

Find the region where an integral is defined
irrationality of $\sqrt{2}^{\sqrt{2}}$.
Asymptotic expansion of $\int_{0}^{\infty} \frac{\sin(\frac{x}{n})}{x(1+x^2)}dx$?
Show that $\mathbb{K}$ is a field
Laplacian in polar coordinates
Solution for exponential function's functional equation by using a definition of derivative
How to derive the formula for the sum of the first $n$ odd numbers: $n^2=\sum_{k=1}^n(2k-1).$
Isometry between $L_\infty$ and $\ell_\infty$
Show that $A$ is an invertible matrix if $\left(A+I\right)^3=0$ and find $A^{-1}$
Dirac delta function as a limit of sinc function
Are the any non-trivial functions where $f(x)=f'(x)$ not of the form $Ae^x$
A question concerning unipotent matrices and a basis choice
How Differential got into calculus
Inequality Of Four Variables
Quotient of cyclic $R$-module is cyclic.

Find the smallest $n$ so that:

$n$ divided by $3$ gives remainder $2$, $n$ divided by $11$ gives remainder $8$, $n$ divided by $27$ gives remainder $5$, $n$ divided by $47$ gives remainder $40$.

I’m not sure if it is $2813$, but that is the number I used to generate this problem. Anyways, I’m trying to figure out how to use the Chinese remainder to solve this problem step by step. I’ve seen “tricks” where they use the LCM and other things, but I need to know the way with the Chinese remainder theorem for my exam.

- Consecutive sets of consecutive numbers which add to the same total
- Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$
- Proof about fibonacci numbers by induction
- Prove that : $(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ divisible by $12$
- Root of a polynomial with rational coefficients
- Is it impossible to recover multiplication from the division lattice categorically?

- Proof that there are infinitely many primes congruent to 3 modulo 4
- How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?
- Finding a primitive root modulo $11^2$
- Find all solutions of ${\frac {1} {x} } + {\frac {1} {y} } +{\frac {1} {z}}=1$, where $x$, $y$ and $z$ are positive integers
- Prime factorization of square numbers
- Integral multiples of g.c.d.(m,n)
- how to find the last non-zero digit of $n$
- Express Integer as Sum of Four Squares
- Find the last two digits of the number $9^{9^9}$
- Prove: $\gcd(a,b) = \gcd(a, b + at)$.

The following is not the fastest method, but it’s pretty simple so I like to use it.

Ok, start with 40, and keep adding 47 until it satisfies the 5 modolu 27:

40 (=13 mod 27 .. No) -> 87 (=6 mod 27, no) -> 134 (26) ->181 (19) ->228 (12) ->275 (5:yes!)

OK, so now keep adding 27*47 =1269 until you get 8 modulo 11:

275 (=0 mod 11, no)->1544 (4, no)-> 2813 (yes!)

OK, so now keep adding 11*27*47 until you get 2 module 3:

2813 (= 2 modulo 3: yes!)

OK, so that’s indeed the answer:2813

You have $M = 11\times 27\times 47 = 13959$ and $M_1 = M/11 = 1269$, $M_2 = M/27 = 517$, $M_3 = M/47 = 297$. Taking $y_1$, $y_2$, $y_3$ such that $M_1y_1 = 1$ (mod 11), $M_2y_2 = 1$ (mod 27), $M_3y_3 = 1$ (mod 47). Then we have $$n = 8M_1y_1 + 5M_2y_2 + 40M_3y_3.$$

EDIT: make some simple calculation, you have $y_1 = 3$, $y_2 = 7$, $y_3 = 22$, then $n = 309911 = 2813$ (mod M).

The following solution is how I learned how to do these problems at first, and can be quite long, but uses a fairly straight forward algorithm so it tends to be accurate.

This problem is equivalent to solving the system of congruences:

$$(*)\begin{cases}n\equiv 2\mod 3\qquad (1)\\n\equiv 8\mod 11\qquad (2)\\n\equiv 5\mod 27\qquad (3)\\n\equiv 40\mod 47\qquad (4)\end{cases}$$

You can use the fact that

$$(**)\begin{cases}x\equiv a\mod m\\x\equiv b\mod n\end{cases}$$

has a solution $\color{red}{x_0=anv+bmu}$ where $u,v\in\Bbb Z$ satisfy $mu+nv=1$. Notice that this solution requires that $\gcd(m,n)=1$ since $\gcd(m,n)=1\iff \exists u,v\in\Bbb Z:mu+nv=1$. Also, any solution to $(**)$ will be congruent to $x_0$ modulo $m\cdot n$. In your question, we see that $3$ and $27$ are not relatively prime, so we can first reduce the system involving $(1)$ and $(3)$, which is the system

$$(***)\begin{cases}n\equiv 2\mod 3\\n\equiv 5\mod 27\end{cases}$$

Note that $(***)$ will have a solution because $\gcd(3,27)=3$ and $2\equiv 5\mod 3$. This comes from the fact that, if $d=\gcd(m,n)$, then the system $(**)$ has a solution if and only if $a\equiv b\mod d$. Indeed, this boils down the original system $(*)$ to the following:

$$(****)\begin{cases}n\equiv 5\mod 27\qquad (5)\\n\equiv 8\mod 11\\n\equiv 40\mod 47\end{cases}$$

since $n=5$ satisfies $n\equiv 2\mod 3$. Then we see that $27,11,47$ are all relatively prime (pairwise), and so you can use the aforementioned particular solution (i.e. $x_0$ as highlighted in red), where you first solve the system of congruences $(5)$ and $(2)$, and then take that solution and solve the system of congruences with $(4)$. Any solution to $(****)$ will be unique modulo $27\cdot 11\cdot 47=13959$.

Just to show you how to solve systems like $(**)$, a solution to the system involving $(5)$ and $(2)$ is $x_0=(5)(11)(5)+(8)(27)(-2)=-157$ since $27(-2)+11(5)=1$. Then this system has a unique solution modulo $27\cdot 11=297$, and is $-157\equiv 140\mod 297$. So now you have to solve the final system:

$$(*****)\begin{cases}n\equiv 140\mod 297\\n\equiv 40\mod 47\end{cases}$$

**A Summary:**

$$\begin{align}&(1)\qquad\text{Break the system $(*)$ into smaller systems like $(**)$.}\\&(2)\qquad\text{Find integers $u$ and $v$ such that $mu+nv=1$, where $m$ and $n$ are described in $(**)$}\\&(3)\qquad\text{Use the particular solution $x_0=anv+bmu$ which solves $(**)$}\\&(4)\qquad\text{Pair these solutions to the smaller congruence systems together to form new} \\&\qquad\qquad\text{systems until you have reduced the system to one congruence.}\end{align}$$

3 is not needed, it is taken care of by 27. Begins with

$$ 27 \cdot (-2) + 11 \cdot 5 = 1 $$

$$ 297 \cdot 22 + 47 \cdot (-139) = 1 $$

$$ 8 \cdot 27 \cdot (-2) + 5 \cdot 11 \cdot 5 = -432 + 275 = -157 $$

is $8 \pmod {11}$ and $5 \pmod {27}.$

$$ 40 \cdot 297 \cdot 22 + (-157) \cdot 47 \cdot (-139) = 1287041 $$

is $40 \pmod {47}$ and $-157 \pmod {297}$

Now, as you knew,

$$ 1287041 \equiv 2813 \pmod {13959}, $$

so the smallest answer is your 2813.

Note

$$ 27 \cdot 11 \cdot 47 = 13959 $$

$$ 1287041 = 92 \cdot 13959 + 2813 $$

LATER

Looking at the other answers, I can see how there is an advantage to choosing positive representatives in the middle stages. In this case

$$ -157 + 297 = 140 \equiv -157 \pmod {297} $$

The next step changes to

$$ 40 \cdot 297 \cdot 22 + 140 \cdot 47 \cdot (-139) = 261360-914620 = -653260 $$

Well, not much better

- $\frac{SU(2)}{N}= U(1) \times Z_2$. Find $N$?
- Isomorphic rings or not?
- How find this limit $\lim \limits_{x\to+\infty}e^{-x}\left(1+\frac{1}{x}\right)^{x^2}$
- Pythagorean Triplets with “Bounds”
- Counting Combinations of a List of Numbers
- Floor function as derivative
- Find all the continuous functions such that $\int_{-1}^{1}f(x)x^ndx=0$.
- What can we learn about a group by studying its monoid of subsets?
- $R$ is a commutative integral ring, $R$ is a principal ideal domain imply $R$ is a field
- Continuous Deformation Of Punctured Torus
- non sequential spaces
- References on similarity orbits of operators
- How to solve this recurrence $T(n) = 2T(n/2) + n\log n$
- How many ways to divide group of 12 people into 2 groups of 3 people and 3 groups of 2 people?
- Topological Vector Space: $\dim Z\text{ finite}\implies Z\text{ closed}$