MHB Why Must We Solve Linear Congruences in the Chinese Remainder Theorem?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Linear
AI Thread Summary
The discussion centers on the necessity of solving the linear congruence \(M_j \cdot x \equiv c_j \pmod{m_j}\) in the proof of the Chinese Remainder Theorem (CRT). Participants highlight that this step is crucial as it leads to a unique solution modulo the product of the coprime integers. The proof involves defining \(M\) as the product of the moduli and \(M_j\) as the quotient of \(M\) divided by each modulus. Clarification is sought on why this specific congruence must be solved, with the explanation indicating that its significance will become clearer in subsequent steps of the proof. Understanding this step is essential for grasping the overall logic of the CRT.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hey! (Wasntme)

I am looking at the proof of the Chinese remainder theorem,which is:
Let $m_1,m_2, \dots, m_n$ be pairwise coprime.
Then the system $$\left\{\begin{matrix}
x \equiv c_1 \pmod {m_1}\\
\dots \dots\\
x \equiv c_n \pmod {m_n}
\end{matrix}\right.$$

is equivalent with one linear congruence of the form $x \equiv c \pmod {m_1 \dots m_n} $ for a ($\text{ unique } \pmod {m_1 \dots m_n} c$).

At the proof,we consider the numbers:

$M=m_1 \cdots m_n $
$M_j=\frac{M}{m_j}, 1 \leq j \leq n$

$\forall j$ we solve the linear congruence

$$M_j \cdot x \equiv c_j \pmod{m_j}$$

But...why do we have to solve this linear congruence? (Thinking)
 
Mathematics news on Phys.org
evinda said:
Hey! (Wasntme)

I am looking at the proof of the Chinese remainder theorem,which is:
Let $m_1,m_2, \dots, m_n$ be pairwise coprime.
Then the system $$\left\{\begin{matrix}
x \equiv c_1 \pmod {m_1}\\
\dots \dots\\
x \equiv c_n \pmod {m_n}
\end{matrix}\right.$$

is equivalent with one linear congruence of the form $x \equiv c \pmod {m_1 \dots m_n} $ for a ($\text{ unique } \pmod {m_1 \dots m_n} c$).

At the proof,we consider the numbers:

$M=m_1 \cdots m_n $
$M_j=\frac{M}{m_j}, 1 \leq j \leq n$

$\forall j$ we solve the linear congruence

$$M_j \cdot x \equiv c_j \pmod{m_j}$$

But...why do we have to solve this linear congruence? (Thinking)

The procedure is explained here...

http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$
 
chisigma said:
The procedure is explained here...

http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$

I still haven't understood why we have to solve the system $M_j \cdot x \equiv c_j \pmod {m_j}$... (Sweating)
 
evinda said:
I still haven't understood why we have to solve the system $M_j \cdot x \equiv c_j \pmod {m_j}$... (Sweating)

Hey! (Emo)

It's the first step in the proof...
The reason why we're solving that system will become apparent in a later step where everything cancels nicely. (Nerd)
 
I like Serena said:
Hey! (Emo)

It's the first step in the proof...
The reason why we're solving that system will become apparent in a later step where everything cancels nicely. (Nerd)

Ok..thank you very much! :)
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'Fermat's Last Theorem'

Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

MHB System of congruences, not relatively prime moduli
Replies
2
Views
4K
Solve the simultaneous linear congruences
Replies
4
Views
2K
Finding Integer with Chinese Remainder Theorem
Replies
3
Views
2K
MHB Parity equivalent to the system
Replies
7
Views
2K
Solve ##x\equiv 5\pmod{11},x\equiv 14\pmod{29},x\equiv 15\pmod{31}##
Replies
3
Views
3K
Solve ##x\equiv 1\pmod {3},x\equiv 2\pmod {5},x\equiv 3\pmod 7 ##
Replies
1
Views
2K
Obtain the two incongruent solutions modulo 210 of the system
Replies
7
Views
3K
MHB Why Do We Solve the Congruence \(7x \equiv 1 \pmod{11}\) to Find Solutions?
Replies
21
Views
4K
MHB Why do we conclude that r1-r2=0?
Replies
6
Views
2K
Chinese Remainder theorem for 2 congruences
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top