# Questions tagged [chinese-remainder-theorem]

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

820 questions
Filter by
Sorted by
Tagged with
25 views

### Reverse a mod in an equation

Being quick and to the point, I have the following equation. (A * M)%F = B I want to solve for M. How do you move the modular F?
• 11
21 views

### Recursive Modular Arithmetic Problem with Pirates and Coins

Four pirates discover a chest of gold coins. The first pirate divides the gold coins in the chest into 4 piles of coins, each having the same number of coins, and finds that there is 1 coin left over ...
• 19
28 views

### show that there are arbitrarily long sequences of consecutive positive integers which are not sums of two squares

Let $p_1, p_2, . . . , p_k$ be different prime numbers. By the Chinese Remainder theorem, show that for each $k ∈ N$ there exists an integer n such that $p_1 |n+1; p_2 |n+2; ...; p_k |n+k$ but $p^2_k$ ...
• 39
1 vote
76 views

### Find solution using infinite descent.

Can someone help with a task? Need to find a solution other than $(0,0,0)$ with infinite descent. $x,y,z\in\mathbb{Z}$. Any help would be appreciated. The equation is $x^2-3y^2=2z^2$. I tried to ...
• 23
1 vote
56 views

67 views

### Chinese Remainder Theorem, discrete math problem [closed]

$5^{2003}$ $\equiv$ $3 \pmod 7$ $5^{2003}$ $\equiv$ $4\pmod{11}$ $5^{2003} \equiv 8 \pmod{13}$ Solve for $5^{2003}$ $\pmod{1001}$ (Using Chinese remainder theorem).
35 views

### Chinese remainder theorem when modulus are not distinct, is my solution right? also - is this a good way to solve such kind of questions? [duplicate]

i learnt about the Chinese remainder theorem, and im trying to solve the following question: find the minimal solution x for (1)x = 11 mod 24 (2)x = 5 mod 18 (3)x = 5 mod 30 i know that in order to ...
• 1
108 views

### Can you generalise the Chinese Remainder Theorem to noncommutative rings without identity?

Ultimately, my question is: does the following theorem hold? Let $I_1, ..., I_n$ be ideals of some ring $R$, with $R = I_i + I_j$ for $1 \leq i < j \leq n$. Then for any $r_1, ..., r_n \in R$ ...
• 135
1 vote
23 views

• 531
47 views

### Finding all vectors $(x_1, x_2, x_3) \in \mathbb{Z}_{2021^2}^3$ such $x_1x_2x_3 \equiv 43 \;(\text{mod } 2021^2)$

I am trying to find all vectors $(x_1, x_2, x_3) \in \mathbb{Z}_{2021^2}^3$ that satisfies following condition $$x_1x_2x_3 \equiv 43 \;(\text{mod } 2021^2)$$ Since $2021^2 = 43^2 * 47^2$ and $43, 47$ ...
• 691
175 views

### What is the property of co-primes that allows CRT to work?

I have been reading about the Chinese Remainder Theorem and I have the following question: Basically the CRT says that there is a $1$ to $1$ correspondance between a number $N \in [0, m\cdot n)$ and ...
• 1,517
319 views

59 views

### Congruence system \begin{cases} 3x \equiv 4 \pmod{7}\\ 5x \equiv 9 \pmod{11} \end{cases} [duplicate]

I've started to study number theory, I completely do not understand from my notes how to work this out. Could anyone show me with simple example how to solve this? \begin{cases} 3x \equiv 4 \pmod{7}\\ ...
61 views

### Can we use Chinese remainder theorem to "shrink" a field? attempt 2

Can someone point me to someone that can prove the following, or help me find something similar that is provably correct? See the link near the bottom of this question for a perhaps easier ...
• 5,921
Suppose that we have a field $p^k$, and we want to express values in this field modulo smaller fields $(q_1)^k$, $(q_2)^k$,... I believe that there is a way to do this using the Chinese remainder ...