Intereting Posts

lim$_{n\rightarrow \infty}\int _{-\pi}^\pi f(t)\cos nt\,dt$
Multivariate Taylor Series Derivation (2D)
Two players placing coins on a round table with the goal of making the last move
A Curious binomial identity
Transitive closure
Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$
Local solutions of a Diophantine equation
“Converse” of Taylor's theorem
$\cap_{A \in \mathcal{F}}(B \cup A) \subseteq B \cup (\cap \mathcal{F})$
Moment generating function of a gamma distribution
Existence proof of the tensor product using the Adjoint functor theorem.
Congruence question with divisibility
Equivalence of definitions of $C^k(\overline U)$
Prove $\bigcap \{A,B,C\} = (A \cap B) \cap C$
When is $8x^2-4$ a square number?

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$

- Solve for n: $\varphi(2n)=\varphi(3n)$
- Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.
- Algorithm to find solution to $ax^2 + by^2 = 1$ in a finite field
- Why does Engel expansion give smaller denominators than the Greedy algorithm?
- Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$
- For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$
$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

- When is the group of quadratic residues cyclic?
- Using Fermat's little theorem to find remainders.
- Is there an algorithm for writing an integer as a difference of squares?
- Show that for any prime numbers $p,q,r$, one has $p^2+q^2 \ne r^2$.
- Prove that $1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n}$ is not an integer
- Can an odd perfect number be divisible by $101$?
- Prove that one of $n$ consecutive integers must be divisible by $n$
- Method for coming up with consecutive integers not relatively prime to $(100!)$
- Is there a conjecture with maximal prime gaps
- A number-theory question on the deficiency function $2x - \sigma(x)$

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

- Minimal Polynomial of $\sqrt{2}+\sqrt{3}+\sqrt{5}$
- What is the role of mathematical intuition and common sense in questions of irrationality or transcendence of values of special functions?
- How to find the angle between two straight line equations?
- Is $2^{1093}-2$ a multiple of $1093^2$?
- Sum of the series $\frac{1}{2\cdot 4}+\frac{1\cdot3}{2\cdot4\cdot6}+\dots$
- A type of integer numbers set
- All the ternary n-words with an even sum of digits and a zero.
- True, false, or meaningless?
- Are “most” continuous functions also differentiable?
- Differentiating both sides of a non-differential equation
- Proving formula for product of first n odd numbers
- Does a polynomial that's bounded below have a global minimum?
- Find all irreducible monic polynomials in $\mathbb{Z}/(2)$ with degree equal or less than 5
- A series involves harmonic number
- Can you please check my Cesaro means proof