Skip to main content

Questions tagged [chinese-remainder-theorem]

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

Filter by
Sorted by
Tagged with
-1 votes
0 answers
53 views

Are there infinitely many primes p for which either $p−1$ or $p+1$ is squarefree?" [duplicate]

It is not known if there is an infinite number of primorial primes. Are there infinitely many primes $p$ for which either $p−1$ or $p+1$ is squarefree?" I imagine this is an open problem also,...
Adam Rubinson's user avatar
2 votes
0 answers
82 views

Homology + Chinese Remainder Theorem =?

Let $M_i, i=1..n$ be a finite collection of pair-wise coprime moduli. The Chinese remainder theorem says that $\Bbb{Z}/M \approx \prod_i \Bbb{Z}/M_i$. Without going into Bezout / Euclidean algorithm,...
SeekingAMathGeekGirlfriend's user avatar
1 vote
3 answers
48 views

Question about Existence Proof for Chinese Remainder Theorem Using Mapping

I'm confused about a proof of existence for the Chinese Remainder Theorem: If the $n_i$ are pairwise coprime, and if $a_1, a_2, \ldots, a_k$ are any integers, then the system $$ \begin{align} x &\...
Hugh Mann's user avatar
2 votes
2 answers
85 views

In polynomial quotient rings over $\mathbb{F}_2$, how to use Chinese Remainder Theorem to solve equations?

