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

learn more… | top users | synonyms

0
votes
3answers
24 views

What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
6
votes
1answer
52 views

An Analogue of Chinese Remainder Theorem for Groups

I am trying to prove the following analogue of Chinese remainder theorem for groups: Let $G$ be group and let $H_1, \dots, H_n$ be its normal subgroups such that their indices $[G : H_1], \dots, [G : ...
-3
votes
2answers
34 views

Theorem on the interpretation of the ring $Z_n$ [closed]

$(m, n)=1 \Rightarrow Z_{mn} \cong Z_m$ x $Z_n$ Can anyone please help me with proof for this theorem? Thanks in advance.
0
votes
0answers
37 views

Using Chinese Remainder Theorem to find an integer $x$ for which $ x\equiv 3\pmod 4 x\equiv 5\pmod 9 x\equiv 10\pmod {35} $

Hello I have got problems with understanding the reduction method in CRT. We have got system like this $$x\equiv 3\pmod 4$$ $$x\equiv 5\pmod 9$$ $$x\equiv 10\pmod {35}$$ There is a way to do this ...
0
votes
2answers
23 views

Quadric modular equation

I had to calculate $x$ from $x^2 =x\pmod{10^3}$ I knew that $a = b\pmod{cd} \Rightarrow a=b \pmod c\ \land a=b \pmod d$ when $\gcd(c,d)=1$ Therefore I got two equations : $x^2 = x \pmod 8$ $x^2 ...
1
vote
0answers
26 views

When is the sum of three reduced rationals equal to an integer

When is the sum of three reduced rationals equal to an integer? This may be a duplicate of Question 1550437 but even if it is, there is no answer associated with this other question. Given three ...
0
votes
2answers
72 views

Evaluate all the square roots of 4 mod 77. [closed]

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? Sorry I am just totally confused and do not how to start Evaluate all the square roots ...
0
votes
0answers
28 views

General Chinese remainder theorem proof

Okay, so we have the Chinese Remainder Theorem: If $m_1$ and $m_2$ are coprime then the simultaneous congruences $\left( x \equiv a_1 \mod m_1 \right)$, $\left( x \equiv a_2 \mod m \right)$ have a ...
0
votes
1answer
22 views

Why '$3t \equiv 2 \pmod 5 \implies t \equiv 4 \pmod 5$' is true in resolving congruence?

I want to resolve this system of equations \begin{equation} \begin{cases} x & \equiv & 1 & \pmod 3\\ x & \equiv & 3 & \pmod 5\\ x & \equiv & 2 & \pmod 7\\ ...
1
vote
2answers
25 views

How can I apply the Chinese Remainder Theorem when a modulus is the square of another one?

For example: $$\begin{cases} x = 23 \mod 3 \\ x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$ I know that when two moduli are not mutually prime (for example: $$\begin{cases} x = n \mod 45 \\ x = m \mod ...
1
vote
0answers
12 views

CRT general equal for three congruences - correct?

I saw someone ask a question regarding the congruences below. $c≡1 \mod 143$ $c≡315 \mod 323$ $c≡167 \mod 667$ I tried to solve them with this equation: For any number of congruences $x≡a\mod n$, ...
0
votes
3answers
21 views

Solve three congruences using CRT

How do I solve the following Congruences= $c ≡ 1 \mod 143$ $c ≡ 315 \mod 323$ $c ≡ 167 \mod 667$ I know that the moduli are coprime so there will be a unique solution. Secondly, I know that the ...
4
votes
0answers
101 views

Description of the equalizer of $\prod _j R/I_j \rightrightarrows \prod _{i,j}R/(I_i+I_j)$

This will hopefully be my last question about the chinese remainder theorem. I have asked several questions in an attmept to get a general version without conditions on the ideals which will trivially ...
7
votes
1answer
127 views

Chinese remainder theorem as sheaf condition?

The chinese remainder theorem in its usual version says that for a finite set of pairwise comaximal ideals $R/\bigcap _jI_j\cong \prod _j R/I_j$. In the binary case, the following general statement ...
-1
votes
1answer
23 views

Chinese Remainder Theorem for infinite system

I have a trouble understanding p.7 of the following article: http://www.edb.gov.hk/attachment/en/curriculum-development/kla/ma/IMO/Nov20155-4online.pdf which says the folllowing: By the same ...
4
votes
2answers
202 views

Prove that $R\cong \mathbb{C}^n$

Let $R=\mathbb{C}[x]/(f(x))$ where $f(x)$ is a polynomial of degree $n>0$ which has $n$ distinct complex roots. Prove that $R\cong \mathbb{C}^n$. I tried to define a homomorphism $\phi$ from ...
4
votes
0answers
51 views

Characteristic and minimal polynomials

Given $A\in\Bbb Z^{n\times n}$, is it possible to find characteristic and minimal polynomials of $A$ by chinese remainder theorem if we know characteristic and minimal polynomials respectively of ...
0
votes
0answers
32 views

Combining solutions of subproblems with CRT when solving discrete logarithm problem with composite modulo

Author of this answer reduces the discrete logarithm problem $a = b^x \pmod{N}$, $N=p q r$, $p,q,r\in {\mathbb P}$ to smaller discrete logarithms problems $a = b^y \pmod{p}$ $a = b^z \pmod{q}$ $a = ...
0
votes
2answers
17 views

$g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$

Let $q$ and $p$ be unique primes. $g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$ I know that $g^{p-1} \equiv 1 ...
1
vote
0answers
29 views

Chinese Remainder theorem clarification needed

I'm trying to solve $p\equiv a\pmod{7}$ and $p\equiv b\pmod{4}$ $m_1=(4)^{-1} \pmod 7$ $m_2=(7)^{-1} \pmod 4$ I need to find $m_1'$ and $m_2'$ which I assumed to be the inverse of $m_1$ and ...
1
vote
1answer
29 views

System of congruences with polynomials

How do I go about solving exercises such as this one: Find all polynomials $f(x)$ in $\mathbb{Z}_3$ that satisfy $$f(x) \equiv 1 \space \space \mathrm{mod} \space \space x^2 + 1$$ $$f(x) \equiv x ...
3
votes
3answers
73 views

Solve $x^2\equiv -3\pmod {13}$

Question 1) Solve $$x^2\equiv -3\pmod {13}$$ I see that $x^2+3=n13$. I don't really know what to do? Any hints? The solution should be $$x\equiv \pm 6 \pmod {13}$$ Question 2) Given $x\equiv \pm 6 ...
1
vote
2answers
22 views

How to determine number of solutions modular

Is there a formula for determine the number of solutions (#S) to $x^{3}=1$ mod $(mn)$ where $n \neq m$ are both prime ( ie in the ring $\mathbb{Z}/mn\mathbb{Z}$) I think from the Chinese remainder ...
2
votes
2answers
57 views

Sheafyness and relative chinese remainder theorem

The relative chinese remainder theorem says that for any ring $R$ with two ideals $I,J$ we have an iso $R/(I\cap J)\cong R/I\times_{R/(I+J)}R/J$. Let's take $R=\Bbbk [x_1,\dots ,x_n]$ for $\Bbbk $ ...
4
votes
1answer
75 views

Multi-pullbacks and the relative chinese remainder theorem

Let $I,J$ be two-sided ideals of a ring $R$. In this question I asked for an "automatic" proof of the fact the natural map $R/(I\cap J)\rightarrow R/I\times _{R/(I+J)} R/J$ is an isomorphism (a direct ...
1
vote
1answer
34 views

Canonical map $R/(I\cap J)\rightarrow R/I\times _{R/(I+J)} R/J$ is an isomorphism

From this MSE question I understand the canonical map $R/(I\cap J)\rightarrow R/I\times _{R/(I+J)} R/J$ is an isomorphism for $R$ a commutative ring and $I,J$ ideals. I tried proving this directly ...
6
votes
1answer
94 views

Relative chinese remainder theorem and the lattice of ideals

Let $R$ be a ring with two-sided ideals $I,J$. The proof of the "absolute" chinese remainder theorem revolves around the fact that if $I,J$ cover $R$ in the lattice of ideals, i.e $I+J=R$, then the ...
1
vote
1answer
28 views

How to compute modular reduction in CRT domain?

I'm working with big integers using chinese remainder theorem (CRT). This way I can map some big integer in a set of small ones. I have addition and multiplication simply applying it ...
0
votes
1answer
28 views

Solving a system of congruences

Solve $17x \equiv 3 \pmod {2\cdot 3 \cdot 5 \cdot 7}$ by solving the system $$17 x \equiv 3 \pmod 2 \qquad \qquad 17x \equiv 3 \pmod 3$$ $$17x \equiv 3 \pmod 5 \qquad \qquad 17x \equiv 3 \pmod ...
1
vote
5answers
53 views

($3$^$34$)/$55$ find out the reminder

($3$^$34$)/$55$ find out the reminder MyApproach $3^1$ mod $55$=$3$ $3^2$ mod $55$=$9$ $3^3$ mod $55$=$7$ $3^4$ mod $55$=$6$ and the pattern repeats .. So,I did $3$^$4$.$8$ +$2$=$3^2$=9 mod ...
0
votes
1answer
27 views

System of congruent relations using Chinese remainder theorem

Could someone explain how to use CRT on the following example: $$x\equiv 7\pmod {17}$$ $$x\equiv 9\pmod {13}$$ $$x\equiv 3\pmod {12}$$ $a_1=7$, $m_1=17$, $M=2652$, $\frac{M}{m_1}=156$ $a_2=9$, ...
1
vote
2answers
79 views

The possible remainders when a multiple of 4 is divided by 6, and when a multiple of 2 is divided by 3

I'm currently studying for the GRE and a specific type of question has me stumped. I have a two part question, but first here is one problem and my work: "If x is the remainder when a multiple of 4 ...
1
vote
0answers
29 views

On chinese remainder theorem

Given $a\equiv x \bmod r_1$ and $b\equiv x\bmod r_2$, we can construct $x$ from $$x=a r_2 [r_2^{-1}]_{r_1} + b r_1 [r_1^{-1}]_{r_2}$$ where $(r_1,r_2)=1$ and $[r_2^{-1}]_{r_1}$ is residue class of ...
0
votes
0answers
24 views

Congruence system.

I have this problem, I need to find the smallest possible solution x≡3(mod10),x≡11(mod13),x≡15(mod17). x≡3(mod10),x≡11(mod13),x≡15(mod17). I used Chinese remainder theorem and found that: x1=3,x2=11 ...
1
vote
1answer
28 views

Quick divisibility question

Hello I know that if $a|bc$ and $gcd(a,b)=1$ then $a|c$ but is this the same as if $n_{1}|a,....n_{k}|a$ and $gcd(n_i,n_{j})=1$ for all $i \neq j$ then the product of all the $n_i$ divides a? I ...
2
votes
1answer
57 views

Chinese Remainder Theorem Modular

I have this problem, I need to find the smallest possible solution $$x \equiv 3 \pmod{10}, \\ x \equiv 11 \pmod{13}, \\ x \equiv 15 \pmod{17}.$$ I used Chinese remainder theorem and found that: ...
-1
votes
1answer
25 views

What's the inverse of 1 in (mod x)? (Working in F3)

I'm struggling with a few basic inverses because the Euclidean algorhithm is not working. 1) Inverse of 1 in mod (x) 2) Inverse of -2x in mod (x^2+2x+2) 3) Inverse of -4 in mod (x^2 +2) The ...
1
vote
1answer
36 views

Find a polynomial $q(x)$ of minimal degree in $F_3[x]$ so that the following condition is true:

$q(x)\equiv x ~(\text{mod}(x^2+2))$ $q(x) \equiv 1 (\text{mod} ~x)$ $q(x) \equiv (x+1) (\text{mod} (x^2 + 2x + 2))$ I know that this is a question about the Chinese remainder theorem but I have no ...
2
votes
0answers
49 views

Linear equations modulo different prime through CRT

Given prime $p$ and equations $$a_1x+b_1y+c_1z=d_1\bmod p \\ a_2x+b_2y+c_2z=d_2\bmod p \\ a_3x+b_3y+c_3z=d_3\bmod p$$ where $a_i,b_i,c_i,d_i\in\Bbb Z_p$, we can solve for $x,y,z\in\Bbb Z_p$. Now ...
0
votes
1answer
24 views

A simple modular reconstruction conundrum on CRT

Assume we have two primes $r$ and $s$. Assume that we have $a =N\bmod r$ and $b=N\bmod s$, then can we find $N\bmod rs$ using CRT? All explanations I have found say that if we have $rs>N$, then ...
4
votes
2answers
58 views

How to find solutions to $x^2 \equiv 4 \pmod{91}$?

As the title says, I'm looking to find all solutions to $$x^2 \equiv 4 \pmod{91}$$ and I am not exactly sure how to proceed. The hint was that since 91 is not prime, the Chinese Remainder Theorem ...
0
votes
1answer
79 views

Isomorphisms between groups, and order

Hi first time posting here, I am self studying group theory and came upon the following exercise: Let G=(Z/612Z)* a) using the Chinese rem theorem, construct an EXPLICIT isomorphism f: ...
2
votes
1answer
43 views

Solve the system of conguruences: $x = 2 \bmod7, x = 5 \bmod12, x = 8 \bmod 25$

Question: Solve the system of conguruences: $x = 2 \bmod7, x = 5 \bmod12, x = 8 \bmod 25$ So far I have The solution: $X= B_1X_1C_1 + B_2X_2C_2 + B_3X_3C_3$ and that the answer is -something- ...
0
votes
2answers
49 views

how to solve $rem(8^{5}+9^{5},17)$ & $rem(3^{8}-4^{8},10)$

I am trying to solve $rem(8^{5}+9^{5},17)$ & $rem(3^{8}-4^{8},10)$ but don't know how to start with
0
votes
0answers
32 views

Splitting $\mathbb Z_{pq}$ into direct sum with $\mathbb Z_p$

I'm trying to show there exists $T \subseteq \mathbb Z_{pq}$ such that $\mathbb Z_{pq} = \mathbb Z_p \oplus T$, where $p$ and $q$ are distinct primes. I tried to use Chinese Remainder so we know ...
0
votes
0answers
17 views

C(N,r)%m , m is not prime

How can I calculate C(N,r)%m if m is not a prime number? I know I have to factorise m into primes and then use Chinese Remainder Theorem. But I am unable to understand HOW to relate the Chinese ...
3
votes
1answer
49 views

Jacobi's Symbol

I read online that even when Jacobi's Symbol is 1, it doesn't necessary means that it's legendre Symbol is 1: $$\left(\frac 2 {15}\right) = \left(\frac 2 3\right)\left(\frac 2 5\right) =-1*-1 = 1$$ ...
0
votes
0answers
25 views

Attack El Gamal private key when p is composite

I'm supposed to find private key of El Gamal cypher. I have public key ($p,g,h$) and order of the element g ($q$). $$h = g^x\ mod\ p$$ ($x$ = private key) I have figured out that $p$ is composite, ...
1
vote
1answer
46 views

Prove that there are no solutions to $x^2 + x + 1 \equiv 0$ (mod $n$) in $\mathbb{Z}/_{n}\mathbb{Z}$

Let's say I want to prove that there are no solutions to $x^2 + x + 1 \equiv 0$ (mod $n$) in $\mathbb{Z}/_{n}\mathbb{Z}$ where $n=pq$ and $p$ and $q$ are chosen prime numbers greater than $2$, given ...
1
vote
1answer
31 views

Does this algorithm work as an alternative to the Chinese Remainder Theorem

The Chinese Remainder Theorem is unbelievably effective as a method for finding an integer $x$ where $x \equiv v_1 \pmod {p_1}$, $x \equiv v_2 \pmod {p_2}$, $\dots$, $x \equiv v_n \pmod {p_n}$. My ...