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

learn more… | top users | synonyms

2
votes
0answers
20 views

Question about the Chinese Remainder Theorem and the residue class ring ${\bf Z}/p\# {\bf Z}$

In a question that I asked on MO, Terence Tao observed that: The Chinese Remainder Theorem tells us that the residue class ring ${\bf Z}/p\# {\bf Z}$ is isomorphic (as a ring) to the product of ...
1
vote
1answer
35 views

How can I find the common solution for the following linear congruences : [on hold]

How can I find the common solution for the following linear congruences : $1.)$ $x \equiv 5 \pmod {13}$ $x \equiv 3 \pmod {12}$ $x \equiv 2 \pmod{35}$ $2.)$ $x \equiv 2 \pmod{35}$ $x \equiv ...
0
votes
1answer
25 views

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 ...
7
votes
0answers
41 views

The difference between the ring version and module version of Chinese Remainder Thereom.

Chinese Remainder Theorem for Commutative Rings If $R$ is a commutative ring with $1$ and $I, J$ are ideals of $R$ that are pairwise coprime or comaximal (meaning $I + J = R$), then $IJ = I \cap J$, ...
5
votes
1answer
74 views

If $R/I \times R/J$ is isomorphic to $R/(I\cap J)$ as $ R $-modules, then $I + J = R$. [duplicate]

If $R$ is a commutative ring with identity and $I$ and $J$ are ideals of $R$ such that $R/I \times R/J$ is isomorphic to $R/(I\cap J)$ as $R$-modules, then $I + J = R$. I know this is the ...
2
votes
1answer
38 views

Show that if $R$ is commutative, then $\mathrm{Ann}(n_1) + \mathrm{Ann}(n_2) = R$.

Let $R$ be a commutative ring with $1$, and let $M$ be a cyclic $R$-module with generator $m$ (so that $M=Rm$). Suppose that $M = N_1 \bigoplus N_2$ for some submodules $N_1$ and $N_2$ of $M$. Let ...
1
vote
1answer
29 views

Chinese remainder theorem to solve 3 mod 11 and 11 mod 13 [closed]

Im trying to Decrypt a cipher text which has been encrypted using RSA and whose resulting value is 20. public parameters are N = 143 and e = 17 . I've gotten down to 3 mod 11 and 11 mod 13 and I've ...
1
vote
3answers
86 views

Show that $R/(I \cap J) \cong (R/I) \times (R/J) $

My question actually follows from this one: Show that if $I + J = R$, then $R/(I \cap J) \cong R/I \times R/J$ What I don't understand is why is it necessary for $I+J=R$, in order for $$ ...
1
vote
1answer
37 views

There exist arbitrarily long sequences of consecutive integers that are not square-free

Let $a$ and $n$ be positive integers. A sequence of $n$ consecutive integers $(a, a+1, a+2,...,a+(n-1))$ is called a Wolczuk of length $n$ if every integer in the sequence is divisible by some perfect ...
4
votes
2answers
78 views

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. [duplicate]

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. $1990 = 2 \times 5 \times 199$. Now $a \equiv 0 \pmod {2}$, $a \equiv 4 \pmod{5}$ and $a \equiv 29 \pmod{199}$. Taking first two together we ...
5
votes
2answers
44 views

Simultaneusly solving $2x \equiv 11 \pmod{15}$ and $3x \equiv 6 \pmod 8$

Find the smallest positive integer $x$ that solves the following simultaneously. Note: I haven't been taught the Chinese Remainder Theorem, and have had trouble trying to apply it. $$ \begin{cases} ...
2
votes
0answers
30 views

Why do we keep the LCM modulo in the Chinese Remainder Theorem?

I'm doing my homework and I'm struggling to get an answer. I'm taking number theory and we're working on a problem to solve congruences. We've got: $ x\equiv 1 \pmod{5}\\ x\equiv 3 \pmod{8}\\ x\equiv ...
1
vote
0answers
24 views

Chinese remainder - Error in my solution

I have the following congruence system: $x \equiv 1 \mod 5 \\ x \equiv 2 \mod 7 \\ x \equiv 0 \mod 8 \\ x \equiv 3 \mod 11$ I used the Chinese Remainder Theorem to get a solution, but it only ...
2
votes
4answers
35 views

Chinese Remainder Theorem for $x\equiv 0 \pmod{y}$

Can anyone solve the following system of congruences using CRT step-wise, without skipping any part? $$\begin{cases} x\equiv 3 \pmod{7}\\ x\equiv 3 \pmod{13}\\ x\equiv 0 \pmod{12}\end{cases}$$ The ...
1
vote
3answers
75 views

Solution congruence system $ x \equiv 11\pmod{36},\,x \equiv 7\pmod{40}, \,x \equiv 32\pmod{75}$

Have solution the following congruence system? $$\begin{align} x & \equiv 11\pmod{36}\\ x & \equiv 7\pmod{40}\\ x & \equiv 32\pmod{75} \end{align}$$ Point of ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
1
vote
2answers
61 views

