# Questions tagged [chinese-remainder-theorem]

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

567 questions
21 views

### How to find an element of order 30 in the multiplicative group of $\Bbb Z_{900}$?

I need to find at least one element which has order $30$ in the multiplicative group of $\Bbb Z_{900}$. I'm following this approach but not really understood how to apply correctly the CRT to set the ...
39 views

26 views

### Variant of System of linear equation…

Using CRT can we solve: 13925 mod x = y 13811 mod x = 2y 13697 mod x = 3y 13583 mod x = 4y If no, how can this be solved?
44 views

### Chinese Remainder Theorem, when the moduli are pairwise coprime.

I'm trying to learn the Chinese Remainder Theorem and I've run into some problem. The problem I am to solve goes like: Find all $x ∈ Z$ such that $x≡2\pmod{3}$ $x≡3\pmod{5}$ $x≡5\pmod{7}$ Also, ...
30 views

### Find all roots of the polynomial $f(x)=x^3-_p$ in $\mathbb{Z}/1729\mathbb{Z}$

Problem is the same as in the title, Find roots of the polynomial $f(x)=x^3-_p$ in $\mathbb{Z}/1729\mathbb{Z}$. I am specifically asking only for someone to point me in the direction of the method ...
54 views

### $x^{1682}+22x≡1652 (\bmod3599)$.

Hello I'm trying to learn the Chinese Remainder Theorem and now I have the problem from an old exam: $x^{1682}+22x≡1652 (\bmod3599)$. Ok, so what makes this problem difficult for me is the ...
24 views

### Remainders of two integers when divided by another integer n

I am curious if the remainder of u+v is the same as the sum of the two integers separately if they are the same how would one go about proving this
49 views

### The Chinese Remainder Theorem with exponentials

Find all $k∈Z_+$ such that: i) $7834^k≡1$ $(mod$ $8613)$ ii) $7834^k≡6850$ $(mod$ $8613)$ iii) $7834^k≡2703$ $(mod$ $8613)$ iv) $7834^k≡1318$ $(mod$ $8613)$ Where $8613=3^3 *11 *29$ Hi I'm ...
57 views

27 views

### Proving the surjective property in Chinese Remainder Theorem

If $\textrm{R}$ is a commutative ring and $\left\{\textrm{I}_i\right\}_{i=1}^n$ are proper ideals of $\textrm{R}$ with $\textrm{I}_i+\textrm{I}_j = \textrm{R}$ for all $1 \leq i \neq j \leq n$, then ...
70 views

### Simultaneous congruences $3x \equiv 2 \pmod{5}$, $3x \equiv 4 \pmod{7}$, $3x \equiv 6 \pmod{11}$

I am stuck in a simultaneous linear congruence problem: \begin{cases} 3x \equiv 2 \pmod{5} \\[4px] 3x \equiv 4 \pmod{7} \\[4px] 3x \equiv 6 \pmod{11} \end{cases} Using the Chinese remainder theorem, ...
59 views

### Chinese remainder theorem, can't figure it out!

x mod 5 = 3 x mod 7 = 5 x mod 11 = 7 How to determine x? I've been searching on YouTube, but they're giving examples in different ways, for example x ≡ 1(mod 3) I don't understand it, is it ...
14 views

24 views

### How to work out modular arithmetic quickly for cryptography [duplicate]

I am not so good at Mathematics so please kindly forgive my stupidity. Basically, I am learning modular arithmetic for cryptography and so I am struggling in understanding how to do big modular ...
64 views

### How many solutions does $x \equiv x^{-1} \pmod n$ have?

How many solutions does $x \equiv x^{-1} \pmod n$ have? $n$ is defined to be a positive integer, What I believe the solution will be is along the lines of 2 cases: When $n = 1$, the set of ...
126 views

### Some questions about $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$

Given the function: $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$ defined as follows $[x]_{44100} \rightarrow ([x]_{150},[x]_{294})$ Calculate $f(12345)$ - Answered A preimage of (...
44 views

64 views

### $x^2\equiv 5 \pmod{1331p^3}$

Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to $$x^2\equiv 5 \pmod{1331p^3}$$ I began the problem by splitting ...