# 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?
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 ...
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$ ...
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 ...
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 ...
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$ ...
1 vote
23 views

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