# Questions tagged [chinese-remainder-theorem]

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

905 questions
Filter by
Sorted by
Tagged with
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,...
• 20.7k
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,...
1 vote
48 views

• 81
1 vote
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$ ...
• 1,670
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 ...
• 804
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 ...
• 849
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 ...
• 281
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$ ...
• 3,105
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 ...
• 1,190
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 ...
• 317
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 ...
• 20.7k
37 views

• 11
1 vote
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 ...
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 ...
1 vote
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. ...
• 281
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 ...
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 ...
• 1,932
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 ...
• 1,662
1 vote
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 ...
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'...
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 ...
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: ...
• 212
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 ...
• 333
136 views

• 511
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 "...
114 views

1 vote
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 ...
• 11
1 vote
### 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 \$...