Intereting Posts

weak convergence of product of weakly and strongly convergent $L^{2}$ sequences in $L^{2}$
Presheaf image of a monomorphism of sheaves is a sheaf
If $f(x) = h(x)g(x)$, is $h$ differentiable if $f$ and $g$ are?
Cyclic Group Generators of Order $n$
Generate solutions of Quadratic Diophantine Equation
$A^A$ in category of graphs
How many compositions of n are there in which each part is an even number?
How to partial differentiate a total differential and be rigorous on all the notion?
How to calculate interpolating splines in 3D space?
When is every group of order $n$ nilpotent of class $\leq c$?
Calculate in closed form $\sum_{n=1}^{\infty} \frac{\arctan(1/n) H_n}{n}$
Cancelling matrices
On modular roots of $-1$?
Polynomial uniqueness proof
Sum of the infinite series $\frac16+\frac{5}{6\cdot 12} + \frac{5\cdot8}{6\cdot12\cdot18} + \dots$

I’m working on some Chinese Remainder problems and it doesn’t seem like I have the procedure down correctly. I’ll list the steps I’m taking so hopefully someone can spot what it is I’m doing wrong.

Find the least nonnegative solution of each system of congruences below.

$x \equiv 3 \space mod \space 4$

- Prove by contradiction that every integer greater than 11 is a sum of two composite numbers
- The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer
- Order of an Element Modulo $n$ Divides $\phi(n)$
- The number of ways of writing an integer as a sum of two squares
- Using Carmichael function in RSA.
- Finding the last two digits of a number by binomial theorem
$x \equiv 2 \space mod \space 5$

Since the mod values are relatively prime, I preformed the following procedure described in my textbook. Let $M = m_{1} \cdot m_{2} \cdot \cdot \cdot m_{n}$ and $M_{i} = \frac{M}{m_{i}}$

$M = (4) \cdot (5) = 20$

$M_{1} = \frac{20}{4} = 5$

$M_{2} = \frac{20}{5} = 4$

Next solve the congruence $M_{i} x_{i} \equiv \text{1 mod} \space m_{i}$ for $x_{i}$

$5x_{1} \equiv \text{1 mod} \space 4$ $\Longrightarrow$ $x_{1} \equiv 1 \space \text{mod} \space 4$

$2x_{2} \equiv \text{1 mod} \space 5$ $\Longrightarrow$ $x_{2} \equiv 3 \space \text{mod} \space 5$

Finally solve for x, where x is defined in the following way: $x = b_{1} \cdot M_{1} \cdot x_{1} + \cdot \cdot \cdot + b_{n} \cdot M_{n} \cdot x_{n}$

$x = (3 \cdot 5 \cdot 1) + (2 \cdot 4 \cdot 3) \space \text{mod} \space 20$

$x = 19 \space mod \space 20$

Now this final value indicates that any positive integer congruent to 19 modulo 20 solves the given system of equations. However, the answer at the back of my textbook is 7 which isn’t congruent to 19 modulo 20.

Any help with where I’m going wrong would be appreciated

- Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions?
- A statement about divisibility of relatively prime integers
- Prove that for no n>1 is the sum $(1!)^2+\cdots+(n!)^2$ a perfect square.
- Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?
- Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm.
- Show that $1^{p-1} + 2^{p-1} +\ldots + (p-1)^{p-1} \equiv -1 \mod p$
- If $x\equiv 1 \mod 3$, then $x^{100}\equiv 1 \mod 3$.
- Proof that $n^3+2n$ is divisible by $3$
- Can the sum of the first $n$ squares be a cube?
- Fibonacci Sequence problem. Prove that there are infinitely many prime numbers such that $p$ divides $F_{p-1}$

Note that your solution is incorrect since $x \equiv 19 \pmod{20}$ gives $x \equiv 4 \pmod {20}$. You need to solve for $$\color{blue}{4 x_2 \equiv 1 \pmod5}$$ and not $$\color{red}{2x_2 \equiv 1 \pmod 5}$$ Hence, you will get that

$$\color{blue}{x_2 \equiv 4 \pmod 5}$$ and not $$\color{red}{x_2 \equiv 3 \pmod 5}$$ The rest of your derivation is correct. Make the above correction and you will get the right answer.

The second case should be $x_2\cdot \frac{20}5\equiv1\pmod 5$

$\implies 4x_2\equiv1\pmod 5\implies -x_2\equiv1\pmod 5\implies x_2\equiv-1\pmod 5\equiv4\pmod 5$

So, $x\equiv3\cdot5\cdot1+2\cdot4\cdot4\pmod{20}\equiv47\equiv7\pmod{20}$

I noticed something very interesting: there are many implementations of the Chinese Remainder Theorem.

**Chinese Remainder Theorem**:

A theorem for solving a system of linear congruences, which come in the form

$\displaystyle x\equiv n_1\pmod{m_1}$

$\displaystyle x\equiv n_2\pmod{m_2}$

$\displaystyle \vdots$

$\displaystyle x\equiv n_k\pmod{m_k}$

Where $\displaystyle k\in\mathbb{N}$ and $\displaystyle m_1, m_2\cdots m_k$ are pairwise coprime, then $\displaystyle x_0=B_1X_1n_1+B_2X_2n_2+\cdots+B_kX_kn_k$ where $\displaystyle B=\prod_{i=1}^{k}m_i$ and $\displaystyle B_k=\frac{B}{m_k}$ and $\displaystyle X_k$ is defined so that $\displaystyle B_kX_k\equiv1\pmod{m_k}$.

The smallest positive integer solution $\displaystyle x_1$ is defined such that $\displaystyle x_0\equiv x_1 \pmod{B}$

For this system where it is

$\displaystyle x \equiv 3 \pmod{4}$

$\displaystyle x \equiv 2 \pmod{5}$

$\displaystyle B = 4\times5 = 20$

$\displaystyle B_1=\frac{20}{4}=5$, $\displaystyle B_2=\frac{20}{5}=4$

$\displaystyle 5X_1\equiv1\pmod{4} \iff X_1\equiv1\pmod{4}$, $\displaystyle X_1=1$

$\displaystyle 4X_2\equiv1\pmod{5}$, $\displaystyle X_2=4$

$\displaystyle x=5\times1\times3+4\times4\times2=47$

$\displaystyle 47 \equiv 7\pmod{20}$

That is why your textbook says the answer if $\displaystyle 7$.

- Proof of the Borsuk-Ulam Theorem
- Why is the inclusion of the tensor product of the duals into the dual of the tensor product not an isomorphism?
- Is $\|x\| = \| \overline{x} \|$ in an inner product space?
- calculating nested exponents modulo n
- A secant inequality for convex functions
- What does a “half derivative” mean?
- second order differential equation with Green's function
- I can't remember a fallacious proof involving integrals and trigonometric identities.
- Integral of Exponential raised by exponential
- Maximum likelihood estimate of hypergeometric distribution parameter
- Proof of Alternate, Corresponding and Co-interior Angles
- Showing the Rec is $\Sigma_3^0$-complete
- Estimating rate of blow up of an ODE
- Generators for $S_n$
- A few clarifications on the irrational slope topology