Questions tagged [chinese-remainder-theorem]

For questions related to the Chinese Remainder Theorem and its applications.

In number theory and algebra, the Chinese Remainder Theorem states that if $n_1, ..., n_k$ are positive, pairwise relatively prime integers, and $a_1, ..., a_k$ is any collection of integers, there is a unique solution to the system of congruences

$$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{n_k}$$

modulo the product $n_1 n_2 \cdots n_k$.

More generally, consider a principal ideal domain $R$. If $u_1, ..., u_k$ are pairwise relatively prime elements of $R$ and $u = u_1 \cdots u_k$, then there is an isomorphism

$$R/uR \cong R/u_1 R \times \cdots \times R/u_k R$$

by the map

$$x + uR \mapsto (x + u_1 R, ..., x + u_k R)$$

Reference: Chinese remainder theorem.

895 questions
6
votes
2 answers

Chinese Remainder Theorem Explanation

I'm reading through a brief example of the Chinese remainder theorem and am having difficulty understand the process they are going through. Consider two primes p and q. For an arbitrary a < p and b < q, there exists a unique y less than p × q such…
mino
  • 258
4
votes
1 answer

Using the chinese remainder theorem to find the last two digits of $49^{19}$

I am trying to find the last 2 digits of $\ 49^{19}$ but I am having some trouble. So far I know that x = $\ 49^{19}$ mod 100 x = $\ 49^{19}$ mod 25 x = $\ 49^{19}$ mod 4 I can then apply the CRT and set u = 4 $\ *$ ( $\ 4^{-1}$) mod 25 and v = 25…
4
votes
4 answers

Chinese Remainder Theorem with 0 mod n

I'm trying to get the least x from a system of congruences by applying the Chinese Remainder Theorem. Keep running into issues. System of congruences: $$ x \equiv 0 (_{mod} 7) \\ x \equiv 5 (_{mod} 6) \\ x \equiv 4 (_{mod} 5) \\ x \equiv 3 (_{mod}…
MNav
  • 43
3
votes
1 answer

Prove the Chinese Remainder Theorem.

In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these…
Cheese Cake
  • 1,143
3
votes
3 answers

Chinese remainder Theorem in polynomials in one variable.

In a question I was answering, I needed to solve these congruences to proceed, and find the least $k<1000$ $$2k+k^2 = 0 \pmod 3$$ $$ 2k^3 + 6k = 0 \pmod 7$$ $$ k = 0 \pmod 2$$ My try: due to the third statement $$ k = 2j$$ for some integer…
SuperMage1
  • 2,486
3
votes
4 answers

Is there a possible explanation in plain English how to use the Chinese Reminder Theorem?

For example, if it is the problem of Find the smallest integer that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11 In some explanation such as in this article it started to…
2
votes
1 answer

Find the principal remainder of $\frac{431^5 + 611}{27}$

I have this problem: $\frac{431^5 + 611}{27}$ I'm supposed to find the principal remainder by hand. But I have no idea how to start when $431$ has en exponent of $5$. Can someone please explain? Thanks.
Ridertvis
  • 381
2
votes
1 answer

Using Chinese Remainder Theorem when moduli are not pairwise relatively prime

I have this a bit of nightmarish set of equations: $$x \equiv 10\pmod {19271}$$ $$x \equiv 4\pmod {7343}$$ $$x \equiv 8\pmod {9973}$$ For which I am supposed to use Chinese Remainder Theorem to find a solution or to show that one does not exist. Now…
Rebronja
  • 301
2
votes
0 answers

Mistake in Chinese Remainder Theorem

I made this calculator to solve system of congruences using Chinese Remainder Theorem a while ago and it's always seemed to work for problems I tried, but today I noticed that the solution was wrong. (I can't post images - please see this link ) For…
2
votes
1 answer

Chinese Remainder Theorem - solving a modulo with big numbers

I have the calculation: $2^{31}\pmod {2925}$ It's for university and we should solve it like: make prime partition $2^{31}$ mod all prime partitions Solve with Chinese Remainder Theorem. I started with $2925 = 3 \cdot 3 \cdot 5 \cdot 5 \cdot 13$ ,…
Somebody
  • 369
2
votes
2 answers

Chinese Remainder Theorem for non prime-numbers.

Let's say I want to find x such that x leaves remainder 2 when divided by 3 and x leaves remainder 3 when divided by 5. x % 3 = 2 x % 5 = 3 We break down the problem to: x % 3 = 1 x % 5 = 0 Therefore, 5k % 3 = 1 2k % 3 = 1 k = 2 10, when remainder =…
2
votes
2 answers

Wrong applying of simple Chinese Remainder Theorem problem

What am I doing wrong? So for the following equations $$ \begin{align} (*) \left\{ \begin{array}{l} 2x\equiv 3\pmod 5 \\ 4x\equiv 2\pmod 6 \\ 3x\equiv 2\pmod 7 \end{array} \right. \end{align} $$ and $N…
Frank Vel
  • 5,339
1
vote
1 answer

RSA Encryption using Chinese Remainder Theorem and Fermat's Little Theorem

Self-learning RSA encryption, came across this problem and would like help getting a better understanding of it. Already solved 7(a) and 7(b), but need help with number 8. Thanks! Here is my work for the first part:
Mandy
  • 83
1
vote
1 answer

Chinese remainder theorem unique solution

If I have two equations such that $$X\equiv a \pmod b\\ X\equiv c \pmod d$$ I can use linear Diophantine Equations to find multiple solutions to X. Can I find multiple solutions using CRT. what if I have a third equation $$X\equiv e \pmod g$$ How do…
1
vote
1 answer

Chinese remainder theorem with squares

I have to solve a Chinese remainder theorem example where one of the congruence relations is $x^2 = 1 (4)$. I figured out that it should also be possible to write $x=1(2)$. Is this correct and is there a general way how such problems (relations with…
1
2 3 4