If every pair of congruence equations admits solutions, then the entire system admits solutions

Let a system of three linear congruence equations in integers be given; \begin{cases}x\equiv b_1\mod c_1\\ x\equiv b_2\mod c_2\\ x\equiv b_3\mod c_3\\ \end{cases} with $c_1,c_2,c_3\in\mathbb ...
0
votes
3answers
34 views

Solving a system of congruences using the Chinese Remainder Theorem

Suppose I have the congruences: $x \equiv 3 ($mod $7)$ $x \equiv 8 ($mod $9)$ $x \equiv 1 ($mod $5)$ $x \equiv 1($mod $16)$ The Chinese Remainder Theorem says I will have a solution $($mod ...
1
vote
1answer
30 views

Using CRT to prove a single congruence relation

I am trying to prove that $2^{700} \equiv 1 \mod 3625$ and I am supposed to use the Chinese Remainder Theorem as part of my proof. I know that the Chinese Remainder Theorem tells me that a solution ...
-1
votes
1answer
61 views

Does $x^2=83\pmod{101}$ have solutions? without calculating them

Does $x^2=83\pmod{101}$ have solutions? without calculating them. I'm not sure how to tackle this without solving, I tried using chinese remainder and quadratic reciprocity.
1
vote
1answer
31 views

Non-linear congruence equation

I want to find solutions to the equation $x^3 + 2x - 3 \equiv 0 (mod 45)$. I have already found solutions to $x^3 + 2x - 3 \equiv 0 (mod 5)$ and $x^3 + 2x - 3 \equiv 0 (mod 9)$, simply by brute ...
4
votes
2answers
174 views

Converse to Chinese Remainder Theorem

So as seen on this question Converse of the Chinese Remainder Theorem, we know that if $(n,m) \neq 1$, then $\mathbb{Z} /mn \mathbb{Z} \ncong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$, ...
2
votes
3answers
37 views

How to find all solutions to system of congruences with Chinese Remainder Theorem?

This is from Discrete Mathematics and its Applications Here is my work so far gcd(3, 4) = 1 $\,$gcd(3, 5) = 1$\,$gcd(4,5) = 1 $\quad$ mod 3 $\quad$ mod 4 $\quad$mod 5 x $\equiv$ 4 * 5$\qquad$3 * ...
1
vote
1answer
34 views

Why doesn't the author straight up multiply the 15 by 2 in Chinese Remainder Theorem?

This is from a Youtube video on the Chinese Remainder Theorem -https://www.youtube.com/watch?v=ru7mWZJlRQg The value at each column is the product of the mod of the two other columns(so moding will ...
2
votes
1answer
41 views

Why doesn't the author subtract everything by two first before applying modulus?

This is from a youtube video on the Chinese Remainder Theorem - https://www.youtube.com/watch?v=ru7mWZJlRQg What the author has done thus far is basically 1.Make sure that the mods, 3, 4, 5 are ...
2
votes
1answer
41 views

Number Theory: Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

I need to find how many incongruent solutions exist to the equation: $x^2 \equiv 1(mod\space m)$. I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number ...
1
vote
0answers
15 views

$x ≡ a \pmod{m}, x ≡ b\pmod{n}, x ≡ c\pmod{r}$ [duplicate]

What could be an example of three positive integers $m, n$, and $r$, and three integers $a, b$, and $c$ such that the $\mathrm{gcd}$ of $m, n$, and $r$ is $1$, but there is no simultaneous solution to ...
0
votes
2answers
36 views

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 ...
1
vote
1answer
70 views

very hard question using chinese remainder theorem

Q. let $p$ and $q$ be distinct odd prime numbers. Prove that for any $x \in \mathbb{Z} /pq$ we get $$x^{(pq-p-q+3)/2} \equiv x \mod pq$$ we have just learnt the chinese remainder theorem so I have ...
3
votes
4answers
64 views

Solving modulus equation systems

I am studying for a test in discrete math and I created my own question but I cannot seem to solve it. Is it possible to solve the following equation system (without brainless testing), and if so, ...
1
vote
2answers
76 views

System of congruences and Chinese remainder theorem

Find all the integers satisfying this system of congruences $$\begin{cases} x \equiv 2 \pmod 5\\ x \equiv 1 \pmod {10}\\ x \equiv 0 \pmod 3 \end{cases} $$ I think you use Chinese remainder theorem ...
2
votes
0answers
45 views

Chinese Remainder Theorem with with non-pairwise coprime moduli

I have a system of congruences: $$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 5\pmod 6 \\ x\equiv 0\pmod 7 $$ 2, 3, 4, 5, 6, 7 are non-pairwise coprime, ...
5
votes
1answer
108 views

The Chinese Remainder Theorem for Rings.

Exercise: The Chinese Remainder Theorem for Rings. Let $R$ be a ring and $I$ and $J$ be ideals in $R$ such that $I+J = R$. (a) Show that for any $r$ and $s$ in $R$, the system of ...
2
votes
0answers
101 views

Generalisation of chinese remainder theorem on ideals of ring without 1

Let $I_1,\dots,I_n$ be (two-sided) ideals of a ring $R$ (not necessarily with 1), which are pairwise co-maximal, i.e. $\forall i\ne j\in \mathbb{Z}_{[1,n]}$, $I_i+I_j=R$. Let $f:R\to R/I_1\times ...
0
votes
1answer
51 views

Chinese Remainder Theorem for prime powers

Let's say I want to find some $x$ that leaves a remainder of $a_1$ when divided by prime power $p^{k_1}$, and a remainder of $a_2$ when divided by $p^{k_2}$, and a remainder of $a_3$ when divided by ...
1
vote
2answers
104 views

Chinese remainder theorem for non-prime / non-coprime moduli

If I want to find some number $x$ where it leaves a remainder when divided by some prime $p$, and another remainder when divided by some prime $q$, and so on, I can use the Chinese Remainder Theorem. ...
16
votes
1answer
262 views

Flaw or not flaw in Excel's RNG?

I have a question about my understanding of an article of B.D. McCullough (2008) about Excel's implementation of the Wichmann-Hill random number generator (1982). First, a bit of context The ...
0
votes
1answer
27 views

Ideals of $\mathbb{Z}/{p_{1}^{k_{1}}..p_{m}^{k_{m}}}$

I need to describe all the ideals of $\mathbb{Z}/{p_{1}^{k_{1}}..p_{m}^{k_{m}}}$ I suppose that trivials, and $(0,..,1_{i},..,0)\mathbb{Z}/{p_{1}^{k_{1}}..p_{m}^{k_{m}}}$ for any $i$ and nilradicals ...
1
vote
2answers
50 views

Chinese remainder theorem other way around

I need to solve the following equation: $x^2\equiv 1 (\textrm{mod }1000)$ According to the chinese remainder theorem I can rewrite this as: $x^2 \equiv 1 (\textrm{mod }8)$ and $x^2 \equiv 1 ...
0
votes
1answer
35 views

Big-$\mathcal{O}$ notation for CRT and Extended Euclidean Algorithm

I am very unfamiliar with Big-$\mathcal{O}$ run time calculation. I know that for addition the run time is $\mathcal{O}(\log n)$ and for multiplication the run time is $\mathcal{O}(\log^2 n)$. How ...
1
vote
1answer
29 views

Cubic residues over $\mathbb{Z}_{p^2}^{*}$

Definition: $x\in\mathbb{Z}_{n}^{*}$ is a cubic residue if there exists $y\in\mathbb{Z}_{n}^{*}$ s.t. $y^3\equiv x \pmod{n}$. I have been asked to prove (and I already did) that if $n=pq$, ...
3
votes
4answers
57 views

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$. Hello. I am working on a review sheet for my test tomorrow and I am stuck on this ...
0
votes
1answer
30 views

System of congruences with not coprime numbers

I have a system of congruences, for example $ x \equiv 2 \mod 15$ $ x \equiv a \mod 21$ where $a$ is an integer to be determined. I have to find all the values of $a$ for which the system has ...
0
votes
3answers
42 views

Chinese Remainder Theorem Finding the Modulo

Find numbers $t,u,v$ so that $33t+2 = 20u+13 = 29v-1 $ This is a Chinese Remainder Theory problem, but the problem I am having is finding what are the appropriate modulo. I figure it is easiest to ...
2
votes
3answers
34 views

Solutions for a system of congruence equations

I have a system $$ \begin{cases} x \equiv 7 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ How can I show that the system does not have any solutions? I know that the first implies that $x = ...
3
votes
1answer
87 views

If $n\mid m$ prove that the canonical surjection $\pi: \mathbb Z_m \rightarrow \mathbb Z_n$ is also surjective on units

Not sure if this is the right proof (i found it online): Since $n\mid m$, if we factor $m = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $n = p_1^{\beta_1}p_2^{\beta_2}\cdots ...
0
votes
3answers
46 views

Does a system om congruence equations have solutions?

I have a system of congruence equations $$ \begin{cases} x \equiv 17 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ I need to investigate the system and see if they've got any solutions. I know ...
0
votes
1answer
53 views

Isomorphism with Euler phi function

Let $m_i > 1$, where $1 ≤ i ≤ n$, be integers, pairwise relatively prime. Let $m = m_1 \cdots m_n$. Let $\phi(m)$ denote the order of the group $(Z/mZ)^×$. The function $\phi : Z_+ → Z_+$ is called ...
1
vote
0answers
32 views

Chinese Remainder Problem with three equations

Let's consider: $$*\begin{cases} 7x \equiv 2 \mod 5\\ 3x \equiv 2 \mod 4 \\ 5x \equiv 2 \mod 6 \end{cases}$$
0
votes
1answer
28 views

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. ...