Suppose I work over the polynomial quotient ring $\mathbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle$, and I want to solve for polynomials $s[x,y]$ that simultaneously solve the equations \begin{equation} a[...
JoJo P's user avatar
  • 133
2 votes
1 answer
61 views

Period of binary sequences [closed]

Let $k>0$ be an integer. Consider a finite binary sequence $\sigma=(b_0,b_1,...,b_{n-1})$ where $n=2\cdot 3 \cdots p_k $ is the product of the first $k$ primes, and $b_i=1$ iff $i$ is divisible by ...
Michele's user avatar
  • 133
0 votes
0 answers
35 views

Intuition behind terms in Chinese Remainder Theorem solution formula [duplicate]

Given the following equations: $$ a = 2 \ (mod \ 5)$$ and $$ a = 3 \ (mod \ 13)$$ Let $a_1=2$, $a_2=3$, $n_1=5$, $n_2=13$, $m_1=13$, $m_2=5$ Let $m=5 \times 13=65$ Let $$c_i = m_i * (m^{-1}_i mod \ ...
jam's user avatar
  • 81
1 vote
2 answers
50 views

Question over decomposition of $\mathbb{Z}_{mn}$

If $m<n\in\mathbb{N}$ and $(m,n)=1$, then there is a natural isomorphism $h: \mathbb{Z}_{mn}\to \mathbb{Z}_m \times \mathbb{Z}_n$. But I'm a little confused about what happens when multiplying $m$ ...
user760's user avatar
  • 1,670
-1 votes
1 answer
69 views

Modular Solution to $x^2\equiv2 \pmod{2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19 \cdot 23}$ [duplicate]

How many solutions are there to $x^2\equiv2 \pmod{2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19 \cdot 23}$ Is it enough to say by Chinese Remainder Theorem, there must be solutions for all individual ...
shrizzy's user avatar
  • 804
0 votes
0 answers
41 views

Find the least number that obtained when divided by $A$ and $B$ leaves the remainder $a$ and $b$ respectively. Also $A-a=B-b=d$. [duplicate]

Find the least number that obtained when divided by $A$ and $B$ leaves the remainder $a$ and $b$ respectively. Also $A-a=B-b=d.$ My attempt Answer given is $LCM(A,B)-d.$ I tried to prove using the ...
Unknown x's user avatar
  • 849
0 votes
1 answer
62 views

How to show that gcd of two quasiperiods is a quasiperiod?

Definition 3.1.1 in page 25 of this book is the definition of quasiperod and Proposition 3.1.3. shows that gcd of two quasiperiods is a quasiperiod. The whole proof is clear except for the part about ...
Ali's user avatar
  • 281
2 votes
0 answers
37 views

If $x\equiv0\pmod a$ and $x\equiv k\pmod b$, is there a simple expression for $x \pmod {ab}$? [duplicate]

Suppose I know that for some values $x,a,b$ that $$ x \equiv 0\pmod a $$ $$ x \equiv k\pmod b. $$ Is there a simple expression that I can use to get the value of $x$ $\pmod{ab}$ assuming that $a,b$ ...
wjmccann's user avatar
  • 3,105
4 votes
0 answers
99 views

Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$

As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
Juan Moreno's user avatar
  • 1,190
-1 votes
1 answer
84 views

Why must the order of $7$ either be $5$ or $10$ in $\mathbb{Z}_{11}^*$? [closed]

I have an old math exam question with the solution included, but there is a certain step of the solution I don't understand. Task: Determine the order of $7$ in $\mathbb{Z}_{44}^*$ Solution: From the ...
Isaac16726's user avatar
3 votes
1 answer
122 views

Given a tuple of $k$ distinct integers, is there a generator list in a $\mathbb{Z}/n\mathbb{Z}$ that matches the tuple?

Motivation: In $\langle\mathbb{Z}/7\mathbb{Z},\times\rangle,\ \langle 3\rangle = (3,2,6,4,5,1).$ Given a $k-$tuple of distinct integers, $q_1, q_2, \ldots, q_k,$ (all nonzero) does $\exists$ integers ...
Adam Rubinson's user avatar
0 votes
0 answers
37 views

Stationary sequence of orders in $(\mathbb{Z}/p^n\mathbb{Z})^\ast$

I am struggling to prove the following statement: Let $p, q$ be coprime numbers. For all $n \in \mathbb{N}^*$, we define $t_n$ as the order of $[q]$ in $(\mathbb{Z}/{p^n}\mathbb{Z})^\ast$. Show that $(...
Arthur Filippi's user avatar
0 votes
0 answers
27 views

The Modular Part Method (System of congruences) [duplicate]

I was reading this short book about Modular arithmetic, towards the end (Chapter 6.3) it provided a fast way to solve a linear system of congruences, instead of solving two of them at a time. Here's ...
Lorenzo Spada's user avatar
0 votes
0 answers
41 views

Question about sum of indices of prime factorisation of consecutive numbers that might be solved via Chinese remainder theorem? [duplicate]

Consider a set of (not necessarily consecutive) prime numbers, $S: = \{ p_1, p_2, \ldots, p_k\}.\ $ For each integer $n,$ for each $1\leq j \leq k,$ let (the function) $u_n(p_j)$ be the greatest ...
Adam Rubinson's user avatar
0 votes
0 answers
34 views

How do you solve a system of linear congruences with moduli that are not relatively prime to each other? [duplicate]

So I know that if all of your moduli are relatively prime to each other, you can simply apply the Chinese remainder theorem. However, what do you do if the moduli are not relatively prime?
David's user avatar
  • 9
1 vote
0 answers
105 views

Find $n \in N$ where $133^5 + 110^5 + 84^5 + 27^5 = n^5$

This question was posited to me by a coworker. I was able to get the answer, but I'm unsatisfied with how I did it. $n < 354$ $n^5 = 133^5 + 110^5 + 84^5 + 27^5 < (133+110+84+27)^5$ $n < ...
Cameron's user avatar
  • 11
1 vote
1 answer
64 views

Chinese Remainder Theorem and ideals generated in localizations

In Milne's notes on algebraic number theory (https://www.jmilne.org/math/CourseNotes/ANT.pdf), on page 51, Corollary 3.14 and 3.15 both used the argument "use Chinese Remainder Theorem and look ...
spiderchips's user avatar
2 votes
1 answer
46 views

reverse construction chinese remainder theorem

How can I determine the original number $x\in[pq]$ from its remainders $x_p$ and $x_q$, when it's divided by two relatively prime numbers $p$ and $q$, given that $\gcd(p, q) = 1$? I learned about a ...
Daniel Aviv's user avatar
1 vote
1 answer
93 views

"Converse" to Chinese Remainder Theorem

There are lots of posts on MSE and the web titled "converse to CRT" but this is not the same. The following is from "Multiplicative number theory I: Classical theory" by Hugh L. ...
Ali's user avatar
  • 281
3 votes
1 answer
638 views

A confusion in understanding a solution to a number theory problem

Prove that there exists a positive integer n, such that for all integers $k$ the number $k^2+k+n$ has no prime divisors less than $2008$. Here is the solution my book gave I don't understand why ...
user avatar
2 votes
2 answers
180 views

Conjecture on a stronger form of Chinese Remainder Theorem (on ideals): $\prod_{i=1}^m A_i+\prod_{i=m+1}^n A_i\overset{?}{=}R$?

Notation: By two ideals $A,B$ in $R$ are comaximal we mean $A+B=R$. Assume $R$ is a commutative ring with $1$, and $\{A_i\}_{1\le i\le n}$ are pairwise-comaximal ideals in $R$. The Chinese Remainder ...
Asigan's user avatar
  • 1,932
2 votes
0 answers
47 views

Sums over residues with non-coprime moduli

Let $f$ be a $1$-periodic function (like $e^{2\pi ix}$). How can I evaluate a sum like $$\sum _{x=1}^{q}\sum _{y=1}^rf\left (\frac {x}{q}+\frac {y}{r}\right )$$ if $q,r$ are not coprime? If they're ...
tomos's user avatar
  • 1,662
1 vote
1 answer
60 views

Chinese Remainder Theorem without GDC=1 [duplicate]

I was looking at this problem: The smallest positive integer greater than 1 that leaves a remainder of 1 when divided by 4, 5, and 6 lies between which of the following pairs of numbers? I was ...
user avatar
5 votes
0 answers
103 views

If $a,b,c \in \mathbb{Z}$ are distinct, then there are infinitely many $n$ such that $a+n$, $b+n$ and $c+n$ are relatively prime. [duplicate]

If $a,b,c \in \mathbb{Z}$ are distinct, then there are infinitely many $n \in \mathbb{Z}$ such that $a+n$, $b+n$ and $c+n$ are pairwise relatively prime. I'm not sure how to solve this problem. Here'...
user avatar
0 votes
0 answers
28 views

Prove Polyvariable Chinese remainder theorem

Currently, I read some articles about Many-variable CRT (polyvariable CRT) But I hardly find a proof for it. As far as I can find, I see that the theorem is stated like this: Let $k$ and $n$ be a ...
Anh Nam's user avatar
0 votes
0 answers
42 views

Isomorphisms between cyclic groups

I was solving an exercise which asked to determine all abelian groups of order 48 two by two not isomorphic with each other and it seemed natural to me to use in the process the following proposition: ...
bocceri's user avatar
  • 212
2 votes
1 answer
146 views

Chinese Remainder Theorem: A categorical perspective

Chinese remainder theorem is extremely important in the theory of rings, it is stated that there is a canonical isomorphism between $R/\bigcap I_i$ and $\prod R/I_i$. However, from the proof, neither ...
Liam's user avatar
  • 333
2 votes
1 answer
136 views

Chinese remainder theorem (equivalence)

I have read a text where it says: " The Chinese remainder theorem states that: $$\begin{align*} x &\equiv a_{1}\pmod{m_1}\\ x &\equiv a_{2}\pmod{m_2}\\ &\vdots\\ x &\equiv a_{n}\...
ops's user avatar
  • 343
-1 votes
1 answer
68 views

Why does Chinese Remainder Theorem imply that respective multiplicative inverse groups are isomorphic?

I came across this result: $\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z}$ implies that $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times} \cong \left(\mathbb{Z}/n_1\...
niobium's user avatar
  • 1,231
0 votes
1 answer
87 views

Condition to prove Chinese remainder theorem for finitely many ideals [duplicate]

I was trying to understand the condition in proving the Chinese remainder theorem below Let R be a ring and $I_1,\dots, I_m$ be ideals of R such that $I_j+\bigcap_{k\neq j}I_k=R$ for $0<j\leq m$. ...
oscarmetal break's user avatar
0 votes
0 answers
51 views

Prove that if $m$ and $n$ are coprime then there exist integers $x$ and $y$ such that $mx≡1\pmod n$ and $ny≡1\pmod m$ [duplicate]

The problem also elaborates that $x$ is a multiplicative inverse of $m\pmod n$, as is $y$. All I've got so far is that, according to Bézout's identity, if $m$ and $n$ are coprime, $\exists x,y|mx+ny=d$...
Felix's user avatar
  • 1
1 vote
1 answer
71 views

Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n

Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n. First, we try $m=1$. Then $n=4$, and clearly it is not true that $4 | (a-1)$ for all odd a. For $m=2,...
Alfred's user avatar
  • 869
4 votes
0 answers
154 views

Chinese remainder theorem, how does one justify the existence of the solution, without intuiting it?

Chinese remainder theorem for three equations goes like this: The system of congruences $$x \equiv a_1 \pmod {n_1}$$ $$x \equiv a_2 \pmod {n_2}$$ $$x \equiv a_3 \pmod {n_3}$$ where $n_1$, $n_2$, $n_3$...
niobium's user avatar
  • 1,231
0 votes
0 answers
13 views

Can you check compatibility of Linear Congruences with non-coprime moduli before simplifying? [duplicate]

Given a pair of linear congruences of the form below where the $m_i$ are not necessarily coprime. $$a_1 x \equiv b_1 \pmod{m_1}$$ $$a_2 x \equiv b_2 \pmod{m_2}$$ I know that if the $a_1 = a_2 = 1$, ...
Jeff's user avatar
  • 895
3 votes
1 answer
163 views

What is the quotient ring $\mathbb{R}[x]/(x-1)(x+1)(x+3)(x-5)$ using Chinese Remainder Theorem?

I know that it is not a PID since $((x-1)(x+1) + I)(x+3)(x-5) + I) = 0$ where $I$ is the ideal we are quotienting by, and this means it is not even an Integral Domain since it has zero divisors ...
user13121312's user avatar
0 votes
0 answers
25 views

Solving a simultaneous system of linear congruences [duplicate]

I wish to solve the following system of congruences using the Chinese remainder theorem: $$13X \equiv 3 (\text{mod} 15), \\ 2X \equiv 6 (\text{mod} 10).$$ I have reduced this system to $$X \equiv 6 (\...
V. Elizabeth's user avatar
2 votes
3 answers
109 views

Number of solutions of $y^2=x^3$ in $\mathbb{Z}_{57}$

The title explains the question. It was one of the 25 questions of a 3 hour olympiad, so I hope it is not too hard. The olympiad is for undergraduate students, so I also hope it doesn't use any "...
Arthur Queiroz Moura's user avatar
3 votes
1 answer
114 views

Deriving a CRT formula for noncoprime moduli

The German Wikipedia page on the Chinese Remainder Theorem states the following Given are the two simultaneous congruences: $$ \begin{aligned} & x \equiv a \quad(\bmod n) \\ & x \equiv b \...
calculatormathematical's user avatar
0 votes
0 answers
56 views

Find the remainder without differentiation [duplicate]

The degree of $f(x)$ is not given. When $f(x)$ is divided by $(x-3)$ the remainder is $15$ and when $f(x)$ is divided by $(x-1)^2$ the remainder is $2x+1$. Now we need to find the remainder when $f(x)$...
Angelo Mark's user avatar
  • 5,976
-1 votes
1 answer
104 views

Remainder of a product of numbers

When the positive integer N is divided by 6, the remainder is 3. When the positive integer M is divided by 4, the remainder is 1. Which of the following integers could be the remainder when the ...
Sruthi's user avatar
  • 1
2 votes
1 answer
94 views

How to find unique least number of moduli when performing arithmetic addition of two integers using Chinese Remainder theorem?

Here's my problem. I have to find the sum of 123456 and 987456 using chinese remainder theorem with least moduli. We know sum = 123456+987456=1,110,912. Let me assume that we have to use n number of ...
CREATIVITY Unleashed's user avatar
0 votes
0 answers
65 views

Using Chinese remainder theorem for Gaussian integers

I have the following two questions that am trying to solve. Use Chinese remainder theorem to solve this system of congruence $x \equiv i \mod (1+i)$ and $x \equiv 2 \mod 3i$. $x \equiv (−3+i) \mod ...
affkoff's user avatar
5 votes
1 answer
95 views

$9$ divides $a - 5$. $18$ divides $a - 14$. $24$ divides $a - 20$. Find $a$. [closed]

I find this tricky for some reason. Don't really know how to approach it. I found the answer, but it was by luck. So first off, I write down: $$a = 9x +5$$ $$a = 18y + 14$$ $$a = 24z +20$$ Not really ...
Mixoftwo's user avatar
  • 133
-1 votes
1 answer
300 views

A number when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5 respectively but when its divided by 11 the remainder is 0. FIND THE NUMBER [duplicate]

A number when divided by $2,3,4,5,6$ leaves remainder $1,2,3,4,5$ respectively but when its divided by $11$ the remainder is $0$. FIND THE NUMBER I tried taking LCM of $2,3,4,5,6$ and subratcing by $1(...
Bruh's user avatar
  • 15
1 vote
0 answers
124 views

Using Chinese Remainder theorem to find number of solutions of modular exponentiation mod composite number [duplicate]

I am struggling to understand a simple fact that should follow from the Chinese remainder theorem. Suppose we have a system of equations. $$ x^n = 1 (mod\ p) $$ $$ x^n = 1 (mod\ q) $$ Where $p, q$ are ...
user9855939's user avatar
1 vote
0 answers
58 views

$X \equiv 1 \pmod{20} \land X \equiv 1 \pmod{22} \iff X \equiv 1 \pmod{\operatorname{lcm}(20,22)}$

$X \equiv 1 \pmod{20} \land X \equiv 1 \pmod{22} \iff X \equiv 1 \pmod{\operatorname{lcm}(20,22)}$ I dont understand how I would go about this proof. I am trying to use this to solve a CRT-problem ...
hack03er's user avatar
1 vote
1 answer
92 views

Nonconstant polynomial $f(x) \in \mathbb{Z}[x]$ with $f(0)=1$, then there exists an $n \in \mathbb{N}$ such that $f(n)$ is divisible by 2021 primes.

I'm working on a problem which is stated as follows : Let $f(x) \in \mathbb{Z}[x]$ be a nonconstant polynomial with $f(0)=1$. Then, there exists $n \in \mathbb{N}$ such that $f(n)$ is divisible by $...
Oopsilon's user avatar
  • 129

1
2 3 4 5
19