0

From https://en.m.wikipedia.org/wiki/Chinese_remainder_theorem

Let $n_1, ..., n_k$ be integers greater than 1, which are often called moduli or divisors. Let us denote by $N$ the product of the $n_i$.

The Chinese remainder theorem asserts that if the $n_i$ are pairwise coprime, and if a1, ..., ak are integers such that $0 ≤ a_i < n_i$ for every $i$, then there is one and only one integer $x$, such that $0 ≤ x< N$ and the remainder of the Euclidean division of $x$ by $n_i$ is $a_i$ for every $i$.

This may be restated as follows in term of congruences: If the $n_i$ are pairwise coprime, and if $a_1, ..., a_k$ are any integers, then there exist integers $x$ such that

$${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}{\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$$

I understood few things, like when x is divided by a divisor ($n_1$) then the remainder is $a_1$, so $x=kn_1+a_1$

But I'm having trouble "reading" the statement, and understanding in the present format. I visited Wikipedia because I have literally no knowledge in modular arithmetic, I don't even know the basic terms. I was hoping Wikipedia would help but it's not helping.

Any website(not YouTube) where I could I learn about these terms at one place?

Ashley
  • 111
  • 3
    If you've got literally no knowledge in modular arithmetic it will be very difficult to understand a complicated theorem about modular arithmetic. Even if you know the meanings of the words the result will be hard to appreciate. Why not start with the Wikipedia article on modular arithmetic? – Matthew Towers Jun 19 '20 at 12:41
  • 1
    https://en.wikipedia.org/wiki/Modular_arithmetic – DanielWainfleet Jun 19 '20 at 13:10
  • Ah, thanks! I am already learning its basics on brilliant – Ashley Jun 19 '20 at 13:15

1 Answers1

0

$x\equiv y \mod n$ means $(x-y)/n \in \Bbb Z.$

This is almost always in a context where $x,y,n \in \Bbb Z$ (and usually $n>0$ ), where it means $n$ is a divisor of $x-y,$ that is, $x$ and $y$ have the same remainder when divided by $n.$

The basic tools, for integers, with $n>0,$ are:

There is exactly one integer $a'$ with $a'\equiv a \mod n$ and $0\le a'\le n-1.$

$a\equiv a'\mod n \iff a-a'\equiv 0 \mod n.$

If $a\equiv a'$ & $b\equiv b'$ & $c\equiv c' \mod n$ then $ab+c\equiv a'b'+c' \mod n.$

If $a\equiv b \mod n$ and if $m\in \Bbb Z^+$ then $a^m\equiv b^m \mod n.$

DanielWainfleet
  • 57